「Violet 5」樱花

题目大意：给定 $n$，求不定方程 $\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!}$ 的正整数解 $(x,y)$ 的个数。$n \leq 10^6$

PoPoQQQ的题解

转化成求 $(n!)^2$ 的约数个数。

$n!$ 的质因子分解中，质数 $p$ 的个数为

$$\dfrac{n}{p}+\dfrac{n}{p^2}+\cdots+\dfrac{n}{p^k}$$

#include <cstdio>
 
const int N = 1000005, xzy = 1e9 + 7;
int n, np[N], p[N], tot, ans = 1;
 
void prime() {
    for (int i = 2; i <= n; ++i) {
        if (!np[i]) p[++tot] = i;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
            np[i*p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}
 
int main() {
    scanf("%d", &n);
    prime();
    for (int i = 1; i <= tot; ++i) {
        int x = n, cnt = 0;
        while (x) (cnt += x / p[i]) %= xzy, x /= p[i];
        ans = 1LL * ans * (cnt << 1 | 1) % xzy; //加上指数为0的情况
    }
    printf("%d\n", ans);
    return 0;
}