自动搬运

查看原文

来自洛谷，原作者为

	Dry_ice Я всегда буду любить мисс Tracy Reznik.

搬运于2025-08-24 22:08:44，当前版本为作者最后更新于2020-08-10 14:52:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

大致思路

开启推柿子模式：

综上，满足 $\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;
}

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