专栏文章

题解：P5253 [JSOI2013] 丢番图

CCharllote_
P5253题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miosmwbr
此快照首次捕获于
2025/12/03 00:29
3 个月前
此快照最后确认于
2025/12/03 00:29
3 个月前
查看原文
题目传送门 更好的阅读体验

题目简述

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

题目思路

转化

对于方程 1x+1y=1n\frac{1}{x}+\frac{1}{y}=\frac{1}{n}，两边同乘 xynxyn 得 xn+yn=xyxn+yn=xy。
移项得 yn−xy=xnyn - xy=xn。
两边同除 n−xn - x 得 y=xnx−ny = \frac{xn}{x-n}。
因为 y∈Z+y\in \mathbb{Z_+} ，所以 xnx−n∈Z+\frac{xn}{x-n}\in\mathbb{Z_+}。
又因为 xnx−n=(x−n)n+n2x−n=n+n2x−n\frac{xn}{x-n} = \frac{(x - n)n + n^2}{x-n}=n+\frac{n^2}{x-n}，简单分析可得 x∣n2x|n^2 且 x≤nx\le n。
于是原问题转化为求 x∣n2x|n^2 且 x≤nx\le n 的 xx 的数量。

处理

如何计算？别的题解都使用数学方法，但我不会所以就有了一个暴力的方法。
可以发现满足条件的 xx 的数量很少，所以可以直接枚举 xx。
证明：
方法一，写一个真正暴力的代码跑 n=1014n=10^{14} 发现只有 421421。
方法二，考虑数学证明。
设 n=∏i=1mpicin=\prod _{i=1}^mp_i^{c_i}，则 n2=∏i=1mpi2cin^2=\prod _{i=1}^mp_i^{2c_i}，m≤log⁡n2m\le \log n^2。
τ(n2)=∑i=1m(2ci+1)\tau (n^2)=\sum_{i=1}^{m}(2c_i + 1) 看似是 Θ(n)\Theta (n) 级别的，但是因为 55 以后的质数都严格大于 22 的两倍，加上 x≤nx\le n 的限制条件使答案小于 log⁡n2\log n^2。
因为 xx 是 n2n^2 的约数，我们对 n2n^2 的质因子进行搜索，dfs(nw,last) 表示现在得出的数为 nw，枚举到第 last 个质数。 由于枚举的数是单调递增的，所以当枚举的数大于 nn 时直接返回，这样就可以保证时间复杂度为 Θ(答案)\Theta(\text{答案})，前文以证答案小于 log⁡n2\log n^2。

code

C
#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; 
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...