计算前 n 个正整数乘积并对 1000000007 取模的正确实现方式

本文详解如何安全计算 n! mod 1000000007，避免中间结果溢出导致错误答案，核心是每次乘法后立即取模，并给出可落地的代码实现与关键注意事项。

本文详解如何安全计算 n! mod 1000000007，避免中间结果溢出导致错误答案，核心是每次乘法后立即取模，并给出可落地的代码实现与关键注意事项。

在编程竞赛或算法题中，常需计算阶乘对大质数（如 $10^9+7 = 1000000007$）取模的结果。直接使用 long ans = 1; for (int i = 1; i <= n; i++) ans *= i; return ans % MOD; 的写法看似简洁，但在 n 较大时（例如 $n > 20$），ans 会迅速超出 long（Java 中为 64 位有符号整数，最大值约 $9.2 times 10^{18}$）的表示范围，造成整数溢出——此时 ans 变为负数或错误值，后续取模毫无意义，最终返回错误结果。

✅ 正确做法是：在每次乘法运算后立即对模数取余，利用模运算的分配律：
$$(a times b) bmod p = big((a bmod p) times (b bmod p)big) bmod p$$
这能确保中间结果始终落在 $[0, p-1]$ 范围内，彻底规避溢出风险。

以下是推荐的实现（以 Java 为例，MOD = 1000000007）：

final long MOD = 1000000007L;public long factorialMod(int n) {    long ans = 1;    for (int i = 1; i <= n; i++) {        ans = (ans * i) % MOD;  // 关键：每一步都取模    }    return ans;}

⚠️ 注意事项：

• *不要写成 `ans = ans i % MOD而不加括号**：虽然%和优先级相同且左结合，但显式加括号(ans i) % MOD` 更清晰、不易出错；
• i 本身小于 MOD，因此 i % MOD 非必需，但若 i 可能超限（如从输入读取的大数），则应写作 (ans % MOD) * (i % MOD) % MOD；
• 使用 long 是必要的（int 最大约 $2.1 times 10^9$，远小于 MOD，无法承载乘积）；
• 当 n ≥ MOD 时，n! 必含因子 MOD，结果恒为 0（因 MOD 是质数），可提前剪枝优化，但一般题目中 n < MOD。

总结：模运算不是仅在最后执行的“装饰”，而是保障中间过程数值稳定的关键防御机制。牢记“边乘边模”，即可稳健应对大 n 场景，得到正确且高效的阶乘模结果。