题解 P4167 [Violet]樱花

题目

求不定方程

\[\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\]

的正整数解(x,y)的数目。

---

先开始万恶的推式子。。。

原式：

\[\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\]

通个分：

\[xy - n!x - n!y= 0\]

补点东西：

\[xy - n!x - n!y + (n!)^2= (n!)^2\]

\[(n! - x)(n! - y) = (n!)^2\]

此时答案就是\((n!)^2\)的约数个数

---

统计\(n!\)的约数个数：

把1~n质因数分解，统计各质因子的幂数和即可

再用唯一分解定理统计

注意线性筛素数时记录每一个数的最小质因子，分解就具体看代码

代码

#include <cstdio>
#include <cctype>
#include <vector>

using namespace std;

template<typename T> inline void read(T &x) {
    x = 0; T k = 1; char in = getchar();
    while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
    while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
    x *= k;
}

typedef long long ll;

const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

ll n, ans;
int cnt[N], g[N];
bool vis[N];
vector<int> pri;

inline void make_prime() {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i])
            pri.push_back(i), g[i] = pri.size() - 1;
        for (int j = 0; j < pri.size() && i * pri[j] <= n; ++j) {
            vis[i*pri[j]] = true;
            g[i*pri[j]] = j;
            if (i % pri[j] == 0)
                break;
        }
    }
}

int main() {
    read(n);
    make_prime();
    for (int i = 2; i <= n; ++i) {
        int x = i;
        while (x != 1)
            cnt[g[x]]++, x /= pri[g[x]];
    }
    ans = 1;
    for (int i = 0; i <= pri.size(); ++i)
        if (cnt[i])
            ans = (ans * (cnt[i] * 2 + 1)) % MOD;
    printf("%lld\n", ans);
    
    return 0;
}