乘法逆元

线性逆元

设$p=k \times i+b$,

则$k=p \div i, b=p \% i$

$k*i+b\equiv0(mod p)$

同时除以i和b

$k*(1\div b)+(1 \div i)\equiv0(modp)$

则$1\div i\equiv-k*(1\div b)(modp)$

将k,b代入

$inv[i]\equiv(-p\div i)*inv[p/i](modp)$,

由于右边式子可能小于0，所以再加上p

$inv[i]\equiv p-p\div i*inv[p\%i](modp)$,

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

线性求任意 n 个数的逆元

用s[i]表示前n个数的前缀积，sv[i]表示n个数的积的逆元

那么$\frac{1}{i}$可用$s[i-1]*sv[i]$表示

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

模数不是质数时求逆元

ll exgcd(ll a, ll b, ll& x, ll& y)  //扩展欧几里得算法
{
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll ret = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
ll getInv(int a, int mod)  //求a在mod下的逆元，不存在逆元返回-1
{
    ll x, y;
    ll d = exgcd(a, mod, x, y);
    return d == 1 ? (x % mod + mod) % mod : -1;
}