📘

🎓. PHÉP TOÁN MODULO & NGHỊCH ĐẢO MODULO

Làm việc với số lớn, tránh tràn số, hiểu và sử dụng nghịch đảo modulo trong các bài toán số học và tổ hợp.

Number Theory Competitive Programming Modulo & Inverse

Mục tiêu bài học

Hiểu cách biểu diễn số lớn bằng phần dư modulo.
Thực hiện chính xác các phép toán: cộng, trừ, nhân, lũy thừa trong modulo.
Biết khi nào nghịch đảo modulo tồn tại và cách tính.
Áp dụng modulo trong các dạng bài lập trình như:
- Tính lũy thừa lớn
- Tính phân số modulo
- Tính tổ hợp (nCk)
- Giải phương trình dạng ax ≡ b (mod m)

I. Khái niệm modulo

Một số nguyên có thể được viết dưới dạng:

a = k · MOD + d, trong đó:
– d là phần dư khi chia a cho MOD
– 0 ≤ d < MOD

Khi làm việc với số rất lớn, ta chỉ lưu phần dư d. Đây chính là ý nghĩa của việc tránh tràn số bằng modulo.

Ví dụ: Tính (123456789 × 987654321) % 1e9+7
– Không nhân trực tiếp (tràn 64-bit)
– Tính lần lượt:

123456789 % MOD
987654321 % MOD
Nhân & lấy mod tiếp

II. TẠI SAO PHẢI DÙNG MODULO?

1. Tránh tràn số

Ví dụ: cần tính 10¹⁰⁰⁰ trong chương trình. Giá trị này có tới 1001 chữ số, không thể lưu vào bất kỳ kiểu dữ liệu thông thường nào.

Nhưng nếu bài toán yêu cầu:

10¹⁰⁰⁰ % 1,000,000,007

thì ta có thể dùng lũy thừa nhanh modulo để tính được, mà không cần lưu giá trị đầy đủ của 10¹⁰⁰⁰.

2. Giảm độ lớn, tối ưu tính toán

Trong các bài toán đếm, tổ hợp, số cách, kết quả thường rất lớn. Ta chỉ cần kết quả theo một modulo, chẳng hạn 1,000,000,007, nên luôn có thể “co” giá trị về trong khoảng [0, MOD-1].

3. Giữ lại phần dư d thay cho a

Về bản chất, trong thế giới modulo, ta thay mỗi số a bằng phần dư d = a % MOD, vì:

a ≡ d (mod MOD)

Ta làm việc với lớp dư, không phải giá trị gốc.

III. CÁC TÍNH CHẤT CƠ BẢN CỦA MODULO

1. Cộng

(a + b) % MOD = (a % MOD + b % MOD) % MOD

2. Trừ

(a - b) % MOD = (a % MOD - b % MOD + MOD) % MOD

Thêm + MOD để tránh số âm.

3. Nhân

(a * b) % MOD = ((a % MOD) * (b % MOD)) % MOD

4. Lũy thừa

Muốn tính a^k % MOD với k rất lớn, ta dùng lũy thừa nhanh (binary exponentiation) để đạt độ phức tạp O(log k).

IV. Lũy thừa nhanh (Binary Exponentiation)

Bài toán: Tính aⁿ mod MOD với n rất lớn (n lên đến 10¹⁸ hoặc 10¹⁰⁰⁰).

Ý tưởng:

Dựa trên phân tích nhị phân của số mũ n.
Một số n được biểu diễn dạng nhị phân ⇒ chỉ cần nhân những lũy thừa a^{2^k} tương ứng.
Mỗi bước chia đôi số mũ ⇒ thời gian O(log n).

Ví dụ minh họa

Tính 3¹³ mod 1000

13 = (1101)₂ = 8 + 4 + 1

⇒ 3¹³ = 3⁸ × 3⁴ × 3¹
⇒ mỗi lũy thừa được tính bằng bình phương liên tiếp.

Cài đặt C++

C++

long long modpow(long long a, long long e, long long MOD) {
    long long r = 1;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

Cài đặt Python

Python

def modpow(a, e, MOD):
    r = 1
    a %= MOD
    while e > 0:
        if e & 1:
            r = r * a % MOD
        a = a * a % MOD
        e //= 2
    return r

V. VÌ SAO MODULO KHÔNG CÓ PHÉP CHIA TRỰC TIẾP?

Trong modulo, biểu thức:

a / b % MOD

không có nghĩa rõ ràng.

Thay vào đó, ta dùng ý tưởng:

a / b (mod MOD)  ≈  a * inv(b) (mod MOD)

Trong đó inv(b) là nghịch đảo của b theo modulo MOD (nếu tồn tại).

VI. Nghịch đảo modulo

Trong modulo, phép chia không tồn tại theo nghĩa thông thường.
Để thực hiện phép chia, ta phải chuyển nó thành phép nhân với nghịch đảo modulo.

Định nghĩa:
Với a và MOD, nghịch đảo modulo của a là số x sao cho:

a × x ≡ 1 (mod MOD)

Khi đó:

a / b mod MOD = a × inv(b) mod MOD

Khi nào nghịch đảo tồn tại?

Nghịch đảo của a theo MOD tồn tại ⇔ gcd(a, MOD) = 1.
Nếu MOD là số nguyên tố (như 10⁹+7), mọi số 1 ≤ a < MOD đều có nghịch đảo.

1. Nghịch đảo modulo khi MOD là số nguyên tố (Fermat nhỏ)

Dựa trên định lý Fermat nhỏ:

a^MOD−1 ≡ 1 (mod MOD)
⇒ a × a^MOD−2 ≡ 1 (mod MOD)

Do đó nghịch đảo của a là:

inv(a) = a^MOD−2 mod MOD

C++

const long long MOD = 1000000007;

long long modpow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

long long modinv(long long a) {
    return modpow(a, MOD - 2);
}

Python

MOD = 10**9 + 7

def modpow(a, e):
    r = 1
    a %= MOD
    while e:
        if e & 1:
            r = r * a % MOD
        a = a * a % MOD
        e //= 2
    return r

def modinv(a):
    return modpow(a, MOD - 2)

2. Nghịch đảo modulo khi MOD không nguyên tố — Euclid mở rộng

Giải phương trình:

a·x + MOD·y = 1

Khi đó x chính là nghịch đảo của a theo MOD. Điều kiện tồn tại: gcd(a, MOD) = 1.

C++ — Euclid mở rộng

C++

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 - y1 * (a / b);
    return g;
}

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

Python — Euclid mở rộng

Python

def extgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = extgcd(b, a % b)
    return g, y1, x1 - y1 * (a // b)

def modinv_general(a, MOD):
    g, x, y = extgcd(a, MOD)
    if g != 1:
        return None  # không tồn tại nghịch đảo
    return x % MOD

3. Ví dụ minh họa

Ví dụ 1: Tìm nghịch đảo của 5 theo MOD = 1,000,000,007.

inv(5) = 5^MOD−2 mod MOD = 5^1000000005 mod MOD
Kết quả: 400000003.

Ví dụ 2: Tìm nghịch đảo của 7 theo MOD = 1000.

gcd(7, 1000) = 1 ⇒ nghịch đảo tồn tại.
Giải: 7x + 1000y = 1
Ta được x = 143 ⇒ inv(7) = 143 mod 1000.

4. Ứng dụng thực tế của nghịch đảo modulo

Tính phân số modulo:
a / b mod MOD = a × inv(b)
Tính tổ hợp C(n, k) modulo: C(n,k) = n! × inv(k!) × inv((n−k)!) mod MOD
Giải phương trình tuyến tính: ax ≡ b (mod m) ⇒ x = b × inv(a)
Nhân chia trong FFT, NTT, phép biến đổi số học.

VII. Bài tập vận dụng

Bài 1. Tính a^b mod 1e9+7

Input: a, b (k có thể tới 10¹⁸)
Output: a^b mod 1e9+7

Làm bài: click vào đây

Bài 2. Hãy đưa ra hai chữ số tận cùng của 7^N

Input: Số nguyên N (0 ≤ N ≤ 10⁹)
Output: Số nguyên duy nhất là hai chữ số tận cùng của 7^N

Làm bài: click vào đây

Bài 3. Tìm nghịch đảo của a theo MOD

Input: a, MOD
Output: inv(a) hoặc -1 nếu không tồn tại

Gợi ý: Nếu MOD nguyên tố → dùng a^MOD−2 mod MOD.
Nếu MOD không nguyên tố → dùng Euclid mở rộng.

Bài 4. Tính phân số modulo

Input: a, b, MOD
Output: (a / b) mod MOD

Gợi ý: Tính inv(b), sau đó a × inv(b).

Bài 5. Giải phương trình a·x ≡ b (mod m)

Input: a, b, m
Output: x nếu tồn tại, ngược lại -1

Gợi ý: x = b × inv(a) (chỉ khi gcd(a, m) = 1).

Bài 6. Tính C(n, k) mod 1e9+7

Input: n, k ≤ 2×10⁶
Output: C(n, k) mod 1e9+7

Gợi ý: Tiền xử lý factorial và inverse factorial.

Bài 7. Tổng bảng số

Làm bài: click vào đây

Bài 8. Tính 2^N mod 1e9+7 với N có 10⁵ chữ số

Input: N dạng chuỗi
Output: 2^N mod MOD

Gợi ý: Dùng phương pháp "mod mũ từ chuỗi":

pow = (pow × 10 + (digit−'0')) % (MOD−1)

Bài 9. Phép chia đa thức modulo (ứng dụng nghịch đảo)

Input: a, b
Output: a × inv(b) mod 1e9+7

Ứng dụng thường gặp trong FFT/NTT.

Bài 10. Kiểm tra hai số có đồng dư modulo m

Input: a, b, m
Output: YES hoặc NO

Gợi ý: Kiểm tra (a − b) % m == 0.