如何让模逆程序支持更大数值输入？

问题核心 #

你的溢出问题和递归无关，根源是没有把所有参与运算的变量都替换成64位整数。只改部分变量的话，比如int类型的x、y、a、b在计算(b/a)*x1这类表达式时，依然会超出int的范围（int最大仅约2e9），导致溢出。

修正方案 #

1. 全量替换为64位整数（保留递归） #

把函数参数、局部变量、指针类型全部换成long long，确保所有运算都在64位范围内进行。修正后的代码如下：

#include <iostream>
using namespace std;

long long gcdExtended(long long a, long long b, long long* x, long long* y);
 
void modInverse(long long A, long long M)
{
    long long x, y;
    long long g = gcdExtended(A, M, &x, &y);
    if (g != 1)
        cout << "Inverse doesn't exist";
    else {
        long long res = (x % M + M) % M;
        cout << "Modular multiplicative inverse is " << res;
    }
}
 
long long gcdExtended(long long a, long long b, long long* x, long long* y)
{
    // Base Case
    if (a == 0) {
        *x = 0, *y = 1;
        return b;
    }
 
    // To store results of recursive call
    long long x1, y1;
    long long gcd = gcdExtended(b % a, a, &x1, &y1);
 
    *x = y1 - (b / a) * x1;
    *y = x1;
 
    return gcd;
}

2. 可选：改用迭代版扩展欧几里得 #

如果担心递归栈深度（但对于5e9级别的模数，递归深度仅约30层，完全不会栈溢出），可以换成迭代实现，逻辑和递归一致：

#include <iostream>
using namespace std;

long long modInverse(long long A, long long M) {
    long long m0 = M;
    long long y = 0, x = 1;
 
    if (M == 1)
        return 0;
 
    while (A > 1) {
        // q 是商
        long long q = A / M;
        long long t = M;
 
        M = A % M, A = t;
        t = y;
 
        y = x - q * y;
        x = t;
    }
 
    // 确保结果为正
    if (x < 0)
        x += m0;
 
    return x;
}

// 调用示例
int main() {
    long long A = 15001, M = 5729413260;
    long long inv = modInverse(A, M);
    if (inv == 0 && M != 1)
        cout << "Inverse doesn't exist";
    else
        cout << "Modular multiplicative inverse is " << inv;
    return 0;
}

关键注意事项 #

• 必须保证所有涉及乘法、减法的变量都是64位整数，long long能覆盖到9e18的范围，完全满足你给出的模数需求。
• 递归版本本身没有问题，无需刻意放弃，极端大数值导致栈溢出的情况几乎不会出现。

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