逆元

方程 的一个解 x ，称 x 为 a 模 M 的逆。

扩展欧几里得求解逆元

注：a 和 M 需要互质，速度比费马小定理快一点

void exgcd(int a, int b, int &x, int &y) { // ax + by = gcd(a,b)
    if (b == 0) x = 1, y = 0;
    else exgcd(b, a%b, y, x), y -= a/b*x;
}

void inv(int a, int M) { // 逆元
    int x, y;
    exgcd(a, M, x, y);
    return (x%M + M) %M;
}

费马小定理求解逆元

时间复杂度
注：M 必须为质数。

fast(b, M-2); // 用快速幂求 b 的逆元

线性递推逆元 -- 打表专用

时间复杂度

void init(int n, int M) {
    sinv[1] = inv[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        inv[i] = (M - M/i) * inv[M%i]  %M;
        sinv[i] = (sinv[i-1] + inv[i]) %M;
    }
}