“输入一个整数n计算1!2!3!…n!。”——这句话我第一次看到时觉得出题人有点敷衍两层循环的事三分钟能写完。后来带人做练习才发现这道题其实是个分水岭有人五分钟交卷还嫌不够有人盯着 n20 的测试点上一个负数结果发呆半小时。它表面考的是循环实际上把递推思维、数据类型边界、大数处理、复杂度估算这几件事一次性串起来了。这篇内容适合三类人刚学完循环和数组、想找个能打通知识点的练手题的初学者准备笔试面试、需要把这类“看起来简单”的题讲清楚的人以及写业务代码时偶尔要算阶乘和、结果发现数字莫名其妙的开发者。我会从最笨的写法讲起一路说到高精度和取模变体中间所有边界值都给出具体数字你可以直接拿去验证。1. 递推骨架把两重循环压成一趟1.1 先看大多数人第一反应写出来的东西刚接触循环的人几乎都会写成这样long long sum 0; for (int i 1; i n; i) { long long fact 1; for (int j 1; j i; j) { fact * j; // 从 1 乘到 i } sum fact; }逻辑没毛病结果也对在小 n 范围内。问题在于重复劳动算i10的时候你把 1 到 10 乘了一遍算i11的时候又从 1 开始乘了一遍前 10 次乘法完全白做。总的乘法次数是12...n n(n1)/2n1000 就是五十万次乘法。而这件事本来只需要一千次。我见过有人辩解“反正电脑快。”在 n 只有几十的时候确实无所谓但这道题的题眼恰恰不在这里而在于你有没有看出相邻两项之间的关系。1.2 相邻两项只差一个因子把每一项写开看1! 1 2! 1 × 2 3! 1 × 2 × 3 4! 1 × 2 × 3 × 4i!和(i-1)!之间只差乘上最后一个因子i。也就是说如果你已经知道了(i-1)!那i!只需要一次乘法而不是 i 次。把这个观察落成代码就是维护两个滚动变量def factorial_sum(n): fact 1 # 滚动保存 i! total 0 # 滚动保存 1!...i! for i in range(1, n 1): fact * i # 由 (i-1)! 推出 i! total fact # 累加进总和 return total一遍循环n 次乘法、n 次加法。fact这个变量是整道题的灵魂它同时承担了“当前阶乘值”和“下一项的原料”两个角色。写熟练之后你会发现凡是形如“求 f(1)f(2)...f(n) 且 f(i) 能由 f(i-1) 常数时间推出”的题都是这个套路——斐波那契前缀和、等比数列求和、某些动态规划的滚动数组优化本质上是同一个东西。1.3 手工跑一遍 n5把中间状态列出来这一步很多人跳过但它决定了你调试时的效率。把每一轮的两个变量列成表轮次 ifact也就是 i!total前 i 项和111223369424335120153有了这张表一旦程序输出不对你可以立刻判断是fact出问题还是total出问题如果fact在第 3 轮就变成 7那是乘法逻辑写错了如果fact全对但total整体大 1那多半是初始值写成了 1 而不是 0。这种“先在小数据上对表”的习惯比盯着代码看十分钟有用得多。顺手记一个有意思的观察1!2!3!4! 33而5! 120之后每一项都含有因子 10末位必然是 0。所以只要 n ≥ 41!2!...n!的个位数就永远是 3。这个结论在后面讲变体题型时会再用到。2. 数值边界才是真正的门槛初学者在这道题上翻车九成不是因为算法而是因为数字太大装不下。这一节我把各种类型的具体边界算给你看。2.1 32 位有符号整数n13 开始就不可信int的上限是2147483647大约 21 亿。12! 479001600还在范围内13! 6227020800已经超过上限。再看累加和1!...12! 522956313安全加上13!之后变成6749977113同样越界。所以用int存结果n ≥ 13 就会得到错误答案而且 C/C 里这种溢出是静默的不会报错结果会回绕成负数。我见过不少人拿到负号结果第一反应是“循环写错了”其实是类型选错了。2.2 64 位整数能撑到 n20换成long longint64上限约9.22 × 10^18。20! 24329020081766400001!2!...20! 2561327494111820313仍然在上限之内21! 51090942171709440000约5.1 × 10^19已经超了。所以 64 位整数的安全边界是n ≤ 20。这个数字建议直接记住因为它是很多在线评测题目的默认分界线题目如果写明“n ≤ 20”就是在暗示你用long long就够如果写“n ≤ 30”或者更大那就必须上大整数。2.3 JavaScript 的 2^53 暗礁用 JS 写这道题的人最容易吃亏。Number是双精度浮点能精确表示整数的上限是2^53 - 1 9007199254740991约 9 × 10^15比int64小了三个数量级。1!2!...18! 6780385526348313还在安全整数范围内到n19和变成128425485935180313已经超出安全范围结果开始丢精度。最要命的是JS 不会报错也不會提示它的输出看起来还是一个大整数只是末几位悄悄错了。这种“静默错误”比 C 里的负数溢出更难排查因为你没法靠肉眼判断对错。写 JS 遇到阶乘类问题我的建议是只要 n 可能超过 18无脑上BigInt。语言 / 类型精确计算的最大 n越界后的表现Cint/int3212回绕成负数Clong long/int6420回绕成负数Javalong20回绕成负数JSNumber18静默丢精度末位出错Pythonint仅受内存限制不会溢出JavaBigInteger仅受内存限制不会溢出提示不要死记这张表自己写个小循环从 n1 往上加每轮检查结果是否变成负数或明显变小跑一次就知道边界在哪了。这种做法比背表格可靠也顺带练了验证习惯。3. 四种语言的落地写法与取舍3.1 C / Clong long打底必要时手写高精度标准写法没什么花头#include stdio.h int main(void) { int n; if (scanf(%d, n) ! 1) return 0; long long fact 1, total 0; for (int i 1; i n; i) { fact * i; total fact; } printf(%lld\n, total); return 0; }两个细节值得强调。第一输出long long必须用%lld用%d只会打印低 32 位结果会变成一个莫名其妙的数。第二total一定初始化为 0我见过太多人写成 1然后所有答案整体大 1还反复检查循环条件。如果 n 超过 20GCC / Clang 提供的unsigned __int128可以救个急它能到 34 左右但具体边界我不建议背实际跑一遍确认更稳妥。再往上就必须自己写高精度了。高精度的思路不复杂用一个数组按 1e9 为一块存十进制数俗称“压 9 位”每轮做一次“大数 × 小整数”和一次“大数 大数”。因为乘的是i这种不超过几万的小整数普通 O(位数) 乘法就够用不上复杂的快速乘法。#include vector using namespace std; const int BASE 1000000000; // 每块存 9 位十进制 // a a * mm 是小整数 void mulSmall(vectorint a, int m) { long long carry 0; for (size_t i 0; i a.size(); i) { long long cur (long long)a[i] * m carry; a[i] (int)(cur % BASE); carry cur / BASE; } while (carry) { a.push_back((int)(carry % BASE)); carry / BASE; } } // acc a void addTo(vectorint acc, const vectorint a) { int carry 0; if (acc.size() a.size()) acc.resize(a.size(), 0); for (size_t i 0; i a.size() || carry; i) { if (i acc.size()) acc.push_back(0); long long cur acc[i] (i a.size() ? a[i] : 0) carry; acc[i] (int)(cur % BASE); carry (int)(cur / BASE); } }输出的时候注意最高位不能补零其余每块要补满 9 位这里是最容易出格式错误的地方。3.2 Python三种写法性能差一个数量级Python 的整数天然支持任意精度所以这道题在 Python 里没有溢出问题区别只在于快慢。常见的三种写法import math # 写法一递推推荐 def s1(n): f t 0 f 1 for i in range(1, n 1): f * i t f return t # 写法二每项单独算 def s2(n): return sum(math.factorial(i) for i in range(1, n 1)) # 写法三reduce 累积 from functools import reduce def s3(n): facts reduce(lambda acc, i: acc [acc[-1] * i], range(1, n 1), [1]) return sum(facts[1:])写法二看起来最简洁但它每一项都从头乘一遍是 O(n²) 次大数乘法写法一是 O(n) 次。n 小的时候感觉不出来n 上到几千差距会拉到一个数量级以上。写法三额外申请了一个列表存所有中间阶乘空间换来的好处几乎为零我一般不用。提示Python 里range(1, n 1)和range(n)差一项这件事坑过太多人。判断方法很简单n1 的时候正确答案是 1如果你的程序输出 0那肯定是范围写错了。3.3 Javalong与BigInteger的分界很清楚n ≤ 20 用longlong fact 1, total 0; for (int i 1; i n; i) { fact * i; total fact; } System.out.println(total);超过 20 就必须换BigIntegerimport java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); BigInteger fact BigInteger.ONE; BigInteger total BigInteger.ZERO; for (int i 1; i n; i) { fact fact.multiply(BigInteger.valueOf(i)); total total.add(fact); } System.out.println(total); } }BigInteger是不可变对象每次multiply都会产生一个新实例。n 上千的时候会产生大量临时对象给垃圾回收带来压力。做算法题无所谓但如果这段逻辑要放进高频调用的业务代码里最好先测一下吞吐或者考虑用数组手写。3.4 JavaScriptBigInt的代价与坑function factorialSum(n) { let fact 1n; let total 0n; const N BigInt(n); for (let i 1n; i N; i) { fact * i; total fact; } return total; // 输出时记得 .toString() }两个必须注意的点第一BigInt和Number不能混合运算fact * i里如果i是普通数字会直接抛TypeError所以循环变量也得写成1n第二BigInt的运算比Number慢不少小 n 场景没必要用n 需要精确到 19 以上再切过去。4. 复杂度没那么简单大数乘法不是常数时间4.1 表面 O(n)实际是位数在拖后腿说递推解法是 O(n) 时间、O(1) 空间这话只在“每个数字都是机器字长”的前提下成立。一旦结果变成几百上千位的大数乘法开销就跟位数挂钩了。i!的十进制位数可以用斯特林公式估位数(i!) ≈ floor(log10(2πi)/2 i · log10(i/e)) 1套进去算几个值100!有 158 位1000!有 2568 位10000!有 35660 位。也就是说越往后每一轮乘法的位数越多整个过程的代价更接近 O(n² log n) 这个量级以“位运算”为单位而不是干净的线性。这一点在做性能预估时很关键。有人看到“一遍循环”就拍胸脯说“n 开到 10^6 也没问题”实际上大数一膨胀n 到几万就已经明显卡了。4.2 实测数据与优化方向在普通笔记本上跑 Python 的递推写法大致是这样不同机器会有出入量级可参考n结果位数耗时量级100159 位亚毫秒10002569 位几毫秒1000035661 位数百毫秒注意结果位数比n!的位数多一位因为前缀和略大于n!。这个表里最有价值的信息是增长曲线n 涨 10 倍耗时涨得比 10 倍多一些多出来的部分就是大数乘法变贵的贡献。优化方向主要有两个。一是数学上的如果你只是要末几位或者取模结果直接用取模版本不需要大数见第 6 节。二是工程上的把连续的几项合并计算或者用更高效的大数库比如 GMP但对手写题来说通常没必要。提示不要凭感觉说“O(n) 所以很快”。写算法的人最常犯的错误就是忽略常数和大数代价。真要做性能判断拿秒表跑三个不同量级的数据比空想靠谱。5. 边界条件与我自己踩过的坑5.1 n0、n1 和负数怎么处理n 0数学上这是个空和约定结果是 0。很多评测数据里会塞一个 0 来测你的初始值如果total初始化成 1这里立刻暴露。n 1结果是 1。n 0整数阶乘没有定义。做算法题通常约定返回 0 或者直接不出现写业务代码我倾向于抛异常因为静默返回 0 会把错误藏起来等到线上出问题更难查。这三条建议在函数开头就写清楚别指望调用方替你保证。5.2 多组输入的正确读法很多题目是“先给一个 T然后 T 行每行一个 n”也有人出成“读到文件结束”。C 里分别是int T; scanf(%d, T); while (T--) { int n; scanf(%d, n); // 处理 }int n; while (scanf(%d, n) 1) { // 处理 }Python 对应的是先int(input())然后循环读。多组数据最容易犯的错是把fact和total定义在循环外面第二组数据带着第一组的残留值继续算。变量一定要在每组数据内部重新初始化。5.3 几个具体的踩坑记录坑一递归写法看起来优雅实际很坑。有人会写f(n) f(n-1) factorial(n)这种递归问题有两个一是每次factorial(n)都从头算退化成 O(n²)二是递归深度到一千左右 Python 就抛RecursionError默认上限 1000。这道题用迭代是明显更优的选择除非你加了记忆化并且真的需要递归结构。坑二输出格式。高精度输出时最高位不能补零低位必须补满。我因为这块格式错误被评测机拒过好几次明明数值对就是不给过。写个print辅助函数把内部表示统一转换一次比到处手写输出逻辑可靠。坑三total和fact都用int声明。结果在小数据上看着对n 一到 13 就错。我在代码审查里见过好几次问作者为什么不用long long回答是“题目说 n 不超过 100我想着能省点内存”。省下来的几个字节换来的是隐蔽的溢出完全不值。6. 变体题型取模、末位和面试追问原题是最基础的形态实际遇到的往往是它的变种。6.1 取模版本写法几乎不变但有个陷阱题目改成形如“求(1!2!...n!) mod 1000000007”代码只需要在每次运算后取模const long long MOD 1000000007LL; long long fact 1, total 0; for (int i 1; i n; i) { fact fact * i % MOD; total (total fact) % MOD; }这样子是正确的因为加法和乘法对取模都满足分配律。但有个陷阱当 n 大于等于模数时i!里含有因子 MODfact会变成 0而且之后每一轮都是 0total就不再增长。用1e97这种大模数时 n 通常远小于它不会触发但如果题目用的是100000之类的小模数而 n 又允许开到很大就必须意识到这个现象题目往往就是冲着这个规律设计的。6.2 末位非零数字这类变体“求1!2!...n!的最后一位非零数字”是个经典难题。因为阶乘末尾的零来自因子 10 2 × 5而因子 2 的数量远多于 5所以关键是把每项里的因子 5 全部剥离同时记录消耗掉的 2 的个数最后再用剩余的 2 补回去。做前缀和的时候还要保证各项剥离后在同一“2 的幂次基准”上才能相加实现起来比分模版本复杂得多属于另一个难度层级。6.3 面试里常见的三个追问追问一为什么 n ≥ 4 时这个和的个位数永远是 3前面提过1!2!3!4! 33而从5!开始每一项都能被 10 整除个位贡献全是 0所以整个和的个位就等于 33 的个位也就是 3。这个观察题考的不是计算能力是你有没有注意到结构。追问二如果 n 是 10^9怎么处理大数版本肯定跑不动只能走取模路线。而且如果模数不大n! mod m在 n 超过某个阈值后会恒为 0此时总和会稳定在一个定值上可以直接算出来不需要真的循环 10^9 次。能不能想到这一步是区分“会写题”和“会分析”的分界线。追问三能不能只用一次循环、不用数组可以就是本文的递推写法。如果你回答的是双层循环面试官通常会再追一句“能不能优化”这时候把滚动变量讲清楚就够了。我自己在实际带新人的过程中发现这道题最大的价值不在答案本身而在于它逼着你去想三件事相邻项之间有没有关系、数据装不装得下、边界情况有没有覆盖。这三件事想明白了后面遇到更复杂的数列求和、动态规划前缀和思路基本是通的。至于代码本身写熟了就是十几行真正花时间的是前面那些判断。