Description
给定$n$，求合法的$(x_1 , x_2 , x_3 , … , x_{2m})$组数。一组$x$是合法的，当且仅当
- $\forall i \in [1,2m], \, x_i \in Z^+ , \, x_i \mid n$
- $\prod_{i=1}^{2m} x_i \leq n^m$
合法的$(x_1 , x_2 , x_3 , … , x_{2m})$可能有很多，请你输出方案数$mod \, \, 998244353$。
Input
一行由空格隔开的两个整数，分别是 n 和 m。
$n \leq 10^9 , \, m \leq 100$
Output
一行表示答案。
Solutions
这题的难点就在于$\prod_{i=1}^{2m} x_i$可能存在某些质因数的指数个数大于$n^m$，从而难以统计答案。
考虑避免这种情况。
注意到$\prod_{i=1}^{2m} n = n^{2m} = (n^m)^2$。如果存在一组方案满足$\prod_{i=1}^{2m} x_i < n^m$，那么必定有$\frac{n^{2m}}{\prod_{i=1}^{2m} x_i} = \prod_{i=1}^{2m} \frac{n}{x_i} > n^m$。
同理可得，一组$> n^m$方案能得到一组$<n^m$的方案。
换言之，$> n^m$的方案数与$< n^m$的方案数是相等的。
如果将$\prod_{i=1}^{2m} x_i$划分成$S_1, \, S_2 ,\, S_3$分别表示$< n^m , \, = n^M , \, > n^m$的方案，那么显然有$S_1+S_2+S_3 = \sigma(n)^{2m} , \, S_1 = S_3$。因此只需要求出$S_2$即能解决问题。
那么现在的问题转换成求$\prod_{i=1}^{2m} x_i = n^m$的方案数。这个问题直接对$n$质因数分解，并对其质因数的指数个数求其方案即可。
时间复杂度$O(m^2\log n)$
CODE
CODE - Click Here