C++快速幂函数qpow计算2^^b mod 100000出错问题排查

问题现象 #

用快速幂函数qpow计算2的b次幂（b>400）并对100000取模时，函数返回-83648后持续输出0；而用简单循环实现的qpow2能得到正确结果。

核心原因：int类型溢出 #

C++中int的最大值通常是2147483647（即INT_MAX），在qpow函数的a *= a步骤中，当a增长到一定程度时，乘积会超出int的范围，触发有符号整数溢出：

• 比如当a=65536（2^16）时，a*a=4294967296，远大于INT_MAX，溢出后a会变成负数（补码机制下的溢出结果）。
• 后续对负数取模100000，结果依然是负数，再经过几次迭代后，a和x会逐步变成0，导致最终输出全为0。

而qpow2每次只执行x *= 2，且每次运算后立即取模100000，x的最大值为99999*2=199998，远小于INT_MAX，不会触发溢出，因此结果正确。

修复方案 #

将qpow中的变量x和a的类型从int改为long long，利用long long更大的数值范围（最大值为9223372036854775807）容纳中间计算结果，避免溢出：

long long qpow(int n) {
    long long x = 1, a = 2;
    const int MOD = 100000;
    while (n > 0) {
        if (n % 2) {
            x = (x * a) % MOD;
        }
        a = (a * a) % MOD;
        n /= 2;
    }
    return x;
}

修改后，a*a的最大值为(99999)^2=9999800001，远小于long long的上限，计算过程不会溢出，取模后结果始终正确。

内容的提问来源于stack exchange，提问作者ehuang98