Unsigned Long Int溢出：快速幂计算x^y mod z高次幂返回0问题排查

老哥，我帮你瞅了下你的代码，问题主要出在俩地方：快速幂的实现逻辑不对，而且没及时做模运算防止溢出。咱们一步步捋清楚：

1. 快速幂的逻辑完全走偏了 #

你现在的代码是遇到指数的第i位为1时，循环i-lastTrueBit次去平方curPow，这根本不是快速幂的正确打开方式。举个你遇到的例子：算2^64 mod3，指数64的二进制是1000000（第6位是1，从0开始数），lastTrueBit初始是0，i=6时会循环6次平方curPow：

• 初始curPow=2，第一次平方变4，第二次变16，第三次变256，...，第六次平方后是2^(2^6)=2^64

但unsigned long long的最大值是2^64-1，2^64直接就溢出归零了，后面resPow=1*0自然也是0，取模3结果肯定是0。

2. 没及时取模，溢出问题根本没解决 #

就算逻辑对了，你也得在每次乘法后立刻取模，不然哪怕是unsigned long long，遇到超大数也会溢出归零。比如上面的例子，要是每次平方后都取模3，curPow永远不会超过2，根本不可能溢出。

咱们改成标准的快速幂实现，并且每一步运算都及时取模：

typedef unsigned long int lint;

lint fastpow(lint nBase, lint nExp, lint nMod) {
    // 特殊情况：任何数模1都是0，直接返回
    if (nMod == 1) return 0;
    
    unsigned long long int resPow = 1ULL;
    unsigned long long int curPow = nBase % nMod; // 先把底数取模，减小初始值
    
    while (nExp > 0) {
        // 如果指数当前最低位是1，把curPow乘到结果里再取模
        if (nExp & 1) {
            resPow = (resPow * curPow) % nMod;
        }
        // 指数右移一位（相当于除以2），底数平方后取模
        curPow = (curPow * curPow) % nMod;
        nExp >>= 1;
    }
    return (lint)resPow;
}

• 标准快速幂逻辑：逐位处理指数的二进制位，每次把指数右移一位，底数平方，遇到1位就乘到结果里，既高效又不会出现过度平方的情况，计算复杂度是O(log n)。
• 及时取模：每次乘法后立刻对nMod取模，让curPow和resPow的值始终保持在合理范围内，完全避免溢出。比如算2^64 mod3时，curPow每次平方后取模3，永远只会是1或2，根本碰不到溢出的情况，最终结果会正确返回1（因为2^2 mod3=1，2⁶⁴⁼⁽²2)^32 mod3=1^32 mod3=1）。

另外，原来的循环只跑32次，现在用while(nExp>0)的方式，不管nExp是多少位的数都能处理，通用性更强。

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