根本原因是ab中间乘法会溢出long long，即使每步取模也无法避免；例如base接近1e18时，basebase达1e36，远超llong_max（约9e18），导致结果错误。
快速幂里乘法溢出的根本原因是什么
不是指数大，而是 a * b 这一步本身就会爆 long long。比如模数 mod 是 1e18 量级，底数 base 经过几次平方后可能接近 1e18，再自乘一次就是 1e36 ——远超 LLONG_MAX（约 9e18）。这时候哪怕每步都写 % mod，乘法中间结果已经溢出变负或截断，取模就完全错误。
用 __int128 替代普通乘法最直接
GCC/Clang 支持 __int128，能容纳两个 long long 相乘的结果（最大约 1e38），足够覆盖绝大多数竞赛和工程场景。关键点是：只在乘法临时计算时用它，不用于存储或返回。
-
res = (__int128)res * base % mod—— 先升到 128 位再模，安全 -
base = (__int128)base * base % mod—— 同理，平方也得防 - 必须确保编译器支持：加
-std=c++17并确认是 GCC/Clang；MSVC 不支持，不能无脑抄 - 别把
__int128当返回类型或函数参数传——标准库、STL、IO 都不认它
没有 __int128 时必须手写 mul_mod
本质是把乘法拆成“加法 + 位运算”，类似快速幂逻辑：把 b 看作二进制，每次判断最低位是否为 1，是则累加当前的 a，然后 a （即 <code>a *= 2），同时每步都 % mod。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 初始
res = 0，a %= mod，b %= mod（先归一化） - 循环中：若
b & 1，则res = (res + a) % mod - 然后
a = (a ，<code>b >>= 1 - 注意：
a 可能溢出，所以必须写成 <code>(a + a) % mod或显式% mod
哪些地方最容易漏掉防溢出
三个典型位置，错一个就 WA：
- 没做
base %= mod就开始循环——如果base原本大于mod，第一次平方就失控 - 指数为 0 时直接返回 1，但没考虑
mod == 1的情况——此时应返回0，否则错 - 负数底数没归一化：
base = (base % mod + mod) % mod缺失，导致后续所有平方和乘法符号混乱
真正难的不是写对逻辑，而是每一步都意识到：模运算保的是最终结果，不是中间值；而中间值一旦溢出，模就毫无意义。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
