题解 P5253 【丢番图】

· · 题解

upd 20210508：感谢 @SegmentTreeJuruo 关于一处符号的指正，现已修改。

一看到丢番图就想到那个年龄故事。

这道题是一道简单数学推柿子题，个人认为难度大约\color{green}{\text{绿}}到\color{blue}{\text{蓝}}。

大致思路

开启推柿子模式：

\frac{1}{x}+\frac{1}{y}=\frac{1}{n} yn+xn=xy xy-xn-yn=0 xy-xn-yn+n^2=n^2 (x-n)(y-n)=n^2

综上，满足 \frac{1}{x}+\frac{1}{y}=\frac{1}{n} 便可转化为不含分式的 (x-n)(y-n)=n^2。这样的话，只需要算出 n^2 大于 n 的因子即 n 的因子即可。我们这时立刻想到了分解质因数，根据因数数量公式就可以把最终满足条件的个数算出来。

最后端上香喷喷的代码！

CODE

#include <stdio.h>
long long n;
int main(void) {
    scanf("%lld", &n);
    long long ans = 1ll;
    for (long long i = 2ll; i * i <= n; ++i)
        if (n % i == 0) {
            long long k = 0ll;
            while (1) {
                if (n % i != 0ll)
                    break;
                n /= i;
                ++k;
            }
            ans *= (k << 1ll) + 1ll;
        }
    if (n > 1)
        ans *= 3;
    printf("%lld\n", (ans + 1) >> 1ll);
    return 0;
}

到这里这篇题解就结束了。如果您觉得还珂以，就顶一下（给个赞）呗！谢谢大家！