P3811 【模板】乘法逆元

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int power(int x, int y, int mod) {
    int ans = 1;
    while (y) {
        if (y & 1) {
            ans = (1LL * ans * x) % mod;
        }
        y >>= 1;
        x = (1LL * x * x) % mod;
    }
    return ans;
}

int inv(int n, int mod) {
    return power(n, mod - 2, mod);
}