【例4.19】阶乘之和

GitHub跳转原题关系图返回列表

计算阶乘之和末尾6位,利用同余取模运算防溢出,并发现25的阶乘及以后末6位全为0从而实现常数级优化。

OJ: roj

题目 ID: 5035

难度:入门

标签:循环数学取模

创建: 2026-10-08 22:57

更新: 2026-10-08 22:57

形式化题目

给定一个正整数 nn(1≤n≤9999991 \le n \le 999999),计算下式的值:

S=∑i=1ni!S = \sum_{i=1}^{n} i!
输出 S mod 106S \bmod 10^6 的值。并且题目要求输出不含前导 0。

正解

思路

题目要求计算末 6 位,也就是对 10610^6 取模。因为阶乘的增长速度极快,如果直接计算阶乘会超出基本数据类型的表示范围,因此我们需要在每次计算阶乘和累加时,都进行对 10610^6 取模的操作。 取模的性质有:(a×b) mod m=((a mod m)×(b mod m)) mod m(a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m。

细节优化: 我们可以发现,i!i! 是由 1×2×3×⋯×i1 \times 2 \times 3 \times \dots \times i 相乘得到的。对于末 6 位的影响,可以看作因数中 2 和 5 的个数。 当 i≥25i \ge 25 时,i!i! 中含有的因数 5 的个数至少为 ⌊25/5⌋+⌊25/25⌋=5+1=6\lfloor 25/5 \rfloor + \lfloor 25/25 \rfloor = 5 + 1 = 6。同时它包含的因数 2 显然多于 6 个。 这就意味着,对于所有的 i≥25i \ge 25,i!i! 必定是 10610^6 的倍数,其对 10610^6 取模的结果恒为 0。 因此,当 n≥24n \ge 24 时,后续所有的阶乘都对末 6 位没有贡献,答案恒等于 n=24n=24 时的结果,即 940313。

同时需要注意,题目明确要求输出“不含前导 0”,所以即使结果像 n=10n=10 时末 6 位为 037913,也应该按普通数值格式输出 37913。使用普通的整数输出(例如 cout << sum)自然就不会带有前导零,而不要自作主张使用补零格式化(例如 printf("%06d"))。

代码

python
#!/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-10-08 22:48
# update_at: 2026-10-08 22:48

import sys
from itertools import accumulate, islice, takewhile

MOD = 10**6  # 末 6 位 = 对 10^6 取模


def solve() -> None:
    """读入 n,输出 1! + 2! + ... + n! 的末 6 位(不含前导 0)。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:  # 空输入:不输出,与 C++ 侧 `if (cin >> n)` 失败时一致
        return

    # accumulate 的 initial=1 是 0!,islice 丢掉它,剩下的依次是 1!, 2!, ..., n! 的末 6 位
    facs = islice(accumulate(range(1, n + 1), lambda f, i: f * i % MOD, initial=1), 1, None)
    # 25! 起必含因子 10^6,其后每一项都是 0,故在第一个 0 处就截断
    terms = takewhile(bool, facs)
    print(sum(terms) % MOD)


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-08 22:48
 * update_at: 2026-10-08 22:48
 */
// roj 5035《【例4.19】阶乘之和》(一本通 2033)
//
// 题意:输入 n(1 <= n <= 999999),求 S = 1! + 2! + ... + n! 的末 6 位,
//   输出不含前导 0。n=10 时 S = 4037913,末 6 位是 037913,应输出 37913。
//
// 做法:同余定理边算边取模,fac 存 i! mod 10^6,sum 存前 i 项和 mod 10^6:
//   (a*b) % m = ((a%m) * (b%m)) % m,(a+b) % m = ((a%m) + (b%m)) % m。
//   又因 25! 中因子 5 的个数为 6(5/10/15/20 各 1 个,25 含 2 个),因子 2 更多,
//   所以 10^6 | 25!,进而 i >= 25 时 i! ≡ 0 (mod 10^6),fac 一旦为 0 后面恒为 0。
// 输出:用普通整数输出(不含前导 0),绝不能用 %06lld 之类的补零格式。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000000; // 末 6 位 = 对 10^6 取模

ll n;   // 题面输入,上界 999999
ll sum; // 答案:1! + 2! + ... + n! 的末 6 位

// 递推求阶乘之和的末 6 位。i >= 25 后 fac 恒为 0,此后每项贡献为 0,可提前退出。
void solve() {
    ll fac = 1; // fac:当前 i! 的末 6 位
    for (ll i = 1; i <= n; i++) {
        fac = fac * i % MOD;
        if (fac == 0) {
            break; // i >= 25 起 fac 恒为 0,后续项不会改变答案
        }
        sum = (sum + fac) % MOD;
    }
}

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

    if (cin >> n) {
        solve();
        cout << sum << "\n"; // 普通整数输出,天然不含前导 0
    }

    return 0;
}

复杂度

  • 时间复杂度:最坏情况下循环体执行最多 25 次就会因为 fac == 0 而退出,因此时间复杂度为 O(min⁡(n,25))O(\min(n, 25)),等同于 O(1)O(1) 常数时间复杂度。
  • 空间复杂度:只需要几个变量存储中间状态,为 O(1)O(1)。

总结

  1. 同余取模:对大数求末 kk 位,等价于对 10k10^k 取模。在每一步运算(无论是加法还是乘法)都对 10610^6 进行取模,可以有效防止溢出。
  2. 输出不含前导 0:
    • 数据中暴露末 6 位 <100000< 100000 必须去前导 0 的点有 p1(n=1) 答案 1,p2(n=2) 答案 3,p3(n=10) 答案 37913。全值域共 9 个 nn 会暴露差异。
    • V1 反事实测试:若将输出改成 %06lld(补零),会导致 p1/p2/p3 失败,分别输出 000001/000003/037913。必须使用普通整数输出(如 cout << sum / %lld)即可满足“不含前导 0”。
  3. 答案从 n=24n = 24 起恒为 940313:
    • 25!25! 含 6 个因子 5(5/10/15/20 各含 1 个,25 含 2 个),所以 25!≡0(mod106)25! \equiv 0 \pmod{10^6}。这意味着当 i≥25i \ge 25 时 i!≡0i! \equiv 0。
    • 24! mod 106=360000≠024! \bmod 10^6 = 360000 \ne 0。S23=580313≠S24=940313=S25S_{23} = 580313 \ne S_{24} = 940313 = S_{25}。
    • 因此,阶乘之和从 n=24n = 24 开始恒定为 940313,不会差一。
  4. break 是性能优化而非正确性必需:
    • 即使删掉 break,10/10 的数据依然能够全对。在 n=999999n=999999 实测用时约为 0.01s。
    • sum += fac 放在 break 前后都正确,因为当 fac=0fac=0 加上去结果不变。
  5. 关于溢出与类型选择:
    • 走 break 路径时 fac * i 的实际最大值为 16640000(发生在 i=20i=20 时),而理论无 break 的上界约为 101210^{12}。
    • 尽管 int 类型(上限约 2.14×1092.14 \times 10^9)在本题的特定情形下恰好不溢出(因为乘积最大不到两千万),但按本仓库规范使用 long long 更加安全且无性能开销。
  6. 验证强度摘要:
    • 异源比对:三条路径(C++ / Python 不取模大整数计算 / 逐步取模实现)交叉验证 00 分歧;全值域 break 与不带 break 扫描也是 00 分歧;实现代码里的字面量没有硬编码任何一个答案。