逆元的三种求法

详情请参考inv[orz]：https://www.cnblogs.com/zjp-shadow/p/7773566.html

拓展欧几里得(当 a与p互质，但 p 不是质数的时候也可以使用。)

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    ll x, y;
    Exgcd (a, p, x, y);
    x = (x % p + p) % p;//????
    printf ("%d
", x); //x是a在mod p下的逆元
}

费马小定理（欧拉定理的特殊情况）：若p为素数，a为正整数，且a、p互质。则有a^(p−1)≡1(mod p)。

ll fpm(ll x, ll power, ll mod) {//快速幂
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
        if(power & 1) (ans *= x) %= mod;
    return ans;
}
int main() {
    ll x = fpm(a, p - 2, p);
}

用于求一连串数字对于一个mod p的逆元。

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