不能直接用pow()计算大数模幂，因为pow(a,b)先算a^b再取模，中间结果会溢出；必须用快速幂配合模乘（__int128中转或龟速乘），每步边乘边模，且需预处理base%=mod、exp非负。
为什么不能直接用 pow() 计算大数模幂
因为 pow(a, b) 先算完整个 a^b，再取模，而大数（比如 1024 位）的幂结果会远超 unsigned long long 范围，直接溢出或触发未定义行为。哪怕你用 __int128 或 boost::multiprecision，中间结果依然爆炸式增长，内存和时间都扛不住。
真正可行的路只有一条：边乘边模，把指数拆成二进制位，每次只维护一个不超过模数的中间值。
- 核心是「快速幂 + 模约简」合并为一步，每轮都做
(result * base) % mod - 必须用
long long或更大整型做中间乘法，但要防乘法溢出 —— 所以不能直接写a * b % mod，得用「模乘」函数 - 如果
mod接近2^63，a * b即使是两个long long相乘也会溢出，此时需用__int128中转，或手写龟速乘（加法模拟乘法）
如何安全实现模乘（避免 a * b % mod 溢出）
当 a 和 b 都接近 mod，且 mod 在 1e18 量级时，a * b 必超 2^64。GCC 支持 __int128，可临时兜底：
long long mul_mod(long long a, long long b, long long mod) {
return (__int128)a * b % mod;
}
但注意：__int128 不是标准 C++，MSVC 不支持；若需跨平台，改用龟速乘（log 时间）：
long long mul_mod(long long a, long long b, long long mod) {
long long res = 0;
a %= mod; b %= mod;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (a >= 1;
}
return res;
}
- 龟速乘本质是把乘法转为加法+位移，每步都取模，不依赖大整型
- 比
__int128版慢约 3–5 倍，但 1000 次以内模幂基本无感 - 务必先
a %= mod、b %= mod，否则左移可能越界
完整模幂函数（mod_pow）怎么写才可靠
把模乘封装好后，快速幂逻辑就干净了：初始化 res = 1，遍历指数 b 的二进制位，对每个为 1 的位，累乘当前底数幂次；底数每次自乘并模约简。
long long mod_pow(long long base, long long exp, long long mod) {
if (mod == 1) return 0; // 任何数 mod 1 都是 0
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) res = mul_mod(res, base, mod);
base = mul_mod(base, base, mod);
exp >>= 1;
}
return res;
}
-
base %= mod必须做，防止初始 base 就超模 - 指数为 0 时返回 1（符合数学定义），但注意
mod == 1是特例，单独处理 - 所有乘法都走
mul_mod，不裸写* - 输入
exp应为非负；若需支持负指数，得先求模逆元（仅当gcd(base, mod) == 1时可行）
遇到 mod 是合数或非质数时要注意什么
上面的 mod_pow 本身不要求 mod 是质数 —— 它只是算 base^exp % mod，无论 mod 是多少都能算。但如果你后续想用费马小定理优化（比如把指数模 mod-1），那就必须确认 mod 是质数且 base 不被 mod 整除。
- 常见误操作：看到
mod = 1e9+7就以为所有模幂都能缩指数，其实缩的是φ(mod)（欧拉函数），不是mod-1 -
mod = 1e9+7是质数，所以φ(mod) = mod - 1；但mod = 1e9+9也是质数，而mod = 1e9+8是合数，φ(1e9+8)得分解质因数再算 - 除非你明确在做数论推导，否则别碰指数缩简 —— 直接传原始
exp给mod_pow最稳妥
最易被忽略的一点：模乘函数里用 while (b) 还是 while (b > 0) —— 如果 b 是 unsigned 类型，前者更安全；但若 b 可能为负（比如没检查输入），龟速乘会陷入死循环。生产代码里，指数类型建议用 unsigned long long，并在入口断言非负。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
