Khóa học CTDL và GT

Bài 4.4: Ứng dụng nghịch đảo modulo trong bài toán tổ hợp

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với các khái niệm cơ bản về modulo và các thuật toán số học như Euclid mở rộng hay lũy thừa modulo, hôm nay chúng ta sẽ cùng nhau khám phá một ứng dụng vô cùng mạnh mẽ của chúng: giải quyết các bài toán tổ hợp mà kết quả cần lấy modulo một số nguyên tố.

Bạn đã bao giờ gặp những bài toán đếm mà số lượng cách quá lớn, vượt xa khả năng lưu trữ của các kiểu dữ liệu thông thường, và đề bài yêu cầu in ra kết quả "modulo 10^9 + 7" hay một số nguyên tố lớn nào đó chưa? Nếu rồi, thì nghịch đảo modulo chính là chìa khóa để bạn "thu nhỏ" các con số khổng lồ đó trong suốt quá trình tính toán mà vẫn giữ được độ chính xác của kết quả cuối cùng!

Vấn đề nan giải: Phép chia trong modulo

Các bài toán tổ hợp thường liên quan đến các khái niệm như hoán vị, chỉnh hợp, và đặc biệt là tổ hợp ($C(n, k)$). Công thức tính tổ hợp $C(n, k)$ quen thuộc là:

$C(n, k) = \frac{n!}{k!(n-k)!}$

Trong đó $n!$ là giai thừa của $n$, tức là tích của các số nguyên từ 1 đến $n$.

Khi $n$ trở nên lớn, $n!$ sẽ tăng trưởng rất nhanh. Ví dụ, $20!$ đã là $2,432,902,008,176,640,000$, một con số khổng lồ! Nếu chúng ta cần tính $C(100, 50)$, giá trị trung gian $100!$, $50!$ sẽ vượt quá sức chứa của hầu hết các kiểu dữ liệu nguyên thủy ngay cả long long.

Vì vậy, yêu cầu "lấy modulo $p$" xuất hiện. Chúng ta cần tính $C(n, k) \pmod{p}$.

Theo tính chất của phép toán modulo, chúng ta có thể áp dụng modulo cho phép cộng, trừ, nhân:

• $(a + b) \pmod{p} = ((a \pmod{p}) + (b \pmod{p})) \pmod{p}$
• $(a - b) \pmod{p} = ((a \pmod{p}) - (b \pmod{p}) + p) \pmod{p}$
• $(a \times b) \pmod{p} = ((a \pmod{p}) \times (b \pmod{p})) \pmod{p}$

Tuy nhiên, không có một phép chia trực tiếp tương tự: $(a / b) \pmod{p}$ không bằng $(a \pmod{p}) / (b \pmod{p})$. Đây chính là vấn đề! Công thức $C(n, k)$ có phép chia cho $k!(n-k)!$. Làm thế nào để thực hiện phép chia này trong thế giới modulo?

Câu trả lời nằm ở nghịch đảo modulo.

Nghịch đảo Modulo là gì?

Nhắc lại một chút kiến thức từ bài trước: Nghịch đảo modulo của một số nguyên $a$ theo modulo $m$, ký hiệu là $a^{-1} \pmod{m}$, là một số nguyên $x$ sao cho:

$a \cdot x \equiv 1 \pmod{m}$

Nói cách khác, nhân $a$ với nghịch đảo modulo của nó tương đương với việc "chia" cho $a$ trong số học modulo $m$.

Nghịch đảo modulo $a^{-1} \pmod{m}$ tồn tại khi và chỉ khi $\gcd(a, m) = 1$. Trong các bài toán tổ hợp, modulo $p$ thường là một số nguyên tố. Khi đó, mọi số nguyên $a$ mà $0 < a < p$ đều có $\gcd(a, p) = 1$, và do đó đều có nghịch đảo modulo theo modulo $p$. Điều này làm cho số học modulo theo số nguyên tố trở nên đặc biệt thuận lợi!

Tính nghịch đảo Modulo bằng Định lý nhỏ Fermat

Khi modulo $p$ là một số nguyên tố, chúng ta có một công cụ mạnh mẽ để tính nghịch đảo modulo: Định lý nhỏ Fermat.

Định lý này phát biểu rằng: Nếu $p$ là một số nguyên tố, và $a$ là một số nguyên không chia hết cho $p$, thì $a^{p-1} \equiv 1 \pmod{p}$.

Từ đó, nếu nhân cả hai vế với $a^{-1}$, ta suy ra: $a^{p-1} \cdot a^{-1} \equiv 1 \cdot a^{-1} \pmod{p}$ $a^{p-2} \equiv a^{-1} \pmod{p}$

Wow! Nghịch đảo modulo của $a$ theo modulo số nguyên tố $p$ (với $a \not\equiv 0 \pmod{p}$) chính là $a^{p-2} \pmod{p}$.

Việc tính $a^{p-2} \pmod{p}$ có thể được thực hiện một cách rất hiệu quả bằng thuật toán lũy thừa modulo (còn gọi là binary exponentiation hay exponentiation by squaring), mà chúng ta đã học trước đó.

Triển khai Lũy thừa Modulo bằng C++

Đây là hàm power (hoặc pow_mod) để tính $base^{exp} \pmod{mod}$:

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod; // Đảm bảo base nằm trong phạm vi modulo

    while (exp > 0) {
        // Nếu exp lẻ, nhân kết quả hiện tại với base
        if (exp % 2 == 1) res = (res * base) % mod;

        // Chia exp cho 2 (bằng cách dịch bit sang phải)
        exp /= 2;
        // Bình phương base
        base = (base * base) % mod;
    }
    return res;
}

• Giải thích code:
  • res: Lưu trữ kết quả lũy thừa hiện tại, khởi tạo bằng 1.
  • base %= mod: Giảm giá trị base xuống phạm vi $[0, mod-1]$ để tránh tràn số trong quá trình tính toán.
  • Vòng lặp while (exp > 0): Duyệt qua các bit của số mũ exp từ phải sang trái.
  • if (exp % 2 == 1): Nếu bit cuối cùng của exp là 1 (tức exp là số lẻ), điều đó có nghĩa là chúng ta cần nhân thêm một lần base vào kết quả. res = (res * base) % mod; thực hiện phép nhân này và lấy modulo ngay lập tức.
  • exp /= 2: Dịch bit của exp sang phải một vị trí, tương đương với chia 2. Chúng ta xử lý bit tiếp theo của số mũ.
  • base = (base * base) % mod: Bình phương base. Nếu exp giảm đi một nửa, thì base cần được bình phương để giá trị biểu thức không đổi (ví dụ $a^8 = (a^4)^2$). Chúng ta cũng lấy modulo ngay sau khi bình phương.
  • Quá trình này tận dụng biểu diễn nhị phân của số mũ để tính toán trong $O(\log \text{exp})$ bước.

Triển khai Nghịch đảo Modulo bằng C++ (sử dụng Fermat)

Áp dụng Định lý nhỏ Fermat, nghịch đảo modulo của n theo modulo mod (với mod là số nguyên tố và n > 0) là n^(mod-2) % mod. Chúng ta chỉ cần gọi hàm power vừa xây dựng:

long long modInverse(long long n, long long mod) {
    // mod phải là số nguyên tố
    // n không chia hết cho mod (n > 0)
    return power(n, mod - 2, mod);
}

• Giải thích code:
  • Hàm này đơn giản chỉ gọi power với cơ số là n, số mũ là mod - 2, và modulo là mod.
  • Lưu ý rằng hàm này chỉ hoạt động chính xác khi mod là số nguyên tố và n không chia hết cho mod.

Ứng dụng tính $C(n, k) \pmod{p}$

Bây giờ chúng ta đã có công cụ nghịch đảo modulo, hãy quay lại với bài toán tính $C(n, k) \pmod{p}$. Công thức: $C(n, k) = \frac{n!}{k!(n-k)!}$

Biến đổi sang dạng nhân bằng cách sử dụng nghịch đảo modulo: $C(n, k) \equiv n! \cdot (k!)^{-1} \cdot ((n-k)! )^{-1} \pmod{p}$

Để tính biểu thức này, chúng ta cần:

1. Tính giai thừa của các số từ 0 đến $n$ modulo $p$.
2. Sử dụng hàm modInverse để tìm nghịch đảo modulo của $k!$ và $(n-k)!$.
3. Nhân $n!$, $(k!)^{-1}$, và $((n-k)! )^{-1}$ lại với nhau, lấy modulo sau mỗi phép nhân để tránh tràn số.

Vì các bài toán thường yêu cầu tính $C(n, k)$ nhiều lần với các cặp $(n, k)$ khác nhau nhưng cùng một modulo $p$ và giới hạn trên $N$ cho $n$, chúng ta có thể tiền xử lý (precompute) mảng giai thừa modulo $p$.

Tiền xử lý Giai thừa Modulo

Chúng ta sẽ tạo một mảng fact (hoặc tên tương tự) để lưu $i! \pmod{p}$ cho $i$ từ 0 đến giới hạn tối đa của $n$ (ví dụ $MAXN$).

#include <vector>

const int MAXN = 100005; // Giới hạn tối đa cho n
long long fact[MAXN];    // Mảng lưu giai thừa modulo

void precompute_factorials(long long mod) {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
}

• Giải thích code:
  • MAXN: Định nghĩa kích thước tối đa của mảng giai thừa.
  • fact[MAXN]: Mảng kiểu long long để lưu giá trị giai thừa modulo.
  • fact[0] = 1: Giai thừa của 0 bằng 1.
  • Vòng lặp: Tính $i! \pmod{mod}$ dựa trên $(i-1)! \pmod{mod}$ đã tính trước đó. fact[i] = (fact[i-1] * i) % mod; thực hiện phép nhân và lấy modulo.

Hàm tính $C(n, k) \pmod{p}$

Bây giờ, với mảng giai thừa đã tiền xử lý và hàm modInverse, chúng ta có thể viết hàm tính $C(n, k) \pmod{p}$.

// Cần có hàm power và modInverse đã định nghĩa ở trên
// Cần có mảng fact đã tiền xử lý bằng precompute_factorials

long long nCr_mod_p(int n, int r, long long mod) {
    // Trường hợp không hợp lệ: r < 0 hoặc r > n
    if (r < 0 || r > n) return 0;
    // Trường hợp đặc biệt: C(n, 0) = C(n, n) = 1
    if (r == 0 || r == n) return 1;
    // Trường hợp: C(n, r) = C(n, n-r), có thể tối ưu tính toán bằng cách chọn min(r, n-r)
    if (r > n / 2) r = n - r;

    // C(n, k) = n! / (k! * (n-k)!)
    // C(n, k) % p = (n! % p * (k!)^(-1) % p * ((n-k)!)^(-1) % p) % p

    long long numerator = fact[n]; // Tử số: n! % mod

    // Mẫu số: k! * (n-k)!
    // Chúng ta cần nghịch đảo modulo của (k! * (n-k)!)
    // (k! * (n-k)!)^(-1) = (k!)^(-1) * ((n-k)!)^(-1) theo tính chất nghịch đảo
    long long denominator = (fact[r] * fact[n - r]) % mod;

    // Kết quả = tử số * nghịch đảo modulo của mẫu số
    return (numerator * modInverse(denominator, mod)) % mod;
}

• Giải thích code:
  • Hàm nhận n, r và mod làm tham số.
  • Xử lý các trường hợp biên: $C(n,k)=0$ nếu $k < 0$ hoặc $k > n$. $C(n,k)=1$ nếu $k=0$ hoặc $k=n$.
  • Tối ưu nhỏ: $C(n, k) = C(n, n-k)$. Nếu $k > n/2$, chúng ta có thể thay thế $k$ bằng $n-k$ để làm việc với số nhỏ hơn (mặc dù với cách tính này không khác biệt nhiều về hiệu quả, nhưng là một tính chất hữu ích).
  • numerator = fact[n]: Lấy giai thừa của $n$ đã được tính modulo $p$ từ mảng fact.
  • denominator = (fact[r] * fact[n - r]) % mod: Tính mẫu số $k!(n-k)!$ modulo $p$.
  • modInverse(denominator, mod): Tìm nghịch đảo modulo của mẫu số theo modulo $p$.
  • (numerator * modInverse(denominator, mod)) % mod: Nhân tử số với nghịch đảo modulo của mẫu số và lấy modulo lần cuối để có kết quả cuối cùng.

Ví dụ minh họa đầy đủ bằng C++

Giả sử chúng ta cần tính $C(5, 2) \pmod{10^9 + 7}$ và $C(10, 3) \pmod{10^9 + 7}$. $10^9 + 7$ là một số nguyên tố phổ biến trong các bài competitive programming.

#include <iostream>
#include <vector>

const int MAXN = 100005; // Giới hạn tối đa cho n
const long long MOD = 1e9 + 7; // Modulo là số nguyên tố

long long fact[MAXN];    // Mảng lưu giai thừa modulo

// Hàm lũy thừa modulo (binary exponentiation)
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        exp /= 2;
        base = (base * base) % MOD;
    }
    return res;
}

// Hàm nghịch đảo modulo sử dụng Fermat's Little Theorem
long long modInverse(long long n) {
    // Đối với modulo P nguyên tố, nghịch đảo của n là n^(P-2) mod P
    return power(n, MOD - 2);
}

// Tiền xử lý giai thừa modulo
void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
}

// Hàm tính C(n, k) modulo p
long long nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) return 0;
    if (r == 0 || r == n) return 1;
    if (r > n / 2) r = n - r; // Tối ưu nhỏ

    // C(n, r) = n! * (r!)^(-1) * ((n-r)!)^(-1) mod p
    long long numerator = fact[n];
    long long denominator = (fact[r] * fact[n - r]) % MOD;

    // Nhân tử số với nghịch đảo modulo của mẫu số
    return (numerator * modInverse(denominator)) % MOD;
}

int main() {
    // Bước 1: Tiền xử lý giai thừa
    precompute_factorials();

    // Bước 2: Sử dụng hàm nCr_mod_p để tính toán
    int n1 = 5, r1 = 2;
    long long result1 = nCr_mod_p(n1, r1);
    // C(5, 2) = 5! / (2! * 3!) = 120 / (2 * 6) = 120 / 12 = 10
    // 10 % (10^9 + 7) = 10
    std::cout << "C(" << n1 << ", " << r1 << ") mod " << MOD << " = " << result1 << std::endl;

    int n2 = 10, r2 = 3;
    long long result2 = nCr_mod_p(n2, r2);
    // C(10, 3) = 10! / (3! * 7!) = (10 * 9 * 8) / (3 * 2 * 1) = 10 * 3 * 4 = 120
    // 120 % (10^9 + 7) = 120
    std::cout << "C(" << n2 << ", " << r2 << ") mod " << MOD << " = " << result2 << std::endl;

    int n3 = 100, r3 = 50; // C(100, 50) là số rất lớn
    long long result3 = nCr_mod_p(n3, r3);
    // Giá trị C(100, 50) thực tế cực lớn, nhưng kết quả modulo thì nhỏ gọn
    std::cout << "C(" << n3 << ", " << r3 << ") mod " << MOD << " = " << result3 << std::endl;

    // Ví dụ với n lớn hơn
    int n4 = 100000, r4 = 100;
     long long result4 = nCr_mod_p(n4, r4);
    std::cout << "C(" << n4 << ", " << r4 << ") mod " << MOD << " = " << result4 << std::endl;


    return 0;
}

• Giải thích các hàm:

  • power(base, exp): Tính base^exp % MOD.
  • modInverse(n): Tính nghịch đảo modulo của n theo MOD. Sử dụng power(n, MOD - 2).
  • precompute_factorials(): Tính trước giai thừa từ 0 đến MAXN-1 modulo MOD và lưu vào mảng fact. Chỉ cần chạy một lần duy nhất lúc đầu.
  • nCr_mod_p(n, r): Tính $C(n, r) \pmod{MOD}$ sử dụng mảng fact đã tiền xử lý và hàm modInverse.

• Giải thích main:

  • Đầu tiên và quan trọng nhất, gọi precompute_factorials() để chuẩn bị dữ liệu giai thừa.
  • Sau đó, chúng ta có thể gọi nCr_mod_p bao nhiêu lần tùy ý với bất kỳ cặp $(n, r)$ nào trong phạm vi MAXN.
  • Các ví dụ được in ra để kiểm tra kết quả. C(100, 50) và C(100000, 100) minh họa cho việc thuật toán này hoạt động ngay cả với các giá trị $n$ rất lớn mà tính toán thông thường sẽ không thể thực hiện được.

• Hiệu năng:

  • Bước tiền xử lý giai thừa: $O(MAXN)$.
  • Mỗi lần tính $C(n, k) \pmod{p}$:
    • Truy cập mảng fact: $O(1)$.
    • Tính modInverse: $O(\log MOD)$ do dùng lũy thừa modulo.
  • Tổng cộng, sau khi tiền xử lý, mỗi lần tính $C(n, k) \pmod{p}$ chỉ mất $O(\log MOD)$ thời gian. Nếu MOD cố định, có thể coi là $O(1)$ cho mỗi truy vấn $C(n, k)$. Đây là một hiệu quả đáng kinh ngạc so với việc cố gắng tính toán trực tiếp.

Một ứng dụng khác: Bài toán đếm đường đi trên lưới

Xét bài toán: Có bao nhiêu đường đi ngắn nhất từ điểm $(0, 0)$ đến điểm $(x, y)$ trên một lưới hình chữ nhật, chỉ được phép di chuyển sang phải hoặc lên trên?

Để đi từ $(0, 0)$ đến $(x, y)$ chỉ bằng cách di chuyển sang phải (R) và lên trên (U), chúng ta cần tổng cộng $x$ bước sang phải và $y$ bước lên trên. Tổng số bước là $x + y$. Bất kỳ chuỗi nào gồm $x$ ký tự 'R' và $y$ ký tự 'U' đều tương ứng với một đường đi duy nhất.

Số lượng các chuỗi như vậy chính là số cách chọn vị trí cho $x$ ký tự 'R' trong tổng số $x+y$ vị trí, hoặc tương đương, số cách chọn vị trí cho $y$ ký tự 'U' trong $x+y$ vị trí.

Đây chính xác là bài toán tổ hợp $C(x+y, x)$ (hoặc $C(x+y, y)$).

Nếu bài toán yêu cầu kết quả modulo một số nguyên tố $p$, chúng ta có thể trực tiếp sử dụng hàm nCr_mod_p đã xây dựng!

#include <iostream>
#include <vector>

// Sử dụng lại các hàm power, modInverse, precompute_factorials, fact, MOD
// đã định nghĩa ở ví dụ trước

const int MAXN = 100005; // Giới hạn cho x+y
const long long MOD = 1e9 + 7; // Modulo

long long fact[MAXN];

long long power(long long base, long long exp) {
    // ... (Code như trên) ...
    long long res = 1; base %= MOD;
    while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; exp /= 2; base = (base * base) % MOD; }
    return res;
}

long long modInverse(long long n) {
    // ... (Code như trên) ...
    return power(n, MOD - 2);
}

void precompute_factorials() {
    // ... (Code như trên) ...
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) fact[i] = (fact[i - 1] * i) % MOD;
}

long long nCr_mod_p(int n, int r) {
    // ... (Code như trên) ...
    if (r < 0 || r > n) return 0;
    if (r == 0 || r == n) return 1;
    if (r > n / 2) r = n - r;
    long long numerator = fact[n];
    long long denominator = (fact[r] * fact[n - r]) % MOD;
    return (numerator * modInverse(denominator)) % MOD;
}


int main() {
    precompute_factorials(); // Cần tiền xử lý

    int x = 2, y = 3; // Đi từ (0,0) đến (2,3)
    // Cần 2 bước R và 3 bước U, tổng 5 bước. C(5, 2) hoặc C(5, 3)
    int n_grid = x + y;
    int k_grid = x; // hoặc y

    long long paths = nCr_mod_p(n_grid, k_grid);
    // C(5, 2) = 10
    std::cout << "So duong di tu (0,0) den (" << x << "," << y << ") mod " << MOD << " = " << paths << std::endl; // Kết quả là 10

    x = 5, y = 5; // Đi từ (0,0) đến (5,5)
    // Cần 5 bước R và 5 bước U, tổng 10 bước. C(10, 5)
    n_grid = x + y;
    k_grid = x;

    paths = nCr_mod_p(n_grid, k_grid);
    // C(10, 5) = 10! / (5! 5!) = (10*9*8*7*6) / (5*4*3*2*1) = 252
    std::cout << "So duong di tu (0,0) den (" << x << "," << y << ") mod " << MOD << " = " << paths << std::endl; // Kết quả là 252

    x = 50000, y = 50000; // Điểm rất xa
    n_grid = x + y; // n = 100000
    k_grid = x;       // k = 50000

    paths = nCr_mod_p(n_grid, k_grid);
    // C(100000, 50000) mod (10^9 + 7) - đây là số rất lớn
    std::cout << "So duong di tu (0,0) den (" << x << "," << y << ") mod " << MOD << " = " << paths << std::endl; // Kết quả sẽ là C(100000, 50000) % MOD


    return 0;
}

• Giải thích code:
  • Chúng ta tái sử dụng các hàm power, modInverse, precompute_factorials, và nCr_mod_p đã xây dựng.
  • Hàm main thể hiện cách áp dụng. Với điểm đến $(x, y)$, tổng số bước là $x+y$ (n_grid), và số bước phải là sang phải (hoặc lên trên) là $x$ (hoặc $y$) (k_grid). Bài toán quy về tính $C(x+y, x) \pmod{MOD}$.
  • Ví dụ cuối cùng với $(50000, 50000)$ cho thấy khả năng xử lý các bài toán lưới lớn một cách hiệu quả.

Khi nào có thể áp dụng?

Phương pháp sử dụng nghịch đảo modulo bằng Định lý nhỏ Fermat để tính $C(n, k) \pmod{p}$ là hiệu quả nhất khi:

1. Modulo $p$ là một số nguyên tố.
2. $p$ không quá nhỏ (lớn hơn $n$), để các giai thừa $n!, k!, (n-k)!$ không chia hết cho $p$. Điều này đảm bảo nghịch đảo modulo tồn tại và công thức $a^{p-2} \equiv a^{-1} \pmod{p}$ đúng.

Nếu modulo $m$ không phải là số nguyên tố, hoặc nếu $m$ là số nguyên tố nhưng $n \ge p$ (dẫn đến $n!$ chia hết cho $p$), chúng ta cần các phương pháp phức tạp hơn (ví dụ: Lucas Theorem cho modulo nguyên tố nhỏ, hoặc phân tích thừa số nguyên tố cho modulo tổng quát). Tuy nhiên, phần lớn các bài competitive programming ở mức độ cơ bản và trung bình đều sử dụng modulo nguyên tố lớn, nơi phương pháp này là cứu cánh.

Bài tập ví dụ:

Số lượng chữ số 0

Trong một buổi phỏng vấn đặc biệt, FullHouse Dev có cơ hội gặp gỡ nhà toán học nổi tiếng Euler. Ông đã đưa ra một bài toán thú vị về việc đếm số lượng chữ số 0 ở cuối của một giai thừa.

Bài toán

Cho một số nguyên \(N\). Nhiệm vụ của bạn là tìm ra số lượng chữ số 0 ở cuối của \(N!\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(N\).

OUTPUT FORMAT:

• Với mỗi test case, in ra một số nguyên trên một dòng - số lượng chữ số 0 ở cuối của \(N!\).

Ràng buộc:

• \(T \leq 1000\)
• \(0 \leq N \leq 10^{11}\)

Ví dụ

INPUT

3
9
11
20

OUTPUT

1
2
4

Giải thích

• Với \(N = 9\), ta có \(9! = 362880\), kết thúc bằng 1 chữ số 0.
• Với \(N = 11\), ta có \(11! = 39916800\), kết thúc bằng 2 chữ số 0.
• Với \(N = 20\), ta có \(20!\) kết thúc bằng 4 chữ số 0. Tuyệt vời, đây là hướng dẫn giải ngắn gọn cho bài toán này bằng C++:

1. Hiểu vấn đề: Số lượng chữ số 0 ở cuối của N! được tạo ra bởi các thừa số 10 trong tích. Vì 10 = 2 * 5, số lượng chữ số 0 chính là số cặp thừa số nguyên tố (2, 5) trong phân tích nguyên tố của N!.

2. Đếm thừa số: Trong tích 1 2 3 ... N, thừa số 2 xuất hiện thường xuyên hơn thừa số 5. Do đó, số cặp (2, 5) bị giới hạn bởi số lượng thừa số 5. Nhiệm vụ quy về đếm số lượng thừa số 5 trong N!.

3. Công thức Legendre: Số lượng thừa số của một số nguyên tố $p$ trong N! được tính bằng công thức: $E_p(N!) = \lfloor N/p \rfloor + \lfloor N/p^2 \rfloor + \lfloor N/p^3 \rfloor + \dots$ Áp dụng cho $p=5$, số lượng chữ số 0 ở cuối N! là: $\lfloor N/5 \rfloor + \lfloor N/25 \rfloor + \lfloor N/125 \rfloor + \dots$ Tổng này tiếp tục cho đến khi lũy thừa của 5 lớn hơn N (khi đó $\lfloor N/\text{lũy thừa của 5} \rfloor$ sẽ bằng 0).

4. Thuật toán:

   • Khởi tạo biến đếm số 0 (ví dụ: count) bằng 0.
   • Khởi tạo biến power_of_5 bằng 5.
   • Lặp:
     • Thêm N / power_of_5 vào count (sử dụng phép chia nguyên).
     • Nhân power_of_5 với 5.
     • Lặp lại chừng nào N / power_of_5 còn lớn hơn 0.

5. Lưu ý kiểu dữ liệu: Vì N có thể lên tới $10^{11}$, cần sử dụng kiểu dữ liệu hỗ trợ số lớn như long long trong C++ để lưu trữ N và các biến tính toán (như power_of_5 và count) nhằm tránh tràn số.

Làm thêm nhiều bài tập miễn phí tại đây