user

1
2
3
4
5
6
7
8
9
10
11
二项式系数质因数分解

二项式系数C(10,3) = 120。
120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5，而2 + 2 + 2 + 3 + 5 = 14。
因此C(10,3)质因数分解后各项的和为14。

求C(20000000,15000000)质因数分解后各项的和。

我的思路:组合数能被表达为阶乘,对阶乘质因数分解,用一个欧拉筛筛出质数用于质因数分解,然后记录每个质数的出现次数即可.

请给我c++代码实现.

gpt

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
你的思路是**完全正确的，而且是正解思路** 👍
这个问题的关键在于：**不能真的算组合数，也不能真的分解阶乘**，而是要用**勒让德公式（Legendre formula）统计每个质数在阶乘中的指数**。

---

## 一、数学思路整理（与你的思路对齐）

[
C(n,k) = \frac{n!}{k!(n-k)!}
]

对任意质数 (p)，它在 (n!) 中的指数为：

[
e_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor
]

那么在组合数中的指数就是：

[
e_p(C(n,k)) = e_p(n!) - e_p(k!) - e_p((n-k)!)
]

而题目要求的是：

> **质因数分解后所有因子的和（带重数）**

也就是：

[
\sum_{p \text{ prime}} p \times e_p(C(n,k))
]

---

## 二、算法步骤

1. 用 **欧拉筛** 或普通筛法筛出 **所有 ≤ n 的质数**
2. 对每个质数 (p)

   * 用勒让德公式计算
     (e_p(n!))、(e_p(k!))、(e_p((n-k)!))
   * 得到 (e_p(C(n,k)))
3. 累加 `p * 指数`
4. 输出结果

---

## 三、复杂度分析

* 筛质数：
  [
  O(n)
  ]
* 每个质数计算指数：
  [
  O(\log_p n)
  ]
* 总复杂度：
  [
  O(n)
  ]

对于 `n = 2e7` 是**完全可行的**（内存约 80MB 以内）

---

## 四、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
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

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

    const int N = 20000000;
    const int K = 15000000;
    const int NK = N - K;

    // 欧拉筛
    vector<int> primes;
    vector<bool> is_composite(N + 1, false);

    for (int i = 2; i <= N; ++i) {
        if (!is_composite[i]) primes.push_back(i);
        for (int p : primes) {
            if ((int64)i * p > N) break;
            is_composite[i * p] = true;
            if (i % p == 0) break;
        }
    }

    auto count_exp = [&](int n, int p) {
        int64 cnt = 0;
        while (n) {
            n /= p;
            cnt += n;
        }
        return cnt;
    };

    int64 answer = 0;

    for (int p : primes) {
        int64 e =
            count_exp(N, p)
          - count_exp(K, p)
          - count_exp(NK, p);

        if (e > 0) {
            answer += (int64)p * e;
        }
    }

    cout << answer << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
---

## 五、一些容易踩的坑

✅ **不能用 `int` 存结果** → 必须 `int64`
✅ **不能真的算阶乘** → 数字会爆
✅ **不能试除分解组合数本身** → 不可能完成
✅ **必须用勒让德公式**

---

## 六、总结一句话

> **这是一个“组合数 × 质因数 × 勒让德公式”的经典大数题，本质是统计指数而不是算值。**

如果你愿意，我也可以帮你：

* 优化到更低内存版本
* 改成分块筛
* 或解释为什么这题不需要 Lucas / Kummer 定理

随时继续 👍