自动搬运

查看原文

来自洛谷，原作者为

	Eason_cyx Play like you never did before?

搬运于2025-08-24 23:07:09，当前版本为作者最后更新于2024-12-18 13:35:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

@junjie_zhao 在我写这题的时候一直嘲讽我 /kel

感谢 @Augenstern5 提供的指导。

记 $n-m=x$，则题目中的条件变为

展开，得

显然有 $nx \bmod x = 0$，所以问题变成了 $n^2 \bmod x = 0$，也就是找 $n^2$ 的所有因数，且由于 $1 \le m \lt n$，所以我们要找的就是 $1 \le x \lt n$ 中所有 $n^2$ 因数的个数。

记 $n^2$ 共有 $p$ 个因子，那么显然 $p$ 是奇数。注意到 $n^2$ 的因子中除了 $n$ 以外一定可以分成 $\frac{p-1}{2}$ 组，每组的两个数 $a,b$ 都可以有 $a \times b = n^2$。那么显然一定有 $\max(a,b) > n$，所以这样每一组对答案的贡献就是 $1$；那么最后答案就是 $\frac{p-1}{2}$。

又因为显然有如下结论：

假设 $n=p_1^{q_1}p_2^{q_2}\dots p_k^{q_k}$，那么 $n^2=p_1^{2\times q_1}p_2^{2\times q_2}\dots p_k^{2\times q_k}$。

所以最终直接对 $n$ 进行质因数分解即可。假设我们得到了 $n=p_1^{q_1}p_2^{q_2}\dots p_k^{q_k}$，则有一个定理：$n$ 的质因数个数为 $\displaystyle\prod_{i=1}^{k}(q_i+1)$。所以有 $p=\displaystyle\prod_{i=1}^{k}(2\times q_i+1)$。

时间复杂度 $O(T\sqrt n)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int, int> mp;
signed main() { ios::sync_with_stdio(false); cin.tie(0);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n; mp.clear();
		for(int i = 2;i * i <= n;i++)
			if(n % i == 0) {
				while(n % i == 0) n /= i, mp[i]++;
			} if(n != 1) mp[n]++; for(auto i : mp) mp[i.first] *= 2;
		long long num = 1; for(auto i : mp) num = (num * (mp[i.first] + 1)); cout << num / 2 << "\n";
	}
	return 0;
}