Modulo & Lũy Thừa Nhanh

1. Khái niệm & bản chất của đại số đồng dư trong lập trình thi đấu

Trong các bài toán đếm tổ hợp, xác suất và tối ưu hóa quy mô lớn, kết quả đầu ra thường tăng theo hàm số mũ hoặc giai thừa, dễ dàng vượt qua giới hạn biểu diễn của số nguyên 64-bit (long long $\approx 9.22 \times 10^{18}$). Để tránh việc phải xử lý số nguyên lớn (BigInt) làm chậm thời gian thực thi, các đề thi thường yêu cầu tính toán kết quả theo modulo của một số nguyên $M$ (thông dụng nhất là số nguyên tố lớn như $10^9 + 7$ hoặc $998244353$).

Đại số đồng dư (Modular Arithmetic) cho phép ta thu gọn các số cực lớn về một không gian hữu hạn $\{0, 1, \dots, M - 1\}$ mà vẫn bảo toàn các tính chất toán học của phép cộng, trừ, nhân. Tuy nhiên, phép chia trong modulo không thể thực hiện trực tiếp mà phải thông qua khái niệm Nghịch đảo modulo (Modular Inverse).

2. Các quy tắc tính toán đồng dư cơ bản & bẫy lỗi tử huyệt

2.1. Bốn phép toán đồng dư cơ sở

Với mọi $A, B \in \mathbb{Z}$ và số chia modulo $M$:

1. Phép cộng: $(A + B) \bmod M = ((A \bmod M) + (B \bmod M)) \bmod M$
2. Phép nhân: $(A \times B) \bmod M = ((A \bmod M) \times (B \bmod M)) \bmod M$
3. Phép trừ: $(A - B) \bmod M = ((A \bmod M) - (B \bmod M) + M) \bmod M$
4. Phép lũy thừa: $A^B \bmod M = (A \bmod M)^B \bmod M$

2.2. Tử huyệt lập trình: Bẫy số âm và bẫy tràn số trung gian

Cảnh báo bẫy lỗi 1: BẪY SỐ ÂM KHI TRỪ MODULO TRONG C++

Trong C++, toán tử % là phép chia lấy phần dư định hướng về 0 (truncated division), nghĩa là nếu $A < B$ thì (A - B) % M sẽ trả về số âm (ví dụ: (3 - 7) % 5 = -4 % 5 = -4 thay vì $+1$).

Quy tắc an toàn tuyệt đối: Luôn cộng thêm $M$ trước khi lấy dư: cpp long long mod_sub(long long a, long long b, long long m) { return ((a - b) % m + m) % m; }

Cảnh báo bẫy lỗi 2: BẪY TRÀN SỐ 32-BIT KHI NHÂN MODULO

Khi $A, B \approx 10^9$ và $M = 10^9 + 7$, tích $A \times B \approx 10^{18}$. Nếu khai báo biến kiểu int, phép nhân sẽ bị tràn số 32-bit trước khi kịp gọi % M. Luôn ép kiểu sang long long khi nhân.

Khi $M \approx 10^{18}$ (số nguyên 64-bit), tích $A \times B \approx 10^{36}$ sẽ làm tràn cả long long. Khi đó bắt buộc phải dùng Nhân Ấn Độ (Binary Multiplication) hoặc kiểu số nguyên 128-bit __int128_t.

3. Thuật toán lũy thừa nhanh

3.1. Ý tưởng thuật toán chia để trị

Để tính $A^B \bmod M$:

• Thuật toán ngây thơ nhân liên tiếp $B$ lần mất $\mathcal{O}(B)$ phép tính $\implies$ Khi $B = 10^{18}$, thời gian chạy là $10^{18}$ bước ($\approx 30$ năm).
• Lũy thừa nhị phân: Dựa trên tính chất phân rã nhị phân của số mũ: $$A^B = \begin{cases} 1 & \text{khi } B = 0 \\ \left(A^{B/2}\right)^2 & \text{khi } B \text{ chẵn} \\ A \times \left(A^{\lfloor B/2 \rfloor}\right)^2 & \text{khi } B \text{ lẻ} \end{cases}$$ Độ phức tạp giảm xuống chỉ còn $\mathcal{O}(\log_2 B)$ bước (với $B = 10^{18}$ chỉ mất $\approx 60$ phép nhân).

3.2. Bảng mô phỏng phân rã Fast Power: Tính $3^{13} \bmod 1000$

Biểu diễn nhị phân của $B = 13$ là $1101_2 = 8 + 4 + 1$: $$3^{13} = 3^8 \times 3^4 \times 3^1 = 6561 \times 81 \times 3$$

3.3. Cài đặt C++ lũy thừa nhanh chuẩn thi đấu

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

4. Nghịch đảo modulo (Modular Inverse) & Phép chia đồng dư

4.1. Khái niệm nghịch đảo modulo

Trong số học thông thường, phép chia $\frac{A}{B}$ tương đương với phép nhân $A \times B^{-1}$ với $B^{-1} = \frac{1}{B}$.
Trong số học đồng dư, nghịch đảo modulo của $B$ theo modulo $M$ là một số nguyên $X$ thỏa mãn: $$B \times X \equiv 1 \pmod{M}$$ Ký hiệu $X = B^{-1} \bmod M$. Khi đó: $$\frac{A}{B} \bmod M = (A \times B^{-1}) \bmod M$$

Điều kiện tồn tại: Nghịch đảo modulo $B^{-1} \pmod{M}$ tồn tại khi và chỉ khi $\gcd(B, M) = 1$ (hai số nguyên tố cùng nhau).

4.2. Hai phương pháp tìm nghịch đảo modulo

Phương pháp 1: Định lý Fermat nhỏ (Áp dụng khi $M$ là số nguyên tố)

Định lý Fermat nhỏ: Nếu $M$ là số nguyên tố và $B$ không chia hết cho $M$, thì $B^{M-1} \equiv 1 \pmod{M}$.
Nhân cả 2 vế với $B^{-1}$, ta có: $$B^{-1} \equiv B^{M-2} \pmod{M}$$

// Khi M là số nguyên tố (ví dụ 10^9 + 7)
long long modInverse_Fermat(long long b, long long m) {
    return power_mod(b, m - 2, m);
}

Phương pháp 2: Thuật toán Euclid mở rộng (Áp dụng khi $M$ bất kỳ, miễn là $\gcd(B, M) = 1$)

Giải phương trình Diophantine: $B \cdot x + M \cdot y = \gcd(B, M) = 1 \implies B \cdot x \equiv 1 \pmod{M}$. Nghiệm $x$ chính là nghịch đảo modulo:

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long modInverse_Euclid(long long b, long long m) {
    long long x, y;
    long long g = extgcd(b, m, x, y);
    if (g != 1) return -1; // Không tồn tại nghịch đảo
    return (x % m + m) % m;
}

5. Kỹ thuật nâng cao: Tiền xử lý nghịch đảo tuyến tính $\mathcal{O}(N)$

Khi cần tính tổ hợp $C_n^k \bmod M$ hoặc nghịch đảo cho tất cả các số từ $1$ đến $N$ (với $N = 10^6$), nếu dùng Fast Power cho từng số sẽ mất $\mathcal{O}(N \log M)$.
Ta có công thức truy hồi tính nghịch đảo của mọi số $i \in [1, N]$ trong thời gian tuyến tính $\mathcal{O}(N)$: $$\text{inv}[i] = - \lfloor M / i \rfloor \times \text{inv}[M \bmod i] \pmod{M}$$

const int MAXN = 1000000;
long long inv[MAXN + 1];

void precompute_inverses(long long m) {
    inv[1] = 1;
    for (int i = 2; i <= MAXN; ++i) {
        inv[i] = m - (m / i) * inv[m % i] % m;
    }
}

6. Mẫu cài đặt chuẩn thi đấu (Competitive Template)

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

const long long MOD = 1000000007;

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

long long mod_inverse(long long a, long long m = MOD) {
    return power_mod(a, m - 2, m);
}

long long mod_divide(long long a, long long b, long long m = MOD) {
    return (a % m * mod_inverse(b, m)) % m;
}

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

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

    // Tính (a / b) % MOD
    cout << mod_divide(a, b) << "\n";
    return 0;
}

7. Ranh giới áp dụng: Khi nào dùng Fermat vs Euclid mở rộng vs BigInt?