C++怎么实现快速幂算法_C++模幂运算优化【数学】

pow()不能用于大数模幂，因其为浮点运算、精度丢失、不支持取模、易溢出且时间复杂度为o(b)；应手写迭代快速幂，注意base取模、防乘法溢出、位运算判断奇偶。

为什么 pow() 不能直接用于大数模幂

因为标准库的 std::pow() 是浮点运算，精度丢失严重，且不支持取模；对大整数（比如 10^9+7 下的 a^b）会立即溢出或返回 inf。它根本不是为模幂设计的。

• 输入是 double，中间结果无法精确表示大整数
• 没有内置取模逻辑，你没法在每一步截断数值
• 时间复杂度是线性的（O(b)），而快速幂要的是 O(log b)

手写快速幂：核心循环怎么写才不出错

关键不是递归，而是迭代——避免栈溢出，也更容易控制模运算时机。每次把指数右移，底数平方，只在当前位为 1 时乘进结果。

long long mod_pow(long long base, long long exp, long long mod) {     long long res = 1;     base %= mod;  // 先取模，防 base >= mod     while (exp > 0) {         if (exp & 1) res = (__int128)res * base % mod;  // 防乘法溢出         base = (__int128)base * base % mod;         exp >>= 1;     }     return res; }

• base %= mod 必须做，否则第一次平方就可能溢出
• 用 (__int128) 强转是 GCC/Clang 常见方案，避免 long long * long long 溢出；若编译器不支持，得手写乘法取模（如倍增加法）
• 别用 exp % 2 == 1，exp & 1 更快且语义更准

当 mod 不是质数时，还能用快速幂吗

能。快速幂本身和模数是否为质数完全无关——它只是个计算 a^b % m 的算法，不依赖费马小定理或逆元。唯一要求是 m > 0 且所有中间乘法可被正确截断。

• 欧拉定理（a^φ(m) ≡ 1 (mod m)）才需要 gcd(a,m)==1，但那是用来降幂的，不是快速幂本身
• 如果 a 和 m 不互质，mod_pow(a, b, m) 依然正确，只是无法用 φ(m) 简化指数
• 注意：若 m == 1，结果恒为 0，建议提前判断

常见报错：runtime Error: signed Integer overflow

这几乎一定发生在 base * base 或 res * base 这两处。64 位 long long 最大约是 9e18，而两个 1e9 级数字相乘就超了。

立即学习“C++免费学习笔记（深入）”；

• 别信“我模数是 1e9+7，所以值不会大”——中间乘积远大于模数
• __int128 不是标准 c++，MSVC 不支持；跨平台项目需 fallback 到龟速乘（binary multiplication）
• 测试时务必覆盖边界：如 mod_pow(1000000000, 1000000000, 1000000007)，这是最易崩的用例

快速幂看着只有十来行，但溢出点、模处理时机、类型选择这三个地方，只要漏一个，结果就全错——而且往往还测不出来，因为小数据刚好蒙对。