给出 (n) 求 (frac{1}{x}+frac{1}{y}=frac{1}{n!}) 的正整数解数量 (mod (10^9+7))
(nleq10^6)
数论
先化式子
令 (a=x-n!, b=y-n!)
原题即为求 (ab=n!^2) 的整数解数量,即为 (n!^2) 的因数个数
令 (n!=displaystyleprod_{p_iin p}p_i^{c_i})
答案即为: $$displaystyleprod_{p_iin p}{(2 imes c_i+1)}$$
(p.s. :) 如果原题为本质不同的方案数,即 (verb|Luogu5253 丢番图|) ,答案即为 (frac{ans+1}{2}) 。因为对于每个 ({(a, b) | a eq b}) 都被多算了一遍。
至于求出 (c_i) ,可以先筛出 (1cdots n) 的每个质数 (p) ,然后考虑阶乘 (n!) 一共包含多少个 (p)
(n!) 中 (p) 的个数等于 (1cdots n) 中每个数包含 (p) 的个数之和。
在 (1cdots n) 中, 至少包含一个 (p) 的数显然有 (lfloorfrac{n}{p} floor) 个。而至少包含两个 (p) 的数有 (lfloorfrac{n}{p^2} floor) 个。不过其中的一个质因子已经在 (lfloorfrac{n}{p} floor) 中统计过了,所以只需要再统计第二个质因子,即累加上 (lfloorfrac{n}{p^2} floor) ,而不是 (2 imeslfloorfrac{n}{p^2} floor) 。 (lfloorfrac{n}{p^3} floor, lfloorfrac{n}{p^4} floor, cdots) 同理
综上所述, (n!) 中质因子 (p) 的个数为: $$displaystylesum_{p^kleq n}{lfloorfrac{n}{p^k} floor}$$
时间复杂度 (O(nlog n))
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10, P = 1e9 + 7;
int n, tot, p[maxn];
void sieve() {
int tmp = sqrt(n) + 1;
for (int i = 2; i <= tmp; i++) {
for (int j = i * i; j <= n; j += i) {
p[j] = 1;
}
}
for (int i = 2; i <= n; i++) {
if (!p[i]) p[++tot] = i;
}
}
int main() {
scanf("%d", &n);
sieve();
int ans = 1;
for (int i = 1; i <= tot; i++) {
int x = 1, s = 0;
while (1ll * p[i] * x <= n) {
x *= p[i], s += n / x;
}
ans = 1ll * ans * (s << 1 | 1) % P;
}
printf("%d", ans);
return 0;
}