Các phép cộng, trừ, nhân

Đối với phép cộng ta có:

$(a+b)modm=(amodm+bmodm)modm$
Tương tự với phép trừ và nhân:

$(a-b)modm=(amodm-bmodm)modm$

$(a\cdot b)modm=((amodm)\cdot (bmodm))modm$

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)modm=((amodm+bmodm)modm+m)modm$

$(a-b)modm=((amodm-bmodm)modm+m)modm$

$(a\cdot b)modm=(((amodm)\cdot (bmodm))modm+m)modm$

Tính

$a^{b}modm$

Ta cũng có thể dùng lũy thừa nhị phân kết hợp thêm

$modm$:

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(\mathrm{mod}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

$(gcd(a,m)=1)$.

Tìm nghịch đảo modular bằng Euclid mở rộng

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 ymodm=0$)

$\Rightarrow a\cdot x\equiv 1(\mathrm{mod}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

Theo định lý Euler, nếu

$a$ và

$m$ là hai số nguyên tố cùng nhau thì:

$a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$ với

$\varphi$ là phi hàm Euler.
Nếu

$m$ là số nguyên tố thì quy về định lý nhỏ Fermat:

$a^{m-1}\equiv 1(\mathrm{mod}m)$ (với

$m$ nguyên tố thì

$\varphi (m)=m-1$).
Nhân cả hai vế cho

$a^{-1}$ ta được:

$$a^{-1}\equiv \{\begin{array}{ll}{a}^{m-2}& \text{với }m\text{ nguyên tố}\\ a^{\varphi (m)-1}& \text{với }m\text{ không nguyên tố}\end{array}(\mathrm{mod}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=\lfloor \frac{m}{a}\rfloor$ và

$p=mmoda$

$$m=a\cdot q+p$$

$$a\cdot q+p\equiv 0(\mathrm{mod}m)$$

$$a\equiv \frac{-p}{q}(\mathrm{mod}m)$$

$$a^{-1}\equiv \frac{-q}{p}(\mathrm{mod}m)$$

$$a^{-1}\equiv -q\cdot p^{-1}(\mathrm{mod}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}(\mathrm{mod}m)$$
Thay

$q$ và

$p$ như bên trên:

$$\Rightarrow a^{-1}\equiv m-\lfloor \frac{m}{a}\rfloor \cdot (mmoda{)}^{-1}(\mathrm{mod}m)$$
Hay:

$$inv[a]\equiv m-\lfloor \frac{m}{a}\rfloor \cdot inv[mmoda](\mathrm{mod}m)$$
Vì

$mmoda<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;