# 同余

两个整数 $a, b$，如果$(a - b) \% m = 0$，则称 $a、b$ 对于模 $m$ 同余，记作 $a ≡ b(mod~m)$，读作：$a$ 同余于 $b$ 模 $m$
$a ≡ b(mod$ $m)$ $\to$ $(a - b)$ $\%$ $m == 0$

# 何谓 "逆元"？

在取模的条件下，除以一个数等于乘以这个数的乘法逆元

$$x / 2 \% 107 ≡ x* 54 \% 107$$

那么 $54$ 就是 $2$ 在模 $107$ 条件下的乘法逆元
一个数 $a$ 存在乘法逆元的充要条件是 $a$ 与模数 $m$ 互质。
当模数 $m$ 为质数时，$a^{m−2}$ 即为 $a$ 的乘法逆元

1
2
3
4
5
6
7
8
9
10
11
12
13

int qmi(int a, int b, int MOD) {
    int res = 1;
    while (b) {
        if (b & 1)
            res *= b;
        b >>= 1, a = a * a % MOD;
    }
    return res;
}

int main() {
    (a / b) % MOD = a * qmi(b, MOD - 2) % MOD 
}