数论与算法实践：丢番图方程1/x+1/y=1/n的解法

1. 题目背景与数学原理解析

丢番图方程作为数论中的经典问题，其研究历史可以追溯到古希腊时期。题目给出的方程形式为1/x + 1/y = 1/n，这看似简单的分数方程实则蕴含着深刻的数论原理。

1.1 方程变形与整数解条件

首先我们对原方程进行变形：
1/x + 1/y = 1/n
=> (x+y)/xy = 1/n
=> n(x+y) = xy
=> xy - nx - ny = 0
=> xy - nx - ny + n² = n²
=> (x-n)(y-n) = n²

这个变形过程揭示了问题的本质：寻找满足(x-n)(y-n)=n²的正整数对(x,y)。由于x和y的对称性，我们只需考虑x≤y的情况，最后统计本质不同的解。

1.2 因数分解与解的数量关系

设n的质因数分解为：
n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k

那么n²的质因数分解就是：
n² = p₁^(2a₁) × p₂^(2a₂) × ... × p_k^(2a_k)

根据数论知识，n²的正因数个数为：
(2a₁+1)(2a₂+1)...(2a_k+1)

由于(x-n)和(y-n)都是n²的因数，且(x-n)≤(y-n)，所以本质不同的解的个数就是n²的因数对数，即(因数个数+1)/2。

2. 算法设计与实现解析

2.1 质因数分解算法

核心思路是对n进行质因数分解，计算每个质因数的指数，然后根据公式计算结果。算法流程如下：

1. 初始化结果ans=1
2. 从i=2开始，尝试分解n的质因数
3. 当i*i≤n时，检查n是否能被i整除
4. 如果能整除，统计这个质因数的指数k
5. 根据公式ans *= (2k+1)
6. 处理剩余的质因数（如果n>1）
7. 最终答案为(ans+1)/2

2.2 C++代码逐行解析

cpp复制#include <stdio.h>
long long n;
int main(void) {
    scanf("%lld", &n);  // 读取输入的正整数n
    long long ans = 1ll;  // 初始化结果为1
    
    // 质因数分解过程
    for (long long i = 2ll; i * i <= n; ++i)