C++如何进行大整数模幂运算？（快速幂算法）

std::pow不能用于大整数模幂，因其返回double导致2⁵³后精度丢失；而模幂需每步取模防溢出，须手写迭代快速幂，配合__int128或mul_mod保证中间乘法不溢出。

为什么 std::pow 不能直接算大整数模幂

因为 std::pow 返回 double，精度在 2⁵³ 之后就丢失了；而大整数模幂（比如 RSA 中的 a^b mod m）要求每一步都严格取模，防止中间结果溢出。用 long long 直接乘再取模也撑不住：两个 10⁹ 级数字相乘就超 LLONG_MAX 了。

所以必须手写快速幂，且每轮乘法后立刻模 m。

• 核心原则：(a * b) % m == ((a % m) * (b % m)) % m，允许把大数拆进模运算里
• 避免用递归实现——栈深可能达 64 层（64 位指数），虽不炸但没必要
• 注意 m == 1 时结果恒为 0，提前返回，否则 base % 1 在某些编译器下行为未定义

手写迭代版快速幂（c++17，支持 long long）

迭代比递归更稳，空间 O(1)，且方便加防溢出乘法。下面这个版本能处理 base、exp、mod 全在 [0, 1e18) 范围内的情况：

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

• __int128 是 GCC/Clang 扩展，不是标准 C++，但对 long long 模幂足够可靠；若需跨平台，得自己写 mul_mod 拆位乘法
• 别漏掉第一行 base %= mod——否则 base >= mod 时初始平方就溢出
• 指数为 0 时返回 1（数学定义），但若 mod == 1，仍得返回 0，优先级更高

遇到 mod 超过 long long 怎么办

如果模数本身超过 2⁶³−1（比如用 __int128 当模），那连 __int128 都不够存平方结果。这时必须换算法：

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

• 用 unsigned long long + 二分乘法（mul_mod）替代直接乘，时间多一次 log，但安全
• 或者改用 boost::multiprecision::cpp_int，但会显著拖慢，只适合调试或极低频调用
• 注意：标准库无任意精度整数，别指望 <numbers></numbers> 或 <bit></bit> 能帮忙

简单 mul_mod 示例（仅当 a, b, mod 时可用）：

long long mul_mod(long long a, long long b, long long mod) {     long long res = 0;     a %= mod; b %= mod;     while (b > 0) {         if (b & 1) res = (res + a) % mod;         a = (a << 1) % mod;         b >>= 1;     }     return res; }

常见报错和静默错误

这类函数最容易“算得出来但结果错”，因为没触发崩溃，只因溢出或符号问题悄悄变负：

• 输入负的 base：C++ 中 -5 % 3 == -2，不是 1，要先做 ((base % mod) + mod) % mod
• 用 int 存指数，结果 1 溢出成负数，循环不退出——务必用 <code>long long 或 unsigned
• 忘记检查 mod == 0：除零未定义行为，运行时可能 SIGFPE，但不总触发
• 在竞赛环境（如 Codeforces）中开 -O2 时，某些手写 mul_mod 可能被误优化，加 volatile 或 asm volatile("" ::: "r0") 干扰优化器（小众但真实）

最麻烦的其实是模数为合数且与底数不互质时的数学边界——这时候快速幂本身没错，但你依赖的欧拉定理降幂就不适用了。别想省事套公式，老老实实按题意走迭代。