最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
计算前 n 个正整数乘积对 1000000007 取模的正确实现方法
时间：2026-07-12 09:16:52 编辑：袖梨 来源：一聚教程网
在计算大数阶乘（如 n!）并对大质数（如 10⁹+7）取模时，若不及时取模会导致中间结果溢出 long 类型范围，从而产生错误答案；正确做法是在每次乘法后立即取模。
在计算前 n 个正整数乘积（即 n!）并对 1000000007（常记为 mod = 10⁹+7）取模时，若仅在最终结果处取模，中间乘积极易超出 `long` 类型的表示范围（java 中 `long` 最大约为 9.2×10¹⁸），导致整数溢出和错误结果。例如当 n ≥ 21 时，21! ≈ 5.1×10²⁰，已远超 `long` 容量，此时 `ans * i` 会发生静默溢出，后续计算完全失真。
为避免溢出，核心原则是：每一步乘法后立即对 MOD 取模。根据模运算性质 (a × b) % MOD == ((a % MOD) × (b % MOD)) % MOD，我们可在循环中持续维护 ans 始终处于 [0, MOD) 范围内：
final long MOD = 1000000007L;long ans = 1;for (int i = 1; i <= n; i++) { ans = (ans * i) % MOD;}return ans;
⚠️ 注意事项：
- 循环起始应为 i = 1（而非 i = 0），否则第一次乘 0 将使结果恒为 0；
- MOD 必须声明为 long 类型（加 L 后缀），防止整型字面量溢出；
- 不必额外写 ((ans % MOD) * (i % MOD)) % MOD——因为 i < MOD（n 通常远小于 10⁹+7），且 ans 已被上一轮取模约束在 [0, MOD) 内，直接 (ans * i) % MOD 即安全高效；
- 若 n ≥ MOD，则 n! % MOD == 0（因阶乘包含因子 MOD），可提前判断优化，但常规题目中 n 一般远小于 MOD。
该方法时间复杂度 O(n)，空间复杂度 O(1)，是计算大阶乘取模的标准实践，兼顾正确性、效率与代码简洁性。
相关文章
- 龙岛异兽起源神秘图腾解锁方式-龙岛异兽起源神秘图腾解锁方法 07-20
- 苍蓝前线格奈森瑙强度如何-苍蓝前线格奈森瑙强度怎样 07-20
- 出发吧麦芬学者风暴之主养成攻略 07-20
- 英雄冒险团全部传家宝获取方法汇总 07-20
- 王者万象棋新手入门指引 王者万象棋零基础快速上手教程 07-20
- 检疫区最后一站金色收集品怎么获得 隐藏收集品获得方法介绍 07-20