## Các phép cộng, trừ, nhân
Đối với phép cộng ta có: $(a + b) \bmod m = (a \bmod m + b \bmod m) \bmod m$
Tương tự với phép trừ và nhân:
$(a - b) \bmod m = (a \bmod m - b \bmod m) \bmod m$
$(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$

***Lưu ý:*** Vì kết quả có thể âm nhưng hầu như ta đều muốn kết quả của phép mod là dương nên ta sẽ cộng thêm m vào cuối:
$(a + b) \bmod m = ((a \bmod m + b \bmod m) \bmod m + m) \bmod m$
$(a - b) \bmod m = ((a \bmod m - b \bmod m) \bmod m + m) \bmod m$
$(a \cdot b) \bmod m = (((a \bmod m) \cdot (b \bmod m)) \bmod m + m) \bmod m$
<br>

## Tính $a^b \bmod m$
Ta cũng có thể dùng [lũy thừa nhị phân](https://hackmd.io/IsGwluMuQSuzeJ8NY0mEKw) kết hợp thêm $\bmod m$:

long long binpow(long long a, long long b, long long m) {
    long long res = 1;
    a %= m;
    while(b > 0) {
        if(b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

## Phép chia
mod trong phép chia không giống với cộng, trừ, hay nhân, mà ta sẽ dùng tới một khái niệm mới: **nghịch đảo modular**.

*Nghịch đảo modular* của một số $a$ là một số $x$ sao cho $a \cdot x \equiv 1 \pmod m$
$x$ cũng được gọi là $a^{-1}$.

***Lưu ý:*** Ta chỉ có thể tìm được nghịch đảo modular của $a$ khi $a$ và $m$ là 2 số nguyên tố cùng nhau $\left(\gcd(a, m) = 1\right)$.

### Tìm nghịch đảo modular bằng [Euclid mở rộng](https://hackmd.io/go85krkoRnKZ8LyEMuIGNw)
Ta có: $\gcd(a, m) = 1 \Rightarrow a \cdot x + m \cdot y = 1$
mod m cho cả 2 vế (dùng công thức cộng mod bên trên $\Rightarrow$ $m \cdot y$ sẽ mất vì $m \cdot y \bmod m = 0$) $\Rightarrow a \cdot x \equiv 1 \pmod m$

int x, y, g;
g = extended_euclidean(a, m, x, y);
if(g == 1) {
    x = (x % m + m) % m;
    cout << x;
}
else
    cout << "No solution";

### Tìm nghịch đảo modular bằng [lũy thừa nhị phân](https://hackmd.io/IsGwluMuQSuzeJ8NY0mEKw)
Theo định lý Euler, nếu $a$ và $m$ là hai số nguyên tố cùng nhau thì: $a^{\phi(m)} \equiv 1 \pmod m$ với $\phi$ là [phi hàm Euler](https://hackmd.io/3RrCoahISgOJ-3phIoXE0g#Phi-h%C3%A0m-Euler).
Nếu $m$ là số nguyên tố thì quy về [định lý nhỏ Fermat](https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_nh%E1%BB%8F_Fermat): $a^{m-1} \equiv 1 \pmod m$ (với $m$ nguyên tố thì $\phi(m) = m-1$).
Nhân cả hai vế cho $a^{-1}$ ta được:
$$a^{-1} \equiv \begin{cases} a^{m-2} &\text{với } m \text{ nguyên tố} \\ a^{\phi(m)-1} &\text{với } m \text{ không nguyên tố} \end{cases} \pmod m$$

Từ đó ta có thể dùng lũy thừa nhị phân như trên để tính.

### Tìm nghịch đảo modular cho $m$ số (chỉ áp dụng cho $m$ nguyên tố)
Ta sẽ xây dựng một mảng $inv$ để lưu lại nghịch đảo modular của các số tới $m$.
Nếu ta duyệt i từ $1$ tới $m$, sau đó tính nghịch đảo modular của từng i, độ phức tạp sẽ là $O(m \log m)$.
Tuy nhiên có một cách để tính trong $O(m)$:
Với số nguyên tố $m$ > $a$, theo Euclidean divison, tồn tại 2 số $q$ và $p$ sao cho: $m = a \cdot q + p$ với $q = \left\lfloor{m \over a}\right\rfloor$ và $p = m \bmod a$
$$m = a \cdot q + p$$
$$a \cdot q + p \equiv 0 \pmod m$$
$$a \equiv {-p \over q} \pmod m$$
$$a^{-1} \equiv {-q \over p} \pmod m$$
$$a^{-1} \equiv -q \cdot p^{-1} \pmod m$$
Có thể thấy $-q \cdot p^{-1}$ là số âm nên ta sẽ cộng thêm $m$ vào:
$$a^{-1} \equiv m - q \cdot p^{-1} \pmod m$$
Thay $q$ và $p$ như bên trên:
$$\Rightarrow a^{-1} \equiv m - \left\lfloor{m \over a}\right\rfloor \cdot (m \bmod a)^{-1} \pmod m$$
Hay: $$inv[a] \equiv m - \left\lfloor{m \over a}\right\rfloor \cdot inv[m \bmod a] \pmod m$$
Vì $m \bmod a < a$ nên ta sẽ tính được $inv[a]$ dựa vào các giá trị trước.

inv[0] = inv[1] = 1;
for(int i = 2; i <= MAXN; ++i) // MAXN <= mod
    inv[i] = mod - (long long)(mod / i) * inv[mod % i] % mod;