Đồng Dư Thức, Lũy Thừa Nhị Phân & Nghịch Đảo Modulo

1. Bản chất vấn đề & trực giác thuật toán (the core problem & intuition)

Trong nhiều bài toán lập trình và thi đấu thuật toán, kết quả tính toán hoặc số cách đếm tổ hợp thường tăng rất nhanh và vượt quá giới hạn lưu trữ của kiểu số nguyên 64-bit (long long). Để tránh việc phải xử lý số lớn phức tạp, đề bài thường yêu cầu: "In ra kết quả sau khi chia lấy dư cho $M$" (thông thường $M = 10^9 + 7$ hoặc $998244353$ — là các số nguyên tố lớn).

Từ yêu cầu thực tế này, bộ ba kỹ thuật nền tảng được hình thành: $\text{Đồng Dư Cơ Bản (+, -, *)} \longrightarrow \text{Lũy Thừa Nhị Phân } \mathcal{O}(\log B) \longrightarrow \text{Nghịch Đảo Modulo } (B^{-1})$

Vấn đề 1: Phép tính lũy thừa $A^B \pmod M$

• Cách ngây thơ: Nhân $B$ lần liên tiếp: $A \times A \times \dots \times A \implies \mathcal{O}(B)$. Khi $B = 10^{18}$, cách này hoàn toàn bất khả thi.
• Trực giác Chia để trị (Binary Exponentiation):
• Nếu $B$ chẵn: $A^B = (A^2)^{B / 2} = (A^{B / 2})^2$.
• Nếu $B$ lẻ: $A^B = A \times A^{B - 1}$.
• Sau mỗi bước, số mũ $B$ giảm đi một nửa $\implies$ Số phép nhân chỉ còn $\mathcal{O}(\log_2 B)$ (chưa tới $60$ phép tính với $B = 10^{18}$).

Vấn đề 2: Phép chia trên vành modulo $\left(\frac{A}{B} \pmod M\right)$

• Trong số học đồng dư, không thể thực hiện phép chia bằng phép chia số nguyên thông thường (tức $\frac{A}{B} \pmod M \not\equiv \frac{A \pmod M}{B \pmod M}$).
• Nghịch đảo Modulo ($B^{-1}$): Muốn tính $\frac{A}{B} \pmod M$, ta chuyển phép chia thành phép nhân với nghịch đảo modulo $B^{-1}$ (nếu nghịch đảo tồn tại): $$\frac{A}{B} \pmod M \equiv (A \times B^{-1}) \pmod M$$ với $B^{-1}$ là số nguyên thỏa mãn: $(B \times B^{-1}) \equiv 1 \pmod M$.

2. Mô phỏng từng bước (visual step-by-step simulation)

Ví dụ 1: Mô phỏng tính $3^{13} \pmod{1000}$ bằng lũy thừa nhị phân

Biểu diễn nhị phân của số mũ $13 = 1101_2 = 8 + 4 + 1$. Do đó: $3^{13} = 3^8 \times 3^4 \times 3^1$.

Ví dụ 2: Mô phỏng tìm nghịch đảo modulo của $3 \pmod 7$

Ta cần tìm số nguyên $X \in \{1, \dots, 6\}$ sao cho $(3 \times X) \pmod 7 = 1$.

Kiểm chứng bằng Định lý Fermat nhỏ: $3^{7-2} = 3^5 = 243 \equiv 5 \pmod 7$.

3. Lý thuyết cốt lõi & bất biến toán học (core invariants)

3.1. Các quy tắc đồng dư cơ bản (+, -, *)

1. Phép Cộng: $(A + B) \pmod M = ((A \pmod M) + (B \pmod M)) \pmod M$.
2. Phép Trừ (Tránh số âm): $(A - B) \pmod M = ((A \pmod M) - (B \pmod M) + M) \pmod M$.
3. Phép Nhân: $(A \times B) \pmod M = ((A \pmod M) \times (B \pmod M)) \pmod M$.

Cảnh báo quan trọng:

2 Bẫy Lỗi KHI THỰC HIỆN PHÉP TOÁN ĐỒNG DƯ:

1. Số dư âm trong C++: Trong C++, phép toán -7 % 5 trả về -2 (không phải 3). Để luôn nhận kết quả không âm, bắt buộc phải viết: (a % m + m) % m.
2. Tràn số 32-bit khi nhân: Nếu $A, B \approx 10^9$, tích $A \times B \approx 10^{18}$ vượt giới hạn kiểu int. Bắt buộc phải ép kiểu 64-bit trước khi nhân: (1LL * a * b) % m.

3.2. Định lý Fermat nhỏ & nghịch đảo modulo

Nếu $M$ là một số nguyên tố và $A$ không chia hết cho $M$ ($\gcd(A, M) = 1$), thì: $$A^{M - 1} \equiv 1 \pmod M \implies A \times A^{M - 2} \equiv 1 \pmod M$$

$$\implies \mathbf{A^{-1} \equiv A^{M - 2} \pmod M}$$

Ta có thể tính $A^{-1} \pmod M$ chỉ bằng một hàm Lũy thừa nhị phân: power(A, M - 2, M) trong $\mathcal{O}(\log M)$.

Chú ý:

ĐIỀU KIỆN TIÊN QUYẾT CỦA ĐỊNH LÝ FERMAT NHỎ:

• Quy tắc $A^{M - 1} \equiv 1 \pmod M$ và việc rút gọn số mũ $B \gets B \pmod{(M - 1)}$ CHỈ ĐÚNG KHI $M$ LÀ SỐ NGUYÊN TỐ VÀ $\gcd(A, M) = 1$.
• Tuyệt đối không tùy tiện áp dụng nếu $A$ chia hết cho $M$ hoặc $M$ là hợp số.

3.3. Thuật toán euclid mở rộng (extended euclidean algorithm)

Khi $M$ không phải là số nguyên tố (nhưng $\gcd(A, M) = 1$), định lý Fermat nhỏ không áp dụng được. Ta dùng thuật toán Euclid mở rộng để giải phương trình nghiệm nguyên: $$A \times x + M \times y = \gcd(A, M) = 1$$ Khi đó, $x \pmod M$ chính là nghịch đảo modulo $A^{-1}$.

3.4. Tính tổ hợp $C(N, K) \pmod M$ trong $\mathcal{O}(1)$ mỗi truy vấn

Công thức số tổ hợp chập $K$ của $N$: $$C(N, K) = \frac{N!}{K! \times (N - K)!} \equiv N! \times (K!)^{-1} \times ((N - K)!)^{-1} \pmod M$$

• Tiền xử lý trong $\mathcal{O}(N)$: 1. Tính mảng giai thừa: fact[i] = (fact[i-1] * i) % M. 2. Tính mảng nghịch đảo giai thừa: invFact[N] = power(fact[N], M - 2, M), sau đó đi ngược về 0: invFact[i - 1] = (invFact[i] * i) % M.
• Trả lời mỗi truy vấn trong $\mathcal{O}(1)$: $$C(N, K) = \text{fact}[N] \times \text{invFact}[K] \pmod M \times \text{invFact}[N - K] \pmod M$$

3.5. Tính tổng cấp số nhân modulo bằng chia để trị

Cần tính tổng: $$S_N = 1 + A + A^2 + \dots + A^N \pmod M$$

• Trường hợp cơ sở: Nếu $N = 0 \implies S_0 = 1$.

• Nếu $N$ lẻ (Tổng có $N + 1$ số hạng chẵn): $$S_N = (1 + A + \dots + A^{(N-1)/2}) + A^{(N+1)/2} (1 + A + \dots + A^{(N-1)/2})$$ $$S_N = S_{(N-1)/2} \times \left(1 + A^{(N+1)/2}\right) \pmod M$$

• Nếu $N$ chẵn: Tách riêng số hạng cuối cùng: $$S_N = 1 + A \times S_{N-1} \pmod M$$

• Độ phức tạp: $\mathcal{O}(\log^2 N)$ hoặc $\mathcal{O}(\log N)$, mở đường cho kỹ thuật nhân lũy thừa ma trận và quy hoạch động cấu trúc đại số.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Chia trực tiếp trên Modulo: * Viết ((A % M) / (B % M)) % M là HOÀN TOÀN SAI BẢN CHẤT TOÁN HỌC. Phép chia bắt buộc phải chuyển thành nhân với nghịch đảo: (A * inverse(B)) % M.
2. Quên xử lý trường hợp $K > N$ hoặc $K < 0$ khi tính tổ hợp:

• $C(N, K) = 0$ khi $K < 0$ hoặc $K > N$. Nếu không kiểm tra sẽ bị truy cập ô nhớ âm hoặc rác.

1. Trường hợp $M = 1$: * $A^B \pmod 1$ luôn bằng $0$. Hàm lũy thừa cần trả về 0 khi $M = 1$.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Lũy thừa nhị phân & nghịch đảo modulo chuẩn

# include <bits/stdc++.h>
using namespace std;

// Tính (a^b) % m trong O(log b)
long long powerMod(long long a, long long b, long long m) {
    if (m == 1) return 0;
    long long ans = 1 % m;
    a %= m;
    while (b > 0) {

        if (b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

// Nghịch đảo Modulo bằng Định lý Fermat nhỏ (khi m là số nguyên tố)
long long modInversePrime(long long a, long long m) {
    return powerMod(a, m - 2, m);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b, m;
    if (!(cin >> a >> b >> m)) return 0;

    cout << powerMod(a, b, m) << "\n";
    return 0;
}

Mẫu 2: Tiền xử lý tổ hợp $C(N, K) \pmod M$ trong $\mathcal{O}(1)$ mỗi truy vấn

# include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000000;
const long long MOD = 1000000007;

vector<long long> fact(MAXN + 1);

vector<long long> invFact(MAXN + 1);

long long powerMod(long long a, long long b, long long m) {
    long long ans = 1;
    a %= m;
    while (b > 0) {

        if (b & 1) ans = (ans * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return ans;
}

void precomputeCombinatorics() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invFact[MAXN] = powerMod(fact[MAXN], MOD - 2, MOD);
    for (int i = MAXN; i >= 1; --i) {
        invFact[i - 1] = (invFact[i] * i) % MOD;
    }
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;

    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    precomputeCombinatorics();

    int q;
    if (!(cin >> q)) return 0;

    while (q--) {
        int n, r;
        cin >> n >> r;

        cout << nCr(n, r) << "\n";
    }
    return 0;
}