【数论】P4167樱花
题目描述
求不定方程 \(\frac {1}{x} + \frac{1}{y} = \frac{1}{n!}\)的正整数解的个数
\(n \leq 100^6\)
Solution
化简得
以上,我们可以看出,所求正整数解的个数其实就是\((n!)^2\)的约数的个数。
这个当然可以暴力求,但是很慢。这里直接给出求解方式
for(int i = 1; pri[i] <= n; ++i){
int tot = 0, x = n, y = pri[i];
while(x) tot += x / y, x /= y;
ans = (ans * (tot << 1 | 1) % mod) % mod;
}
举个例子或许好理解。
13!中有多少个3?包含3这个因数的数有:3, 6, 9, 12,分别包含1, 1, 2, 1个3,总数就是5个。而13 / 3 = 4, 4 / 3 = 1, 4 + 1 = 5。别的例子皆可。因而默认上面的代码是正确的。
Code
#include <iostream>
#include <cstdio>
using namespace std;
inline long long read() {
long long x = 0; int f = 0; char c = getchar();
while (c < '0' || c > '9') f |= c == '-', c = getchar();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f? -x:x;
}
const int mod = 1e9 + 7;
int n, pri[1000006], cnt;
long long ans = 1;
bool v[1000006];
inline void get_pri() {
for (int i = 2; i <= 1000000; ++i) {
if (!v[i]) pri[++cnt] = i;
for (int j = 1; j <= cnt && pri[j] * i <= n; ++j) {
v[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
}
int main() {
n = read();
get_pri();
for (int i = 1; pri[i] <= n; ++i) {
int tot = 0, x = n, y = pri[i];
while (x) tot += x / y, x /= y;
ans = (ans * (tot << 1 | 1) % mod) % mod;
}
printf("%lld\n", ans);
return 0;
}