Khóa học CTDL và GT

Bài 4.1. Nghịch đảo modulo và phương pháp tính

Trong thế giới quen thuộc của số học thông thường, phép chia là một thao tác cơ bản và dễ dàng. Để chia a cho b, chúng ta chỉ cần tìm một số x sao cho b * x = a. Nhưng khi bước chân vào thế giới kỳ diệu của số học đồng dư (modular arithmetic), khái niệm phép chia không còn đơn giản như vậy. Thay vào đó, chúng ta sử dụng một khái niệm tương đương và cực kỳ quan trọng: nghịch đảo modulo.

Nghịch đảo modulo không chỉ là một khái niệm toán học thuần túy; nó là chìa khóa để giải quyết nhiều bài toán phức tạp trong lập trình thi đấu, mật mã học (như thuật toán RSA) và các lĩnh vực khoa học máy tính khác.

Bài viết này sẽ đi sâu vào khái niệm nghịch đảo modulo, điều kiện để nó tồn tại và các phương pháp hiệu quả nhất để tính toán nó, cùng với các ví dụ minh họa chi tiết bằng ngôn ngữ C++.

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

Trong số học đồng dư modulo m, nghịch đảo modulo của một số nguyên a (nếu tồn tại) là một số nguyên x sao cho tích của a và x là đồng dư với 1 modulo m. Nói cách khác, chúng ta tìm x sao cho:

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

Điều này có nghĩa là a * x khi chia cho m sẽ có số dư là 1.

Ví dụ: Tìm nghịch đảo modulo của 3 modulo 11. Chúng ta cần tìm x sao cho 3 * x ≡ 1 (mod 11). Thử các giá trị của x:

• x = 1: 3 * 1 = 3 ≡ 3 (mod 11)
• x = 2: 3 * 2 = 6 ≡ 6 (mod 11)
• x = 3: 3 * 3 = 9 ≡ 9 (mod 11)
• x = 4: 3 * 4 = 12 ≡ 1 (mod 11) - Bingo!

Vậy, nghịch đảo modulo của 3 modulo 11 là 4. Chúng ta ký hiệu là $3^{-1} \equiv 4 \pmod{11}$.

Điều kiện tồn tại:

Nghịch đảo modulo của a modulo m chỉ tồn tại khi và chỉ khi a và m là nguyên tố cùng nhau (coprime). Điều này có nghĩa là ước số chung lớn nhất (GCD - Greatest Common Divisor) của a và m phải bằng 1:

$\text{gcd}(a, m) = 1$

Tại sao lại như vậy? Nếu $\text{gcd}(a, m) = d > 1$, thì ax + my luôn chia hết cho d với mọi số nguyên x, y. Cụ thể, ax chia hết cho d (vì a chia hết cho d), my chia hết cho d (vì m chia hết cho d), nên ax + my chia hết cho d. Nếu tồn tại x sao cho a * x ≡ 1 (mod m), điều này tương đương với việc tồn tại số nguyên k sao cho a * x - 1 = k * m, hay a * x - k * m = 1. Vế trái a * x - k * m chia hết cho d (vì a và m đều chia hết cho d), nhưng vế phải là 1 lại không chia hết cho d (vì d > 1). Điều này dẫn đến mâu thuẫn. Do đó, nếu $\text{gcd}(a, m) > 1$, nghịch đảo modulo không tồn tại.

Ví dụ: Tìm nghịch đảo modulo của 2 modulo 4. $\text{gcd}(2, 4) = 2$. Vì GCD > 1, nghịch đảo modulo của 2 modulo 4 không tồn tại. Thử kiểm tra:

• x = 0: 2 * 0 = 0 ≡ 0 (mod 4)
• x = 1: 2 * 1 = 2 ≡ 2 (mod 4)
• x = 2: 2 * 2 = 4 ≡ 0 (mod 4)
• x = 3: 2 * 3 = 6 ≡ 2 (mod 4) Không có giá trị nào của x trong khoảng [0, 3] thỏa mãn 2 * x ≡ 1 (mod 4).

2. Các phương pháp tính Nghịch đảo Modulo

Sau khi hiểu khái niệm và điều kiện tồn tại, chúng ta cần biết cách tính toán nó một cách hiệu quả. Có một số phương pháp, tùy thuộc vào tính chất của modulo m.

Phương pháp 1: Thử vét cạn (Brute Force)

Đây là phương pháp đơn giản nhất để hiểu. Nếu nghịch đảo modulo của a modulo m tồn tại, nó sẽ nằm trong khoảng $[0, m-1]$. Chúng ta có thể thử lần lượt các giá trị x = 0, 1, 2, ..., m-1 và kiểm tra xem (a * x) % m == 1 hay không.

#include <iostream>

long long modInverseBruteForce(long long a, long long m) {
    // Đảm bảo a nằm trong khoảng [0, m-1]
    a = (a % m + m) % m;

    for (long long x = 0; x < m; ++x) {
        if ((a * x) % m == 1) {
            return x; // Tìm thấy nghịch đảo
        }
    }

    return -1; // Nghịch đảo không tồn tại
}

int main() {
    long long a = 3, m = 11;
    long long inverse = modInverseBruteForce(a, m);
    if (inverse != -1) {
        std::cout << "Nghich dao cua " << a << " mod " << m << " la: " << inverse << std::endl; // Output: 4
    } else {
        std::cout << "Nghich dao cua " << a << " mod " << m << " khong ton tai." << std::endl;
    }

    a = 2; m = 4;
    inverse = modInverseBruteForce(a, m);
    if (inverse != -1) {
        std::cout << "Nghich dao cua " << a << " mod " << m << " la: " << inverse << std::endl;
    } else {
        std::cout << "Nghich dao cua " << a << " mod " << m << " khong ton tai." << std::endl; // Output: khong ton tai
    }

    return 0;
}

Giải thích Code Brute Force: Hàm modInverseBruteForce nhận hai số a và m. Đầu tiên, a = (a % m + m) % m; đảm bảo a nằm trong phạm vi $[0, m-1]$ ngay cả khi a ban đầu là số âm hoặc lớn hơn m. Vòng lặp for duyệt qua tất cả các giá trị x từ 0 đến m-1. Trong mỗi lần lặp, nó kiểm tra điều kiện (a * x) % m == 1. Nếu đúng, x chính là nghịch đảo và hàm trả về x. Nếu vòng lặp kết thúc mà không tìm thấy x nào thỏa mãn, điều đó có nghĩa là nghịch đảo không tồn tại, và hàm trả về -1.

Nhược điểm: Phương pháp này cực kỳ chậm nếu m lớn, vì độ phức tạp thuật toán là O(m). Chúng ta cần các phương pháp hiệu quả hơn cho các bài toán thực tế.

Phương pháp 2: Sử dụng Thuật toán Euclid mở rộng (Extended Euclidean Algorithm)

Đây là phương pháp mạnh mẽ và tổng quát nhất để tìm nghịch đảo modulo. Nó hoạt động khi m là số nguyên tố hoặc hợp số, miễn là $\text{gcd}(a, m) = 1$.

Nhắc lại Thuật toán Euclid mở rộng: Đối với hai số nguyên a và b bất kỳ, Thuật toán Euclid mở rộng tìm các số nguyên x và y sao cho: $ax + by = \text{gcd}(a, b)$

Bây giờ, áp dụng điều này vào bài toán nghịch đảo modulo a modulo m. Chúng ta cần tìm x sao cho $ax \equiv 1 \pmod m$. Điều này tương đương với việc tìm x và số nguyên k sao cho: $ax - km = 1$ So sánh với phương trình của Thuật toán Euclid mở rộng ax + my = \text{gcd}(a, m): Nếu $\text{gcd}(a, m) = 1$, phương trình trở thành: $ax + my = 1$

Thuật toán Euclid mở rộng có thể tìm được các giá trị x và y cho phương trình này. Giá trị x mà thuật toán tìm được chính là nghịch đảo modulo của a modulo m! (Lưu ý: y không quan trọng trong việc tìm nghịch đảo).

Cách hoạt động của Thuật toán Euclid mở rộng (phiên bản đệ quy):

Base case: Khi b = 0, $\text{gcd}(a, 0) = a$. Ta có phương trình ax + 0y = a. Chọn x = 1, y = 0 là một giải pháp.

Recursive step: Giả sử chúng ta đã gọi đệ quy cho (b, a % b) và tìm được các giá trị x', y' sao cho: $bx' + (a \pmod b)y' = \text{gcd}(b, a \pmod b)$

Theo Thuật toán Euclid thông thường, $\text{gcd}(a, b) = \text{gcd}(b, a \pmod b)$. Ta biết $a \pmod b = a - \lfloor a/b \rfloor \cdot b$. Thay vào phương trình trên: $bx' + (a - \lfloor a/b \rfloor \cdot b)y' = \text{gcd}(a, b)$ $bx' + ay' - \lfloor a/b \rfloor \cdot by' = \text{gcd}(a, b)$ $ay' + b(x' - \lfloor a/b \rfloor y') = \text{gcd}(a, b)$

So sánh với phương trình ban đầu $ax + by = \text{gcd}(a, b)$, ta thấy: $x = y'$ $y = x' - \lfloor a/b \rfloor y'$

Vậy, nếu ta có giải pháp $(x', y')$ cho (b, a % b), ta có thể tính giải pháp $(x, y)$ cho (a, b).

Triển khai bằng C++:

Đầu tiên, cài đặt hàm Thuật toán Euclid mở rộng:

#include <iostream>

// Hàm tính Thuật toán Euclid mở rộng
// Tìm x, y sao cho a*x + b*y = gcd(a, b)
long long extendedGcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a; // gcd(a, 0) = a
    }

    long long x1, y1;
    long long gcd = extendedGcd(b, a % b, x1, y1);

    // Cập nhật x và y sử dụng kết quả đệ quy
    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

// Hàm tìm nghịch đảo modulo bằng Thuật toán Euclid mở rộng
long long modInverseEuclidean(long long a, long long m) {
    long long x, y;
    long long g = extendedGcd(a, m, x, y);

    if (g != 1) {
        // Nghịch đảo không tồn tại nếu gcd(a, m) != 1
        return -1;
    } else {
        // x là một giải pháp cho a*x + m*y = 1
        // Ta cần nghịch đảo trong khoảng [0, m-1].
        // Nếu x âm, thêm m để đưa nó vào khoảng dương.
        // Biểu thức (x % m + m) % m đảm bảo kết quả luôn dương và trong [0, m-1].
        return (x % m + m) % m;
    }
}

int main() {
    long long a = 3, m = 11;
    long long inverse = modInverseEuclidean(a, m);
    if (inverse != -1) {
        std::cout << "Nghich dao cua " << a << " mod " << m << " la: " << inverse << std::endl; // Output: 4
    } else {
        std::cout << "Nghich dao cua " << a << " mod " << m << " khong ton tai." << std::endl;
    }

    a = 10, m = 17; // gcd(10, 17) = 1
    inverse = modInverseEuclidean(a, m);
     if (inverse != -1) {
        std::cout << "Nghich dao cua " << a << " mod " << m << " la: " << inverse << std::endl; // Output: 12 (10 * 12 = 120; 120 % 17 = 1)
    } else {
        std::cout << "Nghich dao cua " << a << " mod " << m << " khong ton tai." << std::endl;
    }

    a = 6, m = 9; // gcd(6, 9) = 3 != 1
    inverse = modInverseEuclidean(a, m);
     if (inverse != -1) {
        std::cout << "Nghich dao cua " << a << " mod " << m << " la: " << inverse << std::endl;
    } else {
        std::cout << "Nghich dao cua " << a << " mod " << m << " khong ton tai." << std::endl; // Output: khong ton tai
    }

    return 0;
}

Giải thích Code Thuật toán Euclid mở rộng: Hàm extendedGcd(a, b, x, y):

• Là một hàm đệ quy. Nhận a, b và hai tham chiếu x, y để trả về kết quả.
• Trường hợp cơ sở if (b == 0): Khi b bằng 0, gcd(a, 0) = a. Phương trình ax + by = gcd(a, b) trở thành ax + 0y = a. Một giải pháp đơn giản là x = 1, y = 0. Hàm trả về a (là GCD).
• Bước đệ quy: Gọi đệ quy cho extendedGcd(b, a % b, x1, y1). Hàm này sẽ tìm x1, y1 sao cho b * x1 + (a % b) * y1 = gcd(b, a % b).
• Cập nhật x, y: Sử dụng công thức suy luận từ bước đệ quy ($x = y1$, $y = x1 - \lfloor a/b \rfloor y1$), ta tính được x và y cho lời gọi hiện tại extendedGcd(a, b, x, y).
• Hàm trả về gcd(a, b) (giá trị trả về từ lời gọi đệ quy cuối cùng).

Hàm modInverseEuclidean(a, m):

• Gọi extendedGcd(a, m, x, y) để tìm GCD g và các hệ số x, y sao cho a*x + m*y = g.
• Kiểm tra if (g != 1): Nếu GCD khác 1, nghịch đảo không tồn tại, trả về -1.
• Nếu g == 1: x là một giải pháp cho a*x + m*y = 1. Tuy nhiên, giá trị x có thể âm. Để đảm bảo nghịch đảo nằm trong khoảng $[0, m-1]$, chúng ta sử dụng biểu thức (x % m + m) % m. x % m có thể âm trong C++ nếu x âm, việc cộng thêm m rồi lấy modulo lần nữa sẽ đảm bảo kết quả cuối cùng là dương và trong phạm vi mong muốn.

Độ phức tạp: Thuật toán Euclid mở rộng có độ phức tạp tương đương với Thuật toán Euclid thông thường, là O($\log(\min(a, m))$). Đây là một phương pháp rất hiệu quả.

Phương pháp 3: Sử dụng Định lý Fermat nhỏ (Fermat's Little Theorem)

Phương pháp này chỉ áp dụng được khi modulo m là một số nguyên tố.

Định lý Fermat nhỏ phát biểu rằng: Nếu p là một số nguyên tố, thì với bất kỳ số nguyên a nào không chia hết cho p, ta có: $a^{p-1} \equiv 1 \pmod p$

Từ đồng dư thức này, chúng ta có thể suy ra nghịch đảo modulo. Chia cả hai vế cho a: $a \cdot a^{p-2} \equiv 1 \pmod p$

Điều này cho thấy rằng, nếu m là số nguyên tố, và a không chia hết cho m (tức là $\text{gcd}(a, m)=1$ vì m là số nguyên tố), thì nghịch đảo modulo của a modulo m chính là $a^{m-2} \pmod m$.

Để tính $a^{m-2} \pmod m$ một cách hiệu quả khi m-2 là một số mũ lớn, chúng ta sử dụng kỹ thuật lũy thừa theo modulo (modular exponentiation), còn gọi là binary exponentiation (lũy thừa nhị phân).

Lũy thừa theo Modulo (Modular Exponentiation): Kỹ thuật này giúp tính $base^{exp} \pmod{mod}$ một cách nhanh chóng (trong O($\log{exp}$) thời gian) bằng cách sử dụng biểu diễn nhị phân của số mũ exp.

• Nếu exp là chẵn, $base^{exp} = (base^2)^{exp/2}$.
• Nếu exp là lẻ, $base^{exp} = base \cdot base^{exp-1} = base \cdot (base^2)^{(exp-1)/2}$.

Áp dụng tính modulo sau mỗi phép nhân để giữ cho các số không quá lớn.

Triển khai bằng C++:

Đầu tiên, cài đặt hàm lũy thừa theo modulo:

#include <iostream>

// Hàm tính (base^exp) % mod sử dụng lũy thừa nhị phân
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 khoảng [0, mod-1]

    while (exp > 0) {
        if (exp % 2 == 1) {
            // Nếu số mũ lẻ, nhân kết quả với base
            res = (res * base) % mod;
        }
        // Bình phương base và giảm số mũ đi một nửa
        base = (base * base) % mod;
        exp /= 2;
    }

    return res;
}

// Hàm tìm nghịch đảo modulo bằng Định lý Fermat nhỏ (chỉ khi m là số nguyên tố)
long long modInverseFermat(long long a, long long m) {
    // Phương pháp này chỉ hoạt động khi m là số nguyên tố
    // và gcd(a, m) = 1 (a không chia hết cho m)
    // Kiểm tra xem m có phải số nguyên tố hay không là không hiệu quả ở đây
    // nên giả định m là số nguyên tố.
    // Cần đảm bảo a không chia hết cho m, tức a % m != 0.

    // Theo Định lý Fermat nhỏ, a^(m-1) ≡ 1 (mod m)
    // Suy ra a^(m-2) ≡ a^(-1) (mod m)
    // Chúng ta cần tính a^(m-2) % m

    // Đảm bảo a nằm trong khoảng [0, m-1] và không bằng 0 mod m
    a = (a % m + m) % m;
    if (a == 0) {
        // 0 không có nghịch đảo
        return -1;
    }

    // Tính a^(m-2) % m
    return power(a, m - 2, m);
}

// Hàm kiểm tra số nguyên tố đơn giản (cho mục đích minh họa, không hiệu quả cho số lớn)
bool isPrime(long long n) {
    if (n <= 1) return false;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    long long a = 3, m = 11; // 11 là số nguyên tố
    if (isPrime(m)) {
        long long inverse = modInverseFermat(a, m);
        if (inverse != -1) {
            std::cout << "Nghich dao cua " << a << " mod " << m << " (Fermat) la: " << inverse << std::endl; // Output: 4
        } else {
             std::cout << "Nghich dao cua " << a << " mod " << m << " (Fermat) khong ton tai." << std::endl;
        }
    } else {
        std::cout << m << " khong phai so nguyen to, khong dung Fermat." << std::endl;
    }


    a = 10, m = 17; // 17 là số nguyên tố
    if (isPrime(m)) {
        long long inverse = modInverseFermat(a, m);
        if (inverse != -1) {
            std::cout << "Nghich dao cua " << a << " mod " << m << " (Fermat) la: " << inverse << std::endl; // Output: 12
        } else {
             std::cout << "Nghich dao cua " << a << " mod " << m << " (Fermat) khong ton tai." << std::endl;
        }
    } else {
        std::cout << m << " khong phai so nguyen to, khong dung Fermat." << std::endl;
    }

    a = 6, m = 9; // 9 khong phai so nguyen to
    if (isPrime(m)) {
        long long inverse = modInverseFermat(a, m);
        if (inverse != -1) {
            std::cout << "Nghich dao cua " << a << " mod " << m << " (Fermat) la: " << inverse << std::endl;
        } else {
             std::cout << "Nghich dao cua " << a << " mod " << m << " (Fermat) khong ton tai." << std::endl;
        }
    } else {
        std::cout << m << " khong phai so nguyen to, khong dung Fermat." << std::endl; // Output: 9 khong phai so nguyen to...
    }


    return 0;
}

Giải thích Code Định lý Fermat nhỏ: Hàm power(base, exp, mod):

• Đây là hàm lũy thừa nhị phân. res là kết quả tích lũy, khởi tạo bằng 1.
• base %= mod để giảm base về phạm vi $[0, mod-1]$ ngay từ đầu.
• Vòng lặp while (exp > 0) xử lý số mũ exp.
• if (exp % 2 == 1): Nếu bit cuối cùng của exp là 1 (tức exp lẻ), nhân res với base hiện tại (lưu ý có % mod).
• base = (base * base) % mod: Bình phương base cho bước tiếp theo (tức là tính base^2, base^4, base^8, ...).
• exp /= 2: Dịch bit số mũ sang phải một vị trí (tương đương chia 2).
• Hàm trả về res, là kết quả $(base^{exp}) \pmod{mod}$.

Hàm modInverseFermat(a, m):

• Hàm này chỉ đúng khi m là số nguyên tố và a không chia hết cho m.
• a = (a % m + m) % m; chuẩn hóa a.
• Kiểm tra if (a == 0): Nếu a đồng dư với 0 modulo m, nghịch đảo không tồn tại, trả về -1. (Điều này xảy ra khi a chia hết cho m, vi phạm điều kiện của Định lý Fermat nhỏ).
• Nếu các điều kiện thỏa mãn, nó gọi hàm power để tính $a^{m-2} \pmod m$, theo Định lý Fermat nhỏ, đây chính là nghịch đảo modulo.

Độ phức tạp: Độ phức tạp của phương pháp này phụ thuộc vào hàm lũy thừa theo modulo, là O($\log{m}$) (do số mũ là $m-2$). Đây cũng là một phương pháp rất hiệu quả, nhưng kém tổng quát hơn Thuật toán Euclid mở rộng vì nó yêu cầu m phải là số nguyên tố.

3. So sánh các phương pháp

• Thử vét cạn: Đơn giản, dễ hiểu. Chỉ hiệu quả với m rất nhỏ. Độ phức tạp O(m).
• Thuật toán Euclid mở rộng: Tổng quát, hoạt động với mọi m (nguyên tố hoặc hợp số) miễn là $\text{gcd}(a, m) = 1$. Độ phức tạp hiệu quả O($\log m$). Đây là phương pháp được sử dụng rộng rãi nhất khi m không nhất thiết là số nguyên tố.
• Định lý Fermat nhỏ: Chỉ hoạt động khi m là số nguyên tố và a không chia hết cho m. Độ phức tạp hiệu quả O($\log m$). Thường được sử dụng trong các bài toán lập trình thi đấu khi biết chắc modulo là số nguyên tố (phổ biến là $10^9 + 7$).

Tóm lại: Nếu bạn biết modulo m là số nguyên tố, cả hai phương pháp Euclid mở rộng và Fermat nhỏ đều có thể dùng được và đều hiệu quả (O($\log m$)). Phương pháp Fermat nhỏ có thể cảm giác "đơn giản" hơn một chút vì chỉ cần tính lũy thừa. Tuy nhiên, nếu m là số hợp số (không phải nguyên tố), bạn bắt buộc phải dùng Thuật toán Euclid mở rộng.

4. Ứng dụng của Nghịch đảo Modulo

Nghịch đảo modulo là một công cụ quan trọng trong nhiều lĩnh vực:

• Lập trình thi đấu: Rất nhiều bài toán yêu cầu tính kết quả modulo một số M lớn. Đôi khi, công thức kết quả chứa phép chia, ví dụ như tính Tổ hợp $C(n, k) \pmod M$. Công thức $C(n, k) = \frac{n!}{k!(n-k)!}$ có các phép chia giai thừa. Trong số học đồng dư, phép chia cho b tương đương với nhân với nghịch đảo modulo của b. Do đó, $C(n, k) \pmod M = (n! \cdot (k!)^{-1} \cdot ((n-k)! )^{-1}) \pmod M$. Điều này đòi hỏi tính nghịch đảo modulo của $k!$ và $(n-k)!$ modulo $M$.
• Mật mã học: Thuật toán mã hóa khóa công khai RSA dựa trên tính chất của số học đồng dư và việc khó khăn trong việc phân tích thừa số nguyên tố các số lớn. Việc tính khóa giải mã trong RSA sử dụng nghịch đảo modulo.
• Lý thuyết số: Nghịch đảo modulo là một khái niệm cơ bản trong lý thuyết nhóm, vành, trường hữu hạn...

Bài tập ví dụ:

Rhezo và Bài toán Số nguyên tố

Trong một buổi gặp mặt của FullHouse Dev, Rhezo và người bạn Vanya đã cùng nhau thảo luận về một bài toán thú vị. Họ có một bộ bài tập với nhiều điểm số khác nhau, và Rhezo muốn thử thách bản thân với một cách giải độc đáo.

Bài toán

Rhezo và Vanya có một bộ \(N\) bài tập, mỗi bài được gán một số điểm nhất định. Với sở thích đặc biệt về số nguyên tố, Rhezo quyết định chỉ giải một số lượng bài tập liên tiếp sao cho số lượng đó là số nguyên tố. Vanya, người đã giải hết tất cả các bài, tò mò không biết bạn mình có thể đạt được điểm số tối đa là bao nhiêu với quy luật đặc biệt này.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(N\) - số lượng bài tập.
• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách - điểm số của từng bài tập.

OUTPUT FORMAT:

• In ra một số nguyên duy nhất - số điểm tối đa mà Rhezo có thể đạt được.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• Điểm số của mỗi bài tập là số nguyên dương

Ví dụ

INPUT

4
8 1 3 7

OUTPUT

12

Giải thích

Rhezo sẽ giải 3 bài tập đầu tiên (3 là số nguyên tố) và đạt được \(8 + 1 + 3 = 12\) điểm. Lưu ý rằng Rhezo không thể giải tất cả 4 bài vì 4 không phải là số nguyên tố. Đây là hướng dẫn giải bài toán "Rhezo và Bài toán Số nguyên tố" một cách ngắn gọn bằng C++:

1. Ý tưởng chính: Bài toán yêu cầu tìm tổng lớn nhất của một đoạn con liên tục có độ dài là số nguyên tố. Để giải quyết bài này hiệu quả, ta cần hai kỹ thuật chính:

   • Xác định nhanh các số nguyên tố trong một phạm vi.
   • Tính tổng các đoạn con liên tục một cách hiệu quả.

2. Tìm số nguyên tố:

   • Phạm vi số cần kiểm tra nguyên tố là từ 2 đến N (vì độ dài đoạn con không vượt quá N).
   • Sử dụng Sàng Eratosthenes để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng N. Kỹ thuật này cho phép xác định tất cả các số nguyên tố trong phạm vi N một cách hiệu quả (độ phức tạp O(N log log N)).
   • Lưu kết quả sàng vào một mảng boolean (ví dụ: isPrime[k] = true nếu k là số nguyên tố) để có thể tra cứu tính nguyên tố của một số bất kỳ trong O(1).

3. Tính tổng đoạn con:

   • Cách tính tổng một đoạn con liên tục một cách nhanh nhất là sử dụng Mảng tổng tiền tố (Prefix Sums).
   • Tạo một mảng prefix_sum, trong đó prefix_sum[i] lưu tổng điểm của i bài tập đầu tiên (từ chỉ số 0 đến i-1). prefix_sum[0] = 0.
   • prefix_sum[i] = prefix_sum[i-1] + điểm_bài_i-1 cho i > 0.
   • Tổng điểm của đoạn con từ bài tập có chỉ số j đến bài tập có chỉ số k (0-based, bao gồm cả j và k) là prefix_sum[k+1] - prefix_sum[j].

4. Kết hợp và tìm kết quả:

   • Khởi tạo biến max_score với giá trị rất nhỏ (để đảm bảo tổng đầu tiên tìm được sẽ lớn hơn nó).
   • Sau khi có mảng isPrime (từ Sàng Eratosthenes) và mảng prefix_sum:
     • Lặp qua tất cả các số nguyên p từ 2 đến N.
     • Kiểm tra xem p có phải là số nguyên tố hay không bằng cách tra cứu trong mảng isPrime.
     • Nếu p là số nguyên tố:
       • Lặp qua tất cả các vị trí bắt đầu i có thể có của một đoạn con độ dài p. Vị trí bắt đầu i có thể chạy từ 0 đến N - p.
       • Đối với mỗi i, tính tổng của đoạn con bắt đầu từ i với độ dài p. Đoạn này bao gồm các bài tập từ chỉ số i đến i + p - 1.
       • Sử dụng mảng tổng tiền tố để tính tổng này: current_sum = prefix_sum[i + p] - prefix_sum[i].
       • Cập nhật max_score = max(max_score, current_sum).
   • Sau khi duyệt qua tất cả các độ dài nguyên tố và tất cả các vị trí bắt đầu, max_score sẽ chứa điểm số tối đa tìm được.

5. Lưu ý về kiểu dữ liệu: Tổng điểm có thể rất lớn (N=10^5, mỗi bài điểm dương), nên sử dụng kiểu dữ liệu long long cho mảng prefix_sum và biến max_score để tránh tràn số.

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