[luogu5253]丢番图【数学】

[luogu5253]丢番图【数学】 传送门

【传送门】

题目大意

求\(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\)有多少组不同的解。

分析

将式子转化成\((n-x)(n-y)=n^2\)的形式。

那么很明显，因为我们要求正整数的解，那么就是要求\(a\times b=n^2\)的解的个数。

又变成了约数个数的问题。

代码

#include <bits/stdc++.h>
#define ll long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
using namespace std;
template <typename T>
inline void read(T &x) {
    x = 0; T fl = 1; char ch = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-') fl = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= fl;
}
ll n, ans;
int main() {
    read(n); ans = 1;
    for (ll i = 2; i * i <= n; i ++) {
        if (n % i == 0) {
            ll tot = 0;
            for (; n % i == 0; n /= i) ++ tot;
            ans *= (tot * 2 + 1);
        }
    }
    if (n > 1) ans *= 3;
    printf("%lld\n", (ans + 1) / 2);
    return 0;
}