% 给定 n , m n,m n,m，你需要求出 m m m 个数 ( a 1 , a 2 , … , a n ) (a_1,a_2,\dots ,a_n) (a1,a2,…,an)，满足 ∏ i = 1 2 m a i ⩽ n m , ∀ i ∈ [ 1 , 2 m ] ∩ Z , a i ∈ N ∗ , a i ∣ n \prod_{i=1}^{2m}a_i\leqslant n^m,\\\forall i\in[1,2m]∩\Z ,a_i\in \N^*,a_i|n i=1∏2mai⩽nm,∀i∈[1,2m]∩Z,ai∈N∗,ai∣n
% 求可行的方案数。 数据范围 1 ⩽ n ⩽ 1 0 9 , 1 ⩽ m ⩽ 100 1\leqslant n\leqslant 10^9,1\leqslant m\leqslant 100 1⩽n⩽109,1⩽m⩽100
% 令 T T T 为所有 a i a_i ai 的乘积，可以发现，满足 T ⩾ n m T\geqslant n^m T⩾nm 的方案数和满足 T ⩽ n m T\leqslant n^m T⩽nm 的方案数量相等。换句话说，我们可以考虑所有方案加上满足 T = n m T=n^m T=nm 的方案，然后除以二。 可以发现，若 n n n 的约数个数为 d ( n ) d(n) d(n)，则只考虑第二条的方案数量为 [ d ( n ) ] m [d(n)]^m [d(n)]m。那么现在我们只需要考虑如何求出满足 T = n m T=n^m T=nm 的情况即可。 既然所有 a i a_i ai 之积为 n m n^m nm，若 n n n 中只含有一个质因数 p p p，这说明所有 a i a_i ai 中含有的 p p p 的总数量，必然等于 n n n 中含有的 p p p 的数量，换言之，我们单独考虑每个质数 p p p ，若 n n n 中包含了 k k k 个 p p p，则贡献的方案数等于在 2 m 2m 2m 个位置放 k k k 个 p p p 的方案数。 然后我们来考虑第二条限制，这说明每个位置上放的质因数 p p p 的个数不能超过 k k k，这也决定了这部分内容不可能使用排列组合完成，必须使用动态规划。 我们考虑 f[i][j] \texttt{f[i][j]} f[i][j] 表示在 i i i 个位置中放进 j j j 个数的方案数量。转移如下 f [ i ] [ j ] = ∑ t = w k × m f [ i − 1 ] [ t − w ] f[i][j]=\sum_{t=w}^{k\times m}f[i-1][t-w] f[i][j]=t=w∑k×mf[i−1][t−w]
% 边界为 ∀ i ∈ [ 1 , 2 × m ] ∩ Z , f [ i ] [ 0 ] = 1 \forall i\in [1,2\times m]∩\Z ,f[i][0]=1 ∀i∈[1,2×m]∩Z,f[i][0]=1。时间复杂度为 T ( n ) = Θ ( n + d ( n ) × m × log 2 n ) \text T(n)=\Theta(\sqrt n+d(n)\times m\times \log_2 n) T(n)=Θ(n +d(n)×m×log2n)
