求一个数模逆元的c++代码

以下是求一个数的模逆元的C++代码：

#include <iostream>
using namespace std;

int modInverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1) return 0;

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0) x1 += m0;

    return x1;
}

int main() {
    int a = 5, m = 7;
    cout << "The modulo inverse of " << a << " under " << m << " is " << modInverse(a, m) << endl;
    return 0;
}

输出结果为：

The modulo inverse of 5 under 7 is 3

其中，`modInverse(a, m)` 函数用于计算 a 在模 m 意义下的逆元。