经典算法

扩展欧几里得算法求逆元

模 b 不是必须为质数。

// 小牛编程 
#include <iostream>
using namespace std;

// 扩展欧几里得算法，x即为a在模b下的乘法逆元
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int g = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - (a / b) * y;
    return g;
}

// 求逆元
int inv(int a, int p) {
    int x, y;
    int g = exgcd(a, p, x, y);

    // a和p不互质，逆元不存在
    if (g != 1) {
        return -1;
    }

    // 确保逆元是非负的
    return (x % p + p) % p;
}

int main() {
    int a = 7;
    int p = 13;
    int ans = inv(a, p);

    if (ans == -1) {
        cout << "逆元不存在" << endl;
    } else {
        cout << a << "在模" << p << "下的乘法逆元是：";
        cout << ans << endl;
    }
    return 0;
}