P3811 【模板】乘法逆元

此题不是求单个逆元的模板题，但可以用这道模板题检验这种求逆方法的正确性（没有WA）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int inv(int n, int mod) {
    int ans, k;
    exgcd(n, mod, ans, k);
    return (ans % mod + mod) % mod;
}