形式化题目

给定正整数 $n$（$1 \leqslant n \leqslant 10^6$），统计满足

的正整数对 $(x, y)$ 的数目，答案对 $10^9 + 7$ 取模。

样例：$n = 2$ 时 $n! = 2$，共有 $(3,6),(4,4),(6,3)$ 三组解，答案为 $3$。

这道题的关键在于：$x, y$ 没有任何上界，直接枚举 $x$ 或 $y$ 都不可行——必须先把方程变成一个"能数"的结构。

正解

思路

第一步：把方程变形成乘积式

设 $N = n!$。方程两边同乘 $xyN$：

把左边整体移到右边，再"凑"一个 $N^2$：

这一步把加法方程变成了乘积方程，是数方程计数的经典手法（和 $x^{-1} + y^{-1} = 1$ 类问题通用）。

第二步：解的个数 = $N^2$ 的约数个数

若 $(x,y)$ 是正整数解，由 $xy = N(x+y) > Nx$ 得 $y > N$，同理 $x > N$，于是 $x - N$ 和 $y - N$ 都是正整数，且乘积为 $N^2$。

反过来，取 $N^2$ 的任意正因子 $d$，令

则 $(x-N)(y-N) = d \cdot \frac{N^2}{d} = N^2$，代回原方程成立，且 $x, y > N \geqslant 1$ 为正整数。

所以"正整数解 $(x,y)$"与"$N^2$ 的有序因子对 $(d_1, d_2)$（$d_1 d_2 = N^2$）"一一对应，答案就是

用样例 $n=2$ 验证一下这个双射：$N = 2$，$N^2 = 4$ 的三个约数 $1, 2, 4$ 恰好对应三组解：

第三步：计算 $d((n!)^2)$——只需要 $n!$ 的质因数分解

$N^2$ 可能是一个天文数字（$10^{6!}$ 级别），但约数个数只由质因数分解决定：

若 $n! = \prod p^{e_p}$，那么 $(n!)^2 = \prod p^{2 e_p}$，由约数个数公式

所以整个问题坍缩成一件事：求出 $n!$ 里每个质数 $p \leqslant n$ 的指数 $e_p$。

第四步：线性筛 + 逐数分解

$e_p$ 有两条等价的求法：

• Legendre 公式：$e_p = \sum_{k \geqslant 1} \lfloor n / p^k \rfloor$；
• 逐数分解：把 $2, 3, \dots, n$ 每个数分解，指数累加。

两者复杂度同阶。这里选逐数分解，配合线性筛的最小质因子：筛出每个合数的最小质因子 $\mathrm{min\_prime}[v]$，之后分解任何一个 $v$ 只需要不断"除以自己的最小质因子"，无需试除。把每个数分解出的指数累加进 exp[p]，就得到了 $n!$ 的标准分解。

这里有一个容易踩的坑：必须先把所有 $v$ 的指数累加得到 $n!$ 的总指数 $e_p$，再对每个质数乘上 $2 e_p + 1$。如果对每个 $v$ 分解出一个质因子就立刻乘 $(2e+1)$，那就变成了 $\prod_v v^2$ 的因子结构错位，结果完全不对。

代码

Python 版：

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
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 22:43
# update_at: 2026-09-30 22:43

from math import prod
from sys import stdin

MOD = 10**9 + 7


def solve() -> None:
    n = int(stdin.buffer.read())

    # 线性筛：只记录每个合数的最小质因子，其余因数分解全靠它跳转。
    min_prime = [0] * (n + 1)
    primes: list[int] = []
    for v in range(2, n + 1):
        if min_prime[v] == 0:              # v 没有更小的质因子 → v 是质数
            min_prime[v] = v
            primes.append(v)
        for p in primes:
            if p > min_prime[v] or p * v > n:
                break
            min_prime[p * v] = p

    # 先把 2..n 每个数的质因子指数累加起来，得到 n! 的标准分解。
    exp = [0] * (n + 1)
    for v in range(2, n + 1):
        while v > 1:
            p = min_prime[v]
            while v % p == 0:              # 除尽同一个质因子
                v //= p
                exp[p] += 1

    # ans = d((n!)^2)：n! 里指数为 E 的质因子，平方后指数 2E，贡献 2E+1。
    print(prod(2 * e + 1 for e in exp) % MOD)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:10
 * update_at: 2026-10-05 23:12
 */
// main.cpp：正解。把 1/x + 1/y = 1/n! 变形为 (x-n!)(y-n!)=(n!)^2，
// 正整数解数目 = (n!)^2 的约数个数，用线性筛分解 1..n 求质因子指数后连乘。
#include <iostream>

typedef long long ll;

const int MAXN = 1000000 + 5; // n 的上界
const ll MOD = 1000000007;

int min_prime[MAXN]; // min_prime[v] = v 的最小质因子，线性筛中顺带求出
int primes[MAXN]; // primes[1..prime_cnt] 存放筛出的质数
int prime_cnt;
ll exp_of_prime[MAXN]; // exp_of_prime[p] = p 在 n! 中的指数

int n;

// 线性筛：每个合数只被它的最小质因子筛掉一次，同时记录最小质因子。
void linear_sieve() {
    for (int v = 2; v <= n; v++) {
        if (min_prime[v] == 0) { // 没有更小的质因子，说明 v 是质数
            min_prime[v] = v;
            prime_cnt++;
            primes[prime_cnt] = v;
        }
        for (int i = 1; i <= prime_cnt; i++) {
            int p = primes[i];
            if (p > min_prime[v] || p > n / v) { // p * v > n 时停止
                break;
            }
            min_prime[p * v] = p;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n;

    linear_sieve();

    // 把 2..n 每个数分解质因数，指数累加得到 n! 的标准分解。
    for (int i = 2; i <= n; i++) {
        int x = i; // 用临时变量分解，不能改动外层循环变量 i
        while (x > 1) {
            int p = min_prime[x];
            while (x % p == 0) {
                x /= p;
                exp_of_prime[p]++;
            }
        }
    }

    // 答案 = d((n!)^2) = ∏ (2 * e_p + 1)，其中 e_p 是 p 在 n! 中的指数。
    ll answer = 1;
    for (int i = 1; i <= prime_cnt; i++) {
        int p = primes[i];
        answer = answer * (2 * exp_of_prime[p] + 1) % MOD;
    }

    std::cout << answer << "\n";
    return 0;
}

复杂度

• 时间：线性筛 $O(n)$，逐数分解总代价为 $\sum_{v \leqslant n} \omega(v)$（$\omega$ 是质因子个数），为 $O(n \log \log n)$ 级；合计 $O(n \log \log n)$，$n = 10^6$ 时 C++ 轻松通过，Python 实现也在数秒内完成。
• 空间：两个长度 $n$ 的整数数组，$O(n)$。
• 取模注意：指数 $e_p$ 本身不超过 $\sum \lfloor n/p^k \rfloor$ 量级（约 $2.5 \times 10^7$，即 $2e+1$ 很小），不需要对指数取模，只对乘积取模。

总结

• 核心变形：$\frac{1}{x} + \frac{1}{y} = \frac{1}{N} \iff (x-N)(y-N) = N^2$，其中 $N = n!$。
• 由 $x, y > N$ 知解与 $N^2$ 的有序因子对一一对应，答案 $= d\bigl((n!)^2\bigr) = \prod_{p \leqslant n} (2e_p + 1)$。
• 实现上只需线性筛最小质因子，把 $2..n$ 逐数分解累加指数，最后连乘 $(2 e_p + 1)$ 取模。
• 这道题的通用套路：“倒数和 = 1” 型方程计数 → 移项凑平方 → 约数个数 → 质因数分解（配合 Legendre / 线性筛）。