「HDU 1299」Diophantus of Alexandria

Description

题目链接：HDU 1299

求解如下丢番图方程的正整数解个数：

$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\quad (x,y,n\in\mathbb{N}^+,x\le y)$$

本题 $T$ 组数据。

数据范围：$1\le n\le 10^9$

---

Solution

我们先将方程消去分母：

$$xy-n(x+y)=0$$

由于 $xy$ 中 $x$ 和 $y$ 都是二次的，那么我们使用十字相乘法，将未知数放在方程左侧：

$$(x-n)(y-n)=n^2$$

此时我们发现 $x$ 和 $y$ 都是一次的了，只需要将 $n^2$ 分解质因子，用约数和定理来计算答案即可。

$$\sigma(n)=\prod(c_i+1)$$

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

---

Code

#include <cstdio>

int main() {
    int T,cs=0;
    for(scanf("%d",&T);T--;) {
        int n;
        scanf("%d",&n);
        int ans=1;
        for(int i=2;i*i<=n;++i) {
            int cnt=0;
            while(n%i==0) n/=i,++cnt;
            ans*=2*cnt+1;
        }
        if(n>1) ans*=3;
        printf("Scenario #%d:\n%d\n\n",++cs,(ans+1)/2);
    }
    return 0;
}