计算阶乘之和末尾6位,利用同余取模运算防溢出,并发现25的阶乘及以后末6位全为0从而实现常数级优化。
OJ: roj
题目 ID: 5035
难度:入门
标签:循环数学取模
创建: 2026-10-08 22:57
更新: 2026-10-08 22:57
形式化题目
给定一个正整数
正解
思路
题目要求计算末 6 位,也就是对
细节优化:
我们可以发现,940313。
同时需要注意,题目明确要求输出“不含前导 0”,所以即使结果像 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而退出,因此时间复杂度为,等同于 常数时间复杂度。 - 空间复杂度:只需要几个变量存储中间状态,为
。
总结
- 同余取模:对大数求末
位,等价于对 取模。在每一步运算(无论是加法还是乘法)都对 进行取模,可以有效防止溢出。 - 输出不含前导 0:
- 数据中暴露末 6 位
必须去前导 0 的点有 p1(n=1)答案 1,p2(n=2)答案 3,p3(n=10)答案 37913。全值域共 9 个会暴露差异。 - V1 反事实测试:若将输出改成
%06lld(补零),会导致p1/p2/p3失败,分别输出000001/000003/037913。必须使用普通整数输出(如cout << sum/%lld)即可满足“不含前导 0”。
- 数据中暴露末 6 位
- 答案从
起恒为 940313:含 6 个因子 5(5/10/15/20 各含 1 个,25 含 2 个),所以 。这意味着当 时 。 。 。 - 因此,阶乘之和从
开始恒定为 940313,不会差一。
break是性能优化而非正确性必需:- 即使删掉
break,10/10 的数据依然能够全对。在实测用时约为 0.01s。 sum += fac放在break前后都正确,因为当加上去结果不变。
- 即使删掉
- 关于溢出与类型选择:
- 走
break路径时fac * i的实际最大值为 16640000(发生在时),而理论无 break的上界约为。 - 尽管
int类型(上限约)在本题的特定情形下恰好不溢出(因为乘积最大不到两千万),但按本仓库规范使用 long long更加安全且无性能开销。
- 走
- 验证强度摘要:
- 异源比对:三条路径(C++ / Python 不取模大整数计算 / 逐步取模实现)交叉验证
分歧;全值域 break与不带break扫描也是分歧;实现代码里的字面量没有硬编码任何一个答案。
- 异源比对:三条路径(C++ / Python 不取模大整数计算 / 逐步取模实现)交叉验证