题意简述

求不定方程：

\[\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!\)的质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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!\)的质因数的个数可以直接计算出来，不需要一个一个枚举。

1
2
3
4
5
6
7
8
9
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;
}

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}