逆元c++

(a + b) % p = (a%p + b%p) % p （对）

(a - b) % p = (a%p - b%p) % p （对）

(a * b) % p = (a%p * b%p) % p （对）

(a / b) % p = (a%p / b%p) % p （错）

当运算大数的时候，有时候必须先进行取模运算（否则就爆了）

但是除法不能用

那怎么办呢？

我们引入逆元！

总所周知，2的倒数是0.5，4的倒数是0.25。

但在全是取模运算下，我们定义

若 2*x（mod p）= 1，则x为2关于p的逆元。

对于a的逆元，记作inv（a）。

在引入逆元的概念后，我们可以对第四个式子进行修改，有

(a / b) % p = (a * inv(a) ) % p = (a % p * inv(a) % p) % p

这样我们就可以快乐的进行取模了！

(1的逆元是1)

费马曾说：

$$
a^{p-1}equiv 1(mod p)//p是一个质数，而整数a不是p的倍数
$$

这样，我们有：

$$
inv(a)=a^{p-2}(mod p)
$$

代码：

ll get_inv(ll a, ll p = MOD) {
    ll ans = 1;
    ll t = p - 2;
    while (t) {
        if (t & 1)ans = ans * a % p;
        a = a * a % p;
        t >>= 1;
    }
    return ans;
}

欧几里得说过：

$$
ax + by = gcd(a,b)
$$

此时，x为a关于b的inv

void ex_gcd(ll a, ll b, ll& x, ll& y, ll& d) {
    if (!b) { d = a, x = 1, y = 0; }
    else {
        ex_gcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}
ll get_inv(ll t, ll p) {//如果不存在，返回-1 
    ll d, x, y;
    ex_gcd(t, p, x, y, d);
    return d == 1 ? (x % p + p) % p : -1;
}

$$
inv(a) = (p - p / a) * inv(p % a) % p
$$

ll get_inv(ll a, ll p = MOD) {
    return a == 1 ? 1 : (p - p / a) * 1LL * get_inv(p % a, p) % p;
}
void init_inv(ll n, ll p = MOD) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (p - p / i) * 1LL * inv[p % i] % p;
    }
}