神题-计算

给定$n$，求$(x_1,x_2,\dots x_{2m})$的合法方案数。一组$x$是合法的，当且仅当 > 1.对于任意的$i\in [1,2m]$，有$x_i\in Z^+$且$x_i|n$ > 2.$$\prod_{i=1}^{2m}x_i \leq n^m$$ 合法的方案数可能有很多，所以输出方案数$mod\ 998244353$的值 看上去完全不可做啊，于是敲完$45$暴力分走人（考场上最高分就是$45$） 其实，这道题的解法~~非常简单~~非常神奇 由于$x$可以整除$n$，所以我们可以把条件$2$变一下 $$\prod_{i=1}^{2m}\frac{n}{x_i} \geq n^m$$ 我们只考虑$\prod_{i=1}^{2m}\frac{n}{x_i} > n^m$的情况 每一个$\frac{n}{x_i}$，都与之相对应着一个$x_i$，换句话说，如果我们将上式的$\frac{n}{x_i}$替换成$x_i$，会得到相同的方案个数（让新数列的$x_i$取原数列的$\frac{n}{x_i}$即可），这意味着 满足 $$\prod_{i=1}^{2m}x_i < n^m$$ 的合法方案个数与满足 $$\prod_{i=1}^{2m}x_i > n^m$$ 的合法方案个数相同！ 而这两种情况的方案个数和与满足$\prod_{i=1}^{2m}x_i = n^m$的方案个数之和恰好是所有情况（即只满足条件$1$）的方案个数 每个数都可以取值为$n$的因数，一次快速幂就可以计算出所有方案。 对于$\prod_{i=1}^{2m}x_i = n^m$的方案总数，我们把$n^m$想象成很多个球，要放进$x_1,x_2,\dots x_{2m}$这$2m$个箱子里。具体来说： 1.对$n^m$进行分解，不妨设 $$n^m=p_1^{mk_1}p_2^{mk_2}\dots$$ 其中,$p_1,p_2,\dots$是质数 然后，对于每个质因数，将$mk$这个幂想象成$mk$个球，要放进$2m$个箱子里，组合数即可。 由于每轮放的球都不一样（分别代表着$p_1,p_2,\dots $），最后将答案乘起来即可，设为$ans$。 最后答案即为$($总方案数$-ans)/2+ans$