快速幂代码实现遇问题：无法得到正确模运算结果求解答

我在Coding Ninza平台编写了以下快速幂（fast exponential）代码，但未得到正确结果。我计算指数的部分逻辑正确，但无法得到期望的模运算结果，请问有人能帮我解决这个问题吗？

int modularExponentiation(int x, int n, int m) {
int res=1;
    int t=n/2;
    while(t--){
        res=((res)%m)*((x)%m);
    }
    res=((res)%m)*((res)%m);
    if(n&1){
        res=(res*x)%m;
    }
    return res;
}

你的代码逻辑完全偏离了快速幂的核心思路，问题主要出在这几点：

• while(t--)循环本质是直接计算x^(n/2)，但循环内未对每次乘法结果取模，极易触发整数溢出；若n为奇数，n/2会被截断，后续计算也会因溢出提前出错。
• 快速幂的核心是二分迭代+每次运算取模，而非先算一半再平方的粗暴实现。

以下是符合要求的正确实现，严格规避溢出并遵循模运算规则：

int modularExponentiation(int x, int n, int m) {
    long long res = 1; // 用long long存储中间结果，避免乘法溢出
    x = x % m; // 先对底数取模，减少计算量
    while (n > 0) {
        // 指数为奇数时，将当前底数乘入结果
        if (n & 1) {
            res = (res * x) % m;
        }
        // 指数二分，底数平方后取模
        x = (1LL * x * x) % m;
        n = n >> 1; // 等价于n = n / 2
    }
    return (int)res;
}

关键细节说明 #

• 用long long存储中间值：两个int类型的大数相乘会远超int的范围（如1e9*1e9=1e18，远大于int最大值约2e9），long long可避免溢出。
• 每次运算后立即取模：保证结果始终处于m的范围内，既符合题目要求，又防止数值过大导致的溢出错误。
• 提前对底数取模：若x本身大于m，先取模可缩小后续计算的数值规模，提升效率。

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