首先有一个结论：当 \(n\) 有平方质因子时，除非 \(n=4\)，否则有无数解。
一个并不严谨的证明：
设 \(n = \prod\limits_{i=1}^m p_i^{c_i},x = k\prod\limits_{i=1}^m p_i^{c_i+c'_i}\)，其中 \(\gcd(n,k)=1\)。
则 \(\sigma_0(x) = \sigma_0(k)\prod\limits_{i=1}(c_i+c'_i+1)\)。
对于 \(1 \le i \le m\)，考虑关于 \(c'_i\) 的方程 \(p_i^{c_i} = c_i + c'_i + 1\)。
对于其解 \(c'_i = x_0\)，设 \(d = \frac{c_i + x_0 + 1}{p_i}\)。注意到除非 \(c_i=1\) 或 \(p_i=c_i=2\)，一定仍存在 \(x'_0\) 满足 \(c_0 + x'_0 + 1 = d\)，此时便可将一个 \(p_i\) 的贡献加入到 \(k\) 中，并且易知这样的 \(k\) 有无数种。
而若 \(p_i = c_i = 2\)，易证除非 \(m=1\)，否则亦有无数解。
首先 Pollard-Rho 分解质因子，然后容易发现 \(m \le 15\)，考虑用一个简单的状压 DP 统计答案。
代码：
1 |
|