LOJ#10202. 「一本通 6.2 练习 5」樱花
智子
2021-07-28 15:57:18
## 题意简述
求不定方程：
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$$
的正整数解 $(x, y)$ 的数目。
## 题目分析
### 数学推导
这道题给人的第一印象是难以解决，因为$n!$是一个很大的数，不可能一一枚举答案。所以我们必须对题目中给出的式子进行处理。
$$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$$
$$\frac{x + y}{xy} = \frac{1}{n!}$$
$$n!(x + y) = xy$$
可得 $x \geq n!, y \geq n!$，代入$x = n! + a, y = n! + b$得
$$n!(n! + a + n! + b) = (n! + a)(n! + b)$$
$$n!(2(n!) + a + b) = (n!)^2 + n!(a + b) + ab$$
$$2(n!)^2 + n!(a + b) = (n!)^2 + n!(a + b) + ab$$
$$(n!)^2 = ab$$
因为每一组不同的$(a, b)$都对应一组正整数解$(x, y)$，所以本体的答案就是$(n!)^2的因子个数。$
### 朴素算法（40分）
先筛出从 $1$ 到 $N$ 之间每一个质数，在依次枚举$n!$的质因数
```cpp
for(int i = 2; i <= n; i++) {
for(int j = 1; p[j] <= i; j++) {
if(i % p[j] == 0) {
int k = i;
while(k % p[j] == 0) {
s[j]++;
k /= p[j];
}
}
}
}
int ans = 1;
for(int i = 1; i <= m; i++) {
ans = (long long)ans * (s[i] * 2 + 1) % MOD;
}
```
### 正解
事实上，$n!$的质因数的个数可以直接计算出来，不需要一个一个枚举。
```cpp
for(int i = 1; i <= m; i++) {
for(long long j = p[i]; j <= n; j *= p[i]) {
s[i] = (s[i] + n / j) % MOD;
}
}
int ans = 1;
for(int i = 1; i <= m; i++) {
ans = (long long)ans * (s[i] * 2 + 1) % MOD;
}
```
## 代码实现
```cpp
#include<cstdio>
using namespace std;
const int MAXN = 1000000 + 5;
const int MOD = 1e9 + 7;
bool b[MAXN];
int p[MAXN], s[MAXN];
int m = 0;
int main() {
for(int i = 2; i < MAXN; i++) {
if(!b[i]) {
p[++m] = i;
for(int j = i * 2; j < MAXN; j += i) {
b[j] = true;
}
}
}
int n;
scanf("%d", &n);
for(int i = 1; i <= m; i++) {
for(long long j = p[i]; j <= n; j *= p[i]) {
s[i] = (s[i] + n / j) % MOD;
}
}
int ans = 1;
for(int i = 1; i <= m; i++) {
ans = (long long)ans * (s[i] * 2 + 1) % MOD;
}
printf("%d\n", ans);
return 0;
}
```