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)，这是最易崩的用例
快速幂看着只有十来行，但溢出点、模处理时机、类型选择这三个地方，只要漏一个，结果就全错——而且往往还测不出来，因为小数据刚好蒙对。
