Bài 3.4. Phép toán modulo và các tính chất

Chào mừng các bạn quay trở lại với series về Cấu trúc dữ liệu và Giải thuật của FullhouseDev! Hôm nay, chúng ta sẽ đi sâu vào một khái niệm tuy đơn giản nhưng lại cực kỳ mạnh mẽ và có mặt ở rất nhiều nơi trong lập trình, đặc biệt là khi giải quyết các bài toán liên quan đến số học, tổ hợp, hay xử lý các con số "siêu to khổng lồ". Đó chính là phép toán modulo và những tính chất thú vị của nó.

Phép Toán Modulo là Gì?

Nói một cách đơn giản, phép toán modulo (ký hiệu phổ biến là mod hoặc % trong nhiều ngôn ngữ lập trình) trả về số dư của một phép chia.

Nếu ta có phép chia a cho m, trong đó a là số bị chia (dividend) và m là số chia (divisor) - thường là số dương, thì:

a mod m = số dư khi a chia cho m

Ví dụ:

10 mod 3 = 1 (vì 10 = 3 * 3 + 1)
15 mod 4 = 3 (vì 15 = 3 * 4 + 3)
7 mod 10 = 7 (vì 7 = 0 * 10 + 7)
12 mod 6 = 0 (vì 12 = 2 * 6 + 0)

Kết quả của phép a mod m luôn nằm trong khoảng [0, m-1] (nếu theo định nghĩa toán học chuẩn với m > 0).

Trong C++, phép toán modulo được ký hiệu là %. Tuy nhiên, có một điểm khác biệt quan trọng giữa toán học và cách C++ (và nhiều ngôn ngữ khác) xử lý số âm.

Trong toán học, a mod m với m > 0 luôn trả về một số dư không âm trong khoảng [0, m-1]. Ví dụ: -10 mod 3 thường được định nghĩa là 2 (vì -10 = -4 * 3 + 2).
Trong C++, toán tử % trả về số dư có cùng dấu với số bị chia a. Ví dụ: -10 % 3 trong C++ sẽ cho kết quả là -1.

Hãy xem một ví dụ minh họa trong C++:

#include <iostream>

int main() {
    int a = 10;
    int m = 3;
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: 10 % 3 = 1

    a = 15;
    m = 4;
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: 15 % 4 = 3

    a = 7;
    m = 10;
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: 7 % 10 = 7

    a = 12;
    m = 6;
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: 12 % 6 = 0

    // Xử lý số âm trong C++
    a = -10;
    m = 3;
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: -10 % 3 = -1 (Khác với toán học!)

    a = 10;
    m = -3; // Số chia âm cũng có hành vi đặc biệt trong C++
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: 10 % -3 = 1

    a = -10;
    m = -3;
    std::cout << a << " % " << m << " = " << a % m << std::endl; // Kết quả: -10 % -3 = -1

    // Để có kết quả không âm chuẩn toán học cho số âm 'a' và số dương 'm':
    a = -10;
    m = 3;
    int positive_remainder = (a % m + m) % m; // Thủ thuật để luôn nhận số dư dương [0, m-1]
    std::cout << "Toan hoc chuan: " << a << " mod " << m << " = " << positive_remainder << std::endl; // Kết quả: Toan hoc chuan: -10 mod 3 = 2

    return 0;
}

Giải thích code: Đoạn code trên minh họa cách toán tử % hoạt động trong C++ với cả số dương và số âm. Lưu ý sự khác biệt khi số bị chia là âm (-10 % 3 cho ra -1). Dòng cuối cùng giới thiệu một thủ thuật phổ biến (a % m + m) % m để đảm bảo kết quả số dư luôn nằm trong khoảng [0, m-1] khi a có thể âm và m dương.

Tại Sao Modulo Quan Trọng trong Lập Trình và Giải Thuật?

Modulo không chỉ là một phép toán số học cơ bản. Nó là nền tảng cho Số học Modulo (Modular Arithmetic), một lĩnh vực toán học nghiên cứu các phép toán trên tập hợp các "lớp đồng dư" (remainder classes).

Trong lập trình, modulo giúp chúng ta:

Giữ các con số trong một phạm vi nhất định: Điều này cực kỳ hữu ích khi làm việc với mảng vòng (circular arrays), bảng băm (hash tables), hoặc các cấu trúc dữ liệu có kích thước cố định.
Ngăn chặn tràn số (Overflow): Khi thực hiện các phép tính với số lớn, kết quả trung gian có thể vượt quá khả năng lưu trữ của kiểu dữ liệu (ví dụ: int, long long). Bằng cách áp dụng modulo sau mỗi bước tính, ta có thể giữ các con số trong một phạm vi quản lý được, miễn là kết quả cuối cùng chúng ta quan tâm là kết quả sau khi lấy modulo. Điều này rất quan trọng trong các bài toán tổ hợp, tính toán xác suất, hay các bài toán mật mã.
Kiểm tra tính chia hết: a % m == 0 có nghĩa là a chia hết cho m.
Tạo ra các mẫu lặp lại: Modulo tạo ra các chuỗi giá trị lặp lại tuần hoàn, điều này hữu ích trong việc tạo số giả ngẫu nhiên, hoạt ảnh, v.v.
Làm cơ sở cho nhiều giải thuật: Hashing, mật mã học (RSA, Diffie-Hellman), các bài toán lý thuyết số, v.v.

Các Tính Chất Cơ Bản Của Phép Toán Modulo

Số học modulo có những tính chất rất đẹp cho phép chúng ta "đẩy" phép toán modulo vào bên trong các biểu thức. Giả sử ta có số nguyên a, b và một số nguyên dương m.

1. Tính chất Cộng (Addition Property)

(a + b) mod m = ((a mod m) + (b mod m)) mod m

Tính chất này nói rằng, khi cộng hai số rồi lấy modulo m, ta cũng có thể lấy modulo m cho từng số hạng trước khi cộng, sau đó lại lấy modulo m một lần nữa.

Tại sao lại hữu ích? Nếu a và b là những số rất lớn, việc tính a + b trực tiếp có thể gây tràn số. Nhưng a mod m và b mod m sẽ nhỏ hơn hoặc bằng m-1. Việc tính (a mod m) + (b mod m) sẽ cho một số không quá lớn (nhỏ hơn 2m), và việc lấy modulo lần cuối sẽ đưa nó về phạm vi [0, m-1].

Ví dụ C++:

#include <iostream>

int main() {
    long long a = 123456789012345LL; // Số rất lớn
    long long b = 987654321098765LL; // Số rất lớn
    int m = 1000000007; // Một modulo phổ biến trong competitive programming (là số nguyên tố)

    // Cách tính trực tiếp (có thể gây tràn nếu a+b vượt quá long long)
    // long long sum = a + b;
    // int result1 = sum % m; // Có thể không chính xác nếu sum bị tràn

    // Áp dụng tính chất cộng
    int a_mod_m = a % m;
    int b_mod_m = b % m;
    int result2 = (a_mod_m + b_mod_m) % m;

    std::cout << "((a % m) + (b % m)) % m = " << result2 << std::endl; // Kết quả chính xác

    // Minh họa với số nhỏ hơn để dễ kiểm tra
    int a_small = 20;
    int b_small = 35;
    int m_small = 12;

    // (20 + 35) mod 12 = 55 mod 12 = 7
    std::cout << "(20 + 35) % 12 = " << (20 + 35) % 12 << std::endl; // Kết quả: 7

    // ((20 mod 12) + (35 mod 12)) mod 12 = (8 + 11) mod 12 = 19 mod 12 = 7
    std::cout << "((20 % 12) + (35 % 12)) % 12 = " << ((20 % m_small) + (35 % m_small)) % m_small << std::endl; // Kết quả: 7

    return 0;
}

Giải thích code: Ví dụ đầu tiên với số lớn cho thấy tại sao tính chất này lại quan trọng để tránh tràn số. Ví dụ thứ hai với số nhỏ minh họa rõ ràng rằng hai cách tính đều cho cùng kết quả, xác nhận tính chất cộng modulo.

2. Tính chất Trừ (Subtraction Property)

(a - b) mod m = ((a mod m) - (b mod m) + m) mod m

Tương tự như phép cộng, ta có thể lấy modulo từng số hạng trước khi trừ. Tuy nhiên, hiệu (a mod m) - (b mod m) có thể cho kết quả âm. Để đảm bảo kết quả cuối cùng nằm trong khoảng [0, m-1] (khi m > 0), ta cộng thêm m trước khi lấy modulo lần cuối.

Ví dụ C++:

#include <iostream>

int main() {
    int a = 20;
    int b = 35;
    int m = 12;

    // Cách tính trực tiếp: (20 - 35) mod 12 = -15 mod 12
    // Trong C++, -15 % 12 = -3
    std::cout << "(20 - 35) % 12 = " << (20 - 35) % m << std::endl; // Kết quả: -3

    // Áp dụng tính chất trừ (sử dụng thủ thuật +m để đảm bảo kết quả dương)
    int a_mod_m = a % m; // 20 % 12 = 8
    int b_mod_m = b % m; // 35 % 12 = 11
    int result = (a_mod_m - b_mod_m + m) % m; // (8 - 11 + 12) % 12 = (-3 + 12) % 12 = 9 % 12 = 9

    std::cout << "((a % m) - (b % m) + m) % m = " << result << std::endl; // Kết quả: 9

    // Lưu ý: Kết quả -3 trong C++ là khác với 9 trong toán học.
    // Tùy vào bài toán mà bạn cần kết quả theo định nghĩa C++ hay toán học.
    // Nếu cần kết quả dương [0, m-1] thì dùng công thức có +m.

    return 0;
}

Giải thích code: Ví dụ này làm rõ sự khác biệt giữa kết quả % của C++ với số âm và kết quả dương theo định nghĩa toán học chuẩn. Khi áp dụng tính chất trừ, ta cần thêm + m để đảm bảo kết quả cuối cùng là số dư không âm trong khoảng [0, m-1].

3. Tính chất Nhân (Multiplication Property)

(a b) mod m = ((a mod m) (b mod m)) mod m

Đây là một trong những tính chất mạnh mẽ nhất và được sử dụng rất nhiều. Nó cho phép ta nhân hai số lớn rồi lấy modulo mà không lo tràn số ở bước nhân ban đầu. Ta chỉ cần lấy modulo từng thừa số, nhân chúng lại, rồi lấy modulo lần cuối.

Ví dụ C++:

#include <iostream>

int main() {
    long long a = 123456789;
    long long b = 987654321;
    int m = 1000000007;

    // Cách tính trực tiếp (có thể gây tràn nếu a*b vượt quá long long)
    // long long product = a * b;
    // int result1 = product % m; // Có thể không chính xác nếu product bị tràn

    // Áp dụng tính chất nhân
    long long a_mod_m = a % m; // Kết quả sẽ nhỏ hơn m
    long long b_mod_m = b % m; // Kết quả sẽ nhỏ hơn m
    // (a_mod_m * b_mod_m) có thể lớn hơn int, nên dùng long long cho biến trung gian
    long long result2 = (a_mod_m * b_mod_m) % m;

    std::cout << "((a % m) * (b % m)) % m = " << result2 << std::endl; // Kết quả chính xác

    // Minh họa với số nhỏ hơn
    int a_small = 20;
    int b_small = 35;
    int m_small = 12;

    // (20 * 35) mod 12 = 700 mod 12 = 4
    std::cout << "(20 * 35) % 12 = " << (20 * 35) % m_small << std::endl; // Kết quả: 4

    // ((20 mod 12) * (35 mod 12)) mod 12 = (8 * 11) mod 12 = 88 mod 12 = 4
    std::cout << "((20 % 12) * (35 % 12)) % 12 = " << ((long long)(20 % m_small) * (35 % m_small)) % m_small << std::endl; // Kết quả: 4
    // Chú ý: Dùng (long long) ép kiểu để phép nhân trung gian 8 * 11 = 88 không bị tràn int nếu m_small lớn

    return 0;
}

Giải thích code: Ví dụ đầu tiên cho thấy sự cần thiết của tính chất nhân modulo khi làm việc với số lớn. Ví dụ thứ hai minh họa tính chính xác của công thức. Lưu ý rằng ngay cả sau khi lấy modulo lần đầu, kết quả a % m và b % m vẫn có thể đủ lớn để khi nhân với nhau ((a % m) * (b % m)) gây tràn kiểu int nếu m đủ lớn (ví dụ m cỡ $10^9$). Do đó, việc sử dụng long long cho phép nhân trung gian (a_mod_m * b_mod_m) là một practice tốt và an toàn.

4. Tính chất Luỹ Thừa (Exponentiation Property)

(a^b) mod m = ((a mod m)^b) mod m

Tính chất này là mở rộng của tính chất nhân. Để tính (a^b) mod m, ta có thể lấy a mod m trước, rồi nâng lên luỹ thừa b, và cuối cùng lấy modulo m.

Tuy nhiên, ngay cả khi ta đã lấy a mod m, giá trị (a mod m)^b vẫn có thể trở nên khổng lồ nếu b lớn, gây tràn số. Ví dụ, nếu a mod m = 2 và b = 10^9, thì 2^(10^9) là một số không thể lưu trữ được.

Vì vậy, để tính luỹ thừa modulo (a^b) mod m với b lớn, chúng ta cần một giải thuật hiệu quả hơn, dựa trên các tính chất cộng và nhân modulo. Giải thuật này được gọi là Luỹ thừa Nhị phân (Binary Exponentiation) hay Luỹ thừa Modulo (Modular Exponentiation).

Ý tưởng chính là phân tích số mũ b thành dạng nhị phân. Ví dụ, b = 13 trong hệ nhị phân là 1101 (tức là 13 = 8 + 4 + 1). Vậy, a^13 = a^(8 + 4 + 1) = a^8 * a^4 * a^1.

Để tính (a^b) mod m, ta tính các luỹ thừa của a với số mũ là các luỹ thừa của 2 theo modulo m (ví dụ: a^1 mod m, a^2 mod m, a^4 mod m, a^8 mod m, ...), rồi nhân các kết quả tương ứng với các bit '1' trong biểu diễn nhị phân của b lại với nhau theo modulo m.

Ví dụ C++ (Giải thuật Luỹ thừa Modulo):

#include <iostream>

// Hàm tính (base^exp) % mod sử dụng giải thuật luỹ thừa nhị phân
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod; // Áp dụng tính chất: (base^exp) mod m = ((base mod m)^exp) mod m

    while (exp > 0) {
        // Nếu bit cuối cùng của exp là 1 (exp lẻ)
        if (exp % 2 == 1) {
            // res = (res * base) % mod
            res = (res * base) % mod;
        }

        // Bình phương base cho lần lặp tiếp theo
        // base = (base * base) % mod
        base = (base * base) % mod;

        // Chia đôi exp (dịch bit sang phải)
        exp /= 2; // hoặc exp >>= 1;
    }

    return res;
}

int main() {
    long long base = 3;
    long long exp = 13; // Tương đương nhị phân 1101
    long long mod = 10;

    // Tính 3^13 mod 10
    // 3^13 = 1594323
    // 1594323 mod 10 = 3

    long long result = power(base, exp, mod);
    std::cout << base << "^" << exp << " mod " << mod << " = " << result << std::endl; // Kết quả: 3^13 mod 10 = 3

    // Ví dụ với số lớn
    base = 12345;
    exp = 67890;
    mod = 1000000007;

    result = power(base, exp, mod);
    std::cout << base << "^" << exp << " mod " << mod << " = " << result << std::endl; // Kết quả sẽ là một số trong [0, 1000000006]

    return 0;
}

Giải thích code: Hàm power(base, exp, mod) tính (base^exp) % mod.

res được khởi tạo là 1 (vì bất kỳ số nào mũ 0 đều bằng 1).
base %= mod;: Ta lấy base modulo mod ngay từ đầu để giữ giá trị base trong phạm vi nhỏ hơn mod.
Vòng lặp while (exp > 0) xử lý từng bit của số mũ exp từ phải sang trái.
if (exp % 2 == 1): Nếu bit hiện tại của exp là 1 (tức exp lẻ), điều đó có nghĩa là luỹ thừa base^(2^k) (với k là vị trí bit) cần được nhân vào kết quả cuối cùng. Ta cập nhật res = (res * base) % mod;. Phép nhân này được thực hiện theo modulo để tránh tràn số.
base = (base * base) % mod;: Ở mỗi bước lặp, ta tính bình phương của base hiện tại theo modulo. Nếu base ban đầu là a, thì các giá trị của base trong vòng lặp sẽ lần lượt là a^1 % mod, a^2 % mod, a^4 % mod, a^8 % mod, ...
exp /= 2;: Ta dịch bit của exp sang phải 1 vị trí, tương đương với việc xét bit tiếp theo.
Quá trình lặp cho đến khi exp về 0. Kết quả cuối cùng được lưu trong res.

Giải thuật này có độ phức tạp thời gian là O(log exp), rất hiệu quả cho các giá trị exp lớn, trong khi tính trực tiếp sẽ là O(exp) và nhanh chóng gây tràn số.

5. Tính chất Phân phối (Distributive Property)

Số học modulo cũng tuân theo các tính chất phân phối giống như số học thông thường:

Phân phối phép nhân trên phép cộng: (a + b) c mod m = ((a c mod m) + (b * c mod m)) mod m
Phân phối phép nhân trên phép trừ: (a - b) c mod m = ((a c mod m) - (b * c mod m) + m) mod m

Những tính chất này về cơ bản là sự kết hợp của tính chất cộng/trừ và nhân đã nêu ở trên.

6. Quan hệ Đồng dư (Congruence Relation)

Khái niệm liên quan chặt chẽ đến modulo là đồng dư. Hai số nguyên a và b được gọi là đồng dư modulo m nếu chúng có cùng số dư khi chia cho m. Ký hiệu là:

a ≡ b (mod m)

Điều này tương đương với việc a - b chia hết cho m, hay (a - b) % m == 0.

Ví dụ:

10 ≡ 1 (mod 3) vì 10 % 3 = 1 và 1 % 3 = 1. Hoặc (10 - 1) % 3 = 9 % 3 = 0.
25 ≡ 13 (mod 6) vì 25 % 6 = 1 và 13 % 6 = 1. Hoặc (25 - 13) % 6 = 12 % 6 = 0.
-10 ≡ 2 (mod 3) vì -10 % 3 = -1 (C++) và 2 % 3 = 2 (C++). Sử dụng định nghĩa toán học chuẩn: -10 = -4 * 3 + 2, 2 = 0 * 3 + 2. Hoặc (-10 - 2) % 3 = -12 % 3 = 0.

Quan hệ đồng dư là một quan hệ tương đương và có các tính chất bắc cầu, đối xứng, phản xạ. Nó giúp chúng ta làm việc với các "lớp" số có cùng số dư thay vì bản thân các số đó, đơn giản hóa nhiều bài toán.

Phép Chia Modulo (Modular Division)?

Bạn có thể thắc mắc về phép chia: (a / b) mod m. Liệu có tính chất tương tự như cộng, trừ, nhân không?

Câu trả lời là không có tính chất trực tiếp như vậy. (a / b) mod m thường không bằng ((a mod m) / (b mod m)) mod m. Phép chia trong số học modulo phức tạp hơn và liên quan đến khái niệm Nhân nghịch đảo modulo (Modular Multiplicative Inverse).

Nhân nghịch đảo của b modulo m là một số b^-1 sao cho:

(b * b^-1) ≡ 1 (mod m)

Nếu tồn tại b^-1, thì phép chia a / b modulo m có thể được định nghĩa là (a * b^-1) mod m. Nhân nghịch đảo b^-1 mod m chỉ tồn tại khi b và m là nguyên tố cùng nhau (GCD(b, m) = 1).

Việc tính nhân nghịch đảo modulo thường sử dụng Thuật toán Euclid mở rộng (Extended Euclidean Algorithm) hoặc Định lý Fermat nhỏ (Little Fermat's Theorem) nếu m là số nguyên tố. Tuy nhiên, đây là một chủ đề chuyên sâu hơn và có thể dành cho một bài khác.

Ứng Dụng Thực Tế Của Modulo

Như đã đề cập, modulo xuất hiện ở nhiều nơi:

Bảng Băm (Hash Tables): Hàm băm thường tính chỉ mục lưu trữ bằng cách lấy giá trị băm của khóa modulo kích thước bảng. index = hash(key) % table_size.
Mật Mã Học: Nhiều giải thuật mã hóa hiện đại (ví dụ: RSA) dựa trên số học modulo, đặc biệt là luỹ thừa modulo các số nguyên tố lớn.
Tạo Số Giả Ngẫu Nhiên: Các bộ tạo số giả ngẫu nhiên tuần tự (Linear Congruential Generator - LCG) sử dụng công thức lặp X(n+1) = (A * X(n) + B) mod M để tạo ra chuỗi số nhìn có vẻ ngẫu nhiên.
Các Bài Toán Thuật Toán:
- Tính toán với kết quả có thể rất lớn, yêu cầu lấy modulo một số m cho trước (thường là $10^9+7$ hoặc $10^9+9$ vì chúng là số nguyên tố lớn).
- Các bài toán liên quan đến chu kỳ, lặp lại (ví dụ: tìm phần tử thứ k trong một chuỗi lặp).
- Các bài toán đếm, tổ hợp (kết quả thường rất lớn).
- Kiểm tra tính chia hết, các tính chất số học.
- Làm việc với mảng vòng (ví dụ: hàng đợi dùng mảng). Khi con trỏ đến cuối mảng, ta dùng modulo để quay lại đầu mảng: next_index = (current_index + 1) % array_size.

Tóm Kết (Tạm Thời)

Phép toán modulo là công cụ cơ bản nhưng vô cùng mạnh mẽ. Việc nắm vững định nghĩa (bao gồm cả sự khác biệt trong xử lý số âm giữa toán học và C++), cùng các tính chất cộng, trừ, nhân, và đặc biệt là giải thuật luỹ thừa modulo, sẽ giúp bạn giải quyết hiệu quả nhiều bài toán khó trong lập trình và các kỳ thi giải thuật.

Hãy luyện tập sử dụng các tính chất này trong các bài toán cụ thể để cảm nhận sức mạnh của chúng!

Bài tập ví dụ:

Mảng số nguyên tố

Trong một chuyến đi mua sắm tại trung tâm thương mại, FullHouse Dev tình cờ bắt gặp một câu đố thú vị được dán trên bảng thông báo. Họ quyết định cùng nhau giải quyết bài toán này trong lúc nghỉ giải lao.

Bài toán

FullHouse Dev được cung cấp một mảng có $n$ số nguyên. Nhiệm vụ của họ là tìm số bộ ba chỉ số $i$, $j$, $k$ thỏa mãn điều kiện $A[i] + A[j] + A[k]$ là số nguyên tố.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $T$ - số lượng test case
Với mỗi test case:
- Dòng đầu tiên chứa một số nguyên $n$
- Dòng thứ hai chứa $n$ số nguyên $A[i]$

OUTPUT FORMAT:

Với mỗi test case, in ra số lượng bộ ba thỏa mãn điều kiện đã cho trên một dòng riêng biệt

Ràng buộc:

$1 \leq T \leq 100$
$1 \leq n \leq 1000$
$1 \leq A[i] \leq 1000$

Ví dụ

INPUT

OUTPUT

0
1

Giải thích

Ở test case đầu tiên, không có bộ ba nào thỏa mãn điều kiện đã cho.
Ở test case thứ hai, có một bộ ba thỏa mãn là $(1,1,5)$ vì $1 + 1 + 5 = 7$ là số nguyên tố. Tuyệt vời! Đây là hướng dẫn ngắn gọn để giải bài "Mảng số nguyên tố" bằng C++, tập trung vào các bước chính và kỹ thuật cần dùng mà không đưa ra code hoàn chỉnh:

Xác định giới hạn tổng: Tổng nhỏ nhất là 1 + 1 + 1 = 3, tổng lớn nhất có thể là 1000 + 1000 + 1000 = 3000. Bạn sẽ cần kiểm tra tính nguyên tố cho các số lên đến 3000.
Sàng nguyên tố (Sieve of Eratosthenes): Để kiểm tra tính nguyên tố nhanh chóng, bạn nên sử dụng sàng Eratosthenes để tạo ra một mảng boolean (ví dụ: isPrime[3001]) đánh dấu các số nguyên tố từ 0 đến 3000 (hoặc một giới hạn an toàn hơn một chút, ví dụ 3005). Việc này làm trước khi xử lý các test case (hoặc chỉ làm một lần cho tất cả test case nếu bạn sử dụng biến toàn cục hoặc static).
- Khởi tạo tất cả các giá trị là true.
- Đánh dấu 0 và 1 là false.
- Bắt đầu từ số nguyên tố đầu tiên là 2, đánh dấu tất cả bội số của nó là false. Tiếp tục với số nguyên tố tiếp theo chưa bị đánh dấu cho đến khi đạt đến căn bậc hai của giới hạn trên.
Đọc input:
- Đọc số lượng test case T.
- Lặp lại T lần cho mỗi test case.
- Trong mỗi test case, đọc số nguyên n và sau đó đọc n số nguyên vào một mảng (ví dụ: std::vector hoặc mảng C).
Tìm và đếm bộ ba:
- Khởi tạo một bộ đếm (ví dụ: count) về 0 cho mỗi test case.
- Sử dụng ba vòng lặp lồng nhau để duyệt qua tất cả các bộ ba chỉ số i, j, k từ 0 đến n-1. Chú ý các chỉ số có thể lặp lại.
  - Vòng lặp thứ nhất cho i từ 0 đến n-1.
  - Vòng lặp thứ hai cho j từ 0 đến n-1.
  - Vòng lặp thứ ba cho k từ 0 đến n-1.
- Trong vòng lặp trong cùng, tính tổng sum = A[i] + A[j] + A[k].
- Kiểm tra xem sum có phải là số nguyên tố hay không bằng cách tra cứu trong mảng isPrime đã tính bằng sàng Eratosthenes (isPrime[sum] == true).
- Nếu sum là số nguyên tố, tăng biến đếm count lên 1.
In kết quả: Sau khi duyệt qua tất cả các bộ ba cho một test case, in giá trị của count ra một dòng.

Tóm tắt các bước cần thực hiện trong code C++:

Khai báo và chạy sàng Eratosthenes một lần cho các số đến 3000+.
Đọc T.
Vòng lặp T lần:
- Đọc N và mảng A.
- count = 0.
- Ba vòng lặp lồng nhau for (i=0..n-1) for (j=0..n-1) for (k=0..n-1):
  - sum = A[i] + A[j] + A[k].
  - Nếu isPrime[sum] là true, count++.
- In count.

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

Comments

There are no comments at the moment.