乘法逆元

乘法逆元

如果一个线性方程ax \equiv 1(mod b)，则x称为a(mod)b的逆元，即x = a^{-1}。

下面介绍求逆元的几种方法。

(单个)扩展欧几里得

扩展欧几里得是用来求方程ax + by = gcd(a, b)的解的。
当ab不互质时，a关于令一个数b的逆元是不一定存在的，我们先把上述线性方程进行转化：ax + by = 1，根据裴属定理：ax + by = gcd(a, b)有解，若gcd(a, b)!=1，则解不一定存在。

void extgcd(int a, int b, ll &x, ll &y) {
    if (b==0) {
        x = 1, y = 0;
        return;
    }
    extgcd(b, a%b, y, x);
    y -= a/b*x;
    return;
}

(单个)费马小定理

当p为质数时，a^{p-1} \equiv 1(modp)。
a^{-1} = a^{p-2}(modp)，快速幂求解。

(多个)欧拉筛

因为逆元是完全积性函数，所以可以线筛得到。
a*inv(a)=1(modp), b*inv(b)=1(modp),a*inv(a)*b*inv(b)=(a*b)*(inv(a)*inv(b))=1(modp)

(多个)线性求

实在太懒了，贴个别人的证明吧...

inv[1] = 1;
for(int i=2; i<=n; i++)
    inv[i] = (p - p / i) * inv[p % i] % p;