题解：P5253 [JSOI2013] 丢番图

· · 题解

题目传送门 更好的阅读体验

题目简述

给定一正整数 n，求 \left|\left \{ \{x\in \mathbb{Z_+},y\in \mathbb{Z_+}\}|\frac{1}{x}+\frac{1}{y}=\frac{1}{n} \right\} \right|。

题目思路

转化

对于方程 \frac{1}{x}+\frac{1}{y}=\frac{1}{n}，两边同乘 xyn 得 xn+yn=xy。

移项得 yn - xy=xn。

两边同除 n - x 得 y = \frac{xn}{x-n}。

因为 y\in \mathbb{Z_+} ，所以 \frac{xn}{x-n}\in\mathbb{Z_+}。

又因为 \frac{xn}{x-n} = \frac{(x - n)n + n^2}{x-n}=n+\frac{n^2}{x-n}，简单分析可得 x|n^2 且 x\le n。

于是原问题转化为求 x|n^2 且 x\le n 的 x 的数量。

处理

如何计算？别的题解都使用数学方法，但我不会所以就有了一个暴力的方法。

可以发现满足条件的 x 的数量很少，所以可以直接枚举 x。

证明：

方法一，写一个真正暴力的代码跑 n=10^{14} 发现只有 421。

方法二，考虑数学证明。

设 n=\prod _{i=1}^mp_i^{c_i}，则 n^2=\prod _{i=1}^mp_i^{2c_i}，m\le \log n^2。

因为 x 是 n^2 的约数，我们对 n^2 的质因子进行搜索，dfs(nw,last) 表示现在得出的数为 nw，枚举到第 last 个质数。 由于枚举的数是单调递增的，所以当枚举的数大于 n 时直接返回，这样就可以保证时间复杂度为 \Theta(\text{答案})，前文以证答案小于 \log n^2。

code

#include <bits/stdc++.h> 
#define int long long 
using namespace std; 

using PII = pair<int, int>; 
int n, ans, t;               // ans: 答案数量；t: 原始n值 
vector<PII> p;               // 存储n²的质因子分解结果 (质数, 指数) 

// DFS枚举n²的约数，统计<=t的约数个数 
// nw: 当前约数；last: 上一个使用的质因子索引（避免重复） 
void dfs(int nw, int last) { 
    if (nw > t) return;      // 约数超过n，停止搜索 
    ans++;                   // 统计当前有效约数 
    if (nw == t || last == p.size())  return;  // 边界条件：约数等于n或无更多质因子 

    // 枚举下一个质因子及其幂次 
    for (int i = last + 1; i < p.size();  i++) { 
        int prime = p[i].first; 
        int max_exp = p[i].second; 
        int power = prime;  // prime^1, prime^2, ..., prime^max_exp 
        for (int j = 1; j <= max_exp; j++) { 
            dfs(nw * power, i); 
            power *= prime; 
            if (nw * power > t) break;  // 提前终止溢出情况 
        } 
    } 
} 

signed main() { 
    cin >> n; t = n; 
    // 分解n的质因子（用于计算n²的质因子） 
    for (int i = 2; i <= n / i; i++) { 
        if (n % i == 0) { 
            p.push_back({i,  0}); 
            while (n % i == 0) p.back().second++,  n /= i; 
        } 
    } 
    if (n > 1) p.push_back({n,  1}); 

    // n²的质因子指数翻倍 
    for (auto& [prime, exp] : p) exp *= 2; 

    dfs(1, -1);  // 从约数1开始枚举，初始无使用质因子 
    cout << ans << '\n'; 
    return 0; 
}