题解：P11416 [EPXLQ2024 fall round] Simple Math Problem

Eason_cyx · 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;
}