MinGW64环境下long int整数运算结果异常，请求技术支持

你的代码目的是计算 (b^e \mod n)，在线编译器能输出正确结果199324862，但Windows 10+Code::Blocks+MinGW64环境下得到错误值298405922，核心原因是整数溢出，具体分析和修复方案如下：

问题根源：平台依赖的整数宽度差异 #

long int的字节宽度在不同平台下并不统一：

• 在线Linux编译器中，long int是8字节（64位），最大值为 (2^{63}-1)，能容纳代码中a * r产生的大中间值；
• Windows下的MinGW64中，long int是4字节（32位），最大值仅为 (2^{31}-1=2147483647)。而你的代码中，第一次乘法1 * 116104101没问题，但第二次乘法116104101 * 116104101结果约为(1.347×10^{16})，远超过32位整数的上限，直接触发溢出，导致后续计算全部出错。

修复方案 #

方案1：改用64位整数类型 #

将代码中所有long int替换为long long（Windows和Linux下均为64位），确保中间乘积不会溢出：

#include <iostream>
#include <math.h>

using namespace std;

long long cifra(long long b, long long e, long long n)
{
    /* Calcula a tal que (b^e)=a MOD n. Algoritmo 3.1 de Allenby & Redfern,1989. */
    long long a, i, q, r;

    a = 1;
    q = b / n;
    r = b - q * n;
    for (i = 1; i <= e; i++)
    {
        a = a * r;
        q = a / n;
        a = a - q * n;        /* ou, de forma equivalente, a=mod(a,n) */
    }
    return a;
}

int main()
{
    long long a, b, e, n;

    b = 116104101;
    e = 19661;
    n = 383768051;

    a = cifra(b, e, n);

    cout << "a=" << a << endl;

    return 0;
}

方案2：使用高效的快速幂（模幂）算法 #

你当前的逐次乘法算法时间复杂度为(O(e))，且容易溢出。快速幂算法通过每次迭代都取模，彻底避免大中间值产生，同时将时间复杂度降至(O(\log e))，效率提升明显：

#include <iostream>
using namespace std;

long long mod_pow(long long b, long long e, long long n)
{
    long long result = 1;
    b = b % n; // 先将底数约束在模n范围内
    while (e > 0)
    {
        // 指数为奇数时，将当前底数乘入结果并取模
        if (e % 2 == 1)
            result = (result * b) % n;
        // 指数折半
        e = e >> 1;
        // 底数平方后取模
        b = (b * b) % n;
    }
    return result;
}

int main()
{
    long long a, b, e, n;
    b = 116104101;
    e = 19661;
    n = 383768051;
    a = mod_pow(b, e, n);
    cout << "a=" << a << endl;
    return 0;
}

内容的提问来源于stack exchange，提问作者Rudnei Dias da Cunha