Khóa học CTDL và GT

Bài 3.5. Bài tập tổng hợp về số nguyên tố và đồng dư

Chào mừng trở lại với chuỗi bài viết 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à một số cấu trúc dữ liệu đầu tiên, hôm nay chúng ta sẽ lặn sâu vào một lĩnh vực toán học cực kỳ quan trọng và có nhiều ứng dụng trong lập trình, đặc biệt là trong thiết kế giải thuật: Số nguyên tố và Đồng dư.

Hai khái niệm này thoạt nhìn có vẻ chỉ là lý thuyết toán học khô khan, nhưng chúng lại là trụ cột xây dựng nên nhiều kỹ thuật và thuật toán mạnh mẽ, từ các bài toán tối ưu cơ bản đến những hệ thống mật mã phức tạp đảm bảo an toàn thông tin của chúng ta. Hiểu rõ về số nguyên tố và đồng dư sẽ mở ra những cánh cửa mới trong việc giải quyết các bài toán lập trình đầy thách thức.

Hãy cùng bắt đầu khám phá!

I. Số Nguyên Tố (Prime Numbers)

Số nguyên tố là một trong những khối xây dựng cơ bản nhất của toán học. Chúng là những số tự nhiên lớn hơn 1 chỉ có đúng hai ước số dương phân biệt là 1 và chính nó. Ví dụ điển hình là 2, 3, 5, 7, 11, ... Số 4 không phải số nguyên tố vì nó có các ước là 1, 2, và 4. Số 1 không phải số nguyên tố theo quy ước.

Tại sao số nguyên tố lại quan trọng trong lập trình?

1. Nền tảng của Số học: Mọi số tự nhiên lớn hơn 1 đều có thể phân tích duy nhất thành tích của các số nguyên tố (Định lý cơ bản của Số học). Điều này giúp chúng ta hiểu cấu trúc của các con số.
2. Mật mã học: Các thuật toán mã hóa hiện đại như RSA dựa trên sự khó khăn của việc phân tích một số lớn thành tích của hai số nguyên tố rất lớn.
3. Thuật toán: Nhiều giải thuật (ví dụ: kiểm tra tính nguyên tố, phân tích thừa số nguyên tố, các bài toán liên quan đến ước chung lớn nhất, bội chung nhỏ nhất) trực tiếp làm việc với số nguyên tố.
4. Hashing: Đôi khi, kích thước của bảng băm (hash table) được chọn là một số nguyên tố để giảm thiểu xung đột.

1. Kiểm tra tính nguyên tố (Primality Test)

Đây là bài toán cơ bản nhất: Cho một số nguyên dương N, kiểm tra xem N có phải là số nguyên tố không?

Phương pháp ngây thơ (Naive Approach)

Ý tưởng đơn giản nhất là thử chia N cho tất cả các số từ 2 đến N-1. Nếu N chia hết cho bất kỳ số nào trong khoảng này, thì N không phải là số nguyên tố. Ngược lại, nếu không chia hết cho số nào, thì N là số nguyên tố.

bool isPrimeNaive(int n) {
    if (n <= 1) return false; // 0 và 1 không phải nguyên tố
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false; // Tìm thấy ước, không phải nguyên tố
        }
    }
    return true; // Không tìm thấy ước nào, là nguyên tố
}

Giải thích code:

• Hàm isPrimeNaive(int n) nhận một số nguyên n.
• Trường hợp n <= 1 được xử lý trước vì 0 và 1 không phải số nguyên tố.
• Vòng lặp for bắt đầu từ i = 2 và chạy đến i < n.
• Bên trong vòng lặp, chúng ta kiểm tra xem n có chia hết cho i không (n % i == 0).
• Nếu có, tức là n có ước khác 1 và chính nó, hàm trả về false.
• Nếu vòng lặp kết thúc mà không tìm thấy ước nào, hàm trả về true.

Độ phức tạp: Phương pháp này có độ phức tạp là O(N), khá chậm đối với các số N lớn.

Tối ưu hóa

Chúng ta có thể tối ưu hóa đáng kể.

• Tối ưu 1: Chúng ta chỉ cần kiểm tra đến N/2. Nếu một số N có ước d > N/2, thì ước còn lại N/d sẽ nhỏ hơn 2, điều này chỉ xảy ra khi d=N (ước là chính nó) hoặc N=1 (không xét). Do đó, mọi ước thực sự (khác 1 và N) của N đều phải nhỏ hơn hoặc bằng N/2.
• Tối ưu 2: Quan sát sâu hơn, nếu N có một ước d, thì N = d * k với k = N/d. Nếu cả d và k đều lớn hơn sqrt(N), thì tích d * k sẽ lớn hơn sqrt(N) * sqrt(N) = N. Điều này mâu thuẫn với N = d * k. Do đó, ít nhất một trong hai ước d hoặc k phải nhỏ hơn hoặc bằng sqrt(N). Điều này có nghĩa là nếu N có ước, nó phải có một ước nhỏ hơn hoặc bằng sqrt(N). Chúng ta chỉ cần kiểm tra đến sqrt(N).

#include <cmath> // Cần thư viện cmath cho sqrt()

bool isPrimeOptimized(int n) {
    if (n <= 1) return false; // 0 và 1 không phải nguyên tố
    for (int i = 2; i * i <= n; i++) { // Kiểm tra đến căn bậc hai của n
        if (n % i == 0) {
            return false; // Tìm thấy ước
        }
    }
    return true; // Là nguyên tố
}

Giải thích code:

• Hàm isPrimeOptimized(int n) tương tự hàm trước.
• Điểm khác biệt chính là điều kiện của vòng lặp: i * i <= n. Điều này tương đương với i <= sqrt(n) nhưng tránh tính toán sqrt trong mỗi lần lặp (và tránh làm việc với số dấu phẩy động).
• Các trường hợp cơ bản và logic trả về tương tự.

Độ phức tạp: Phương pháp này có độ phức tạp O(sqrt(N)), nhanh hơn nhiều so với O(N) cho N lớn.

Tối ưu hóa thêm

Chúng ta có thể tối ưu hóa hơn nữa bằng cách loại bỏ việc kiểm tra các ước chẵn (ngoại trừ số 2) và các ước chia hết cho 3 (ngoại trừ số 3).

• Số 2 và 3 là số nguyên tố.
• Tất cả các số nguyên tố khác 2 và 3 đều có dạng 6k ± 1 (tức là 6k - 1 hoặc 6k + 1) với k là số nguyên dương.
• Chúng ta kiểm tra riêng cho 2 và 3. Sau đó, bắt đầu kiểm tra từ 5 với bước nhảy 6: kiểm tra i và i+2 (tương ứng với 6k-1 và 6k+1).

bool isPrime(int n) {
    if (n <= 1) return false; // 0 và 1
    if (n <= 3) return true;  // 2 và 3
    if (n % 2 == 0 || n % 3 == 0) return false; // Các số chẵn khác 2, các số chia hết cho 3 khác 3

    // Kiểm tra các số có dạng 6k ± 1 từ 5 trở đi
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false; // Tìm thấy ước dạng 6k-1 hoặc 6k+1
    }
    return true; // Là nguyên tố
}

Giải thích code:

• Xử lý các trường hợp đặc biệt: n <= 1, n <= 3, n % 2 == 0 hoặc n % 3 == 0.
• Vòng lặp bắt đầu từ i = 5. Điều kiện lặp vẫn là i * i <= n.
• Bước nhảy của i là i = i + 6. Trong mỗi lần lặp, chúng ta kiểm tra chia hết cho i và i+2.
• Logic này bao phủ việc kiểm tra các ước tiềm năng dạng 5, 7, 11, 13, 17, 19, ... cho đến sqrt(n).

Độ phức tạp: Vẫn là O(sqrt(N)) về mặt tiệm cận, nhưng nhanh hơn trong thực tế vì số phép chia ít hơn khoảng 3 lần so với chỉ kiểm tra số lẻ.

2. Tìm tất cả số nguyên tố trong một khoảng (Generating Primes)

Khi cần tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một giới hạn N, việc kiểm tra từng số một bằng isPrime sẽ không hiệu quả (tổng độ phức tạp sẽ là khoảng N sqrt(N)). Thuật toán Sàng Eratosthenes* (Sieve of Eratosthenes) là một phương pháp hiệu quả hơn nhiều.

Ý tưởng của Sàng Eratosthenes:

1. Tạo một danh sách tất cả các số tự nhiên từ 2 đến N, ban đầu đánh dấu tất cả chúng là "có thể là nguyên tố".
2. Bắt đầu với số nguyên tố nhỏ nhất là 2. Đánh dấu tất cả các bội số của 2 (lớn hơn 2) là "không phải nguyên tố".
3. Tìm số tiếp theo trong danh sách vẫn được đánh dấu là "có thể là nguyên tố". Số đó chắc chắn là một số nguyên tố (vì nó không phải là bội của bất kỳ số nguyên tố nào nhỏ hơn nó).
4. Lặp lại bước 2 và 3: đánh dấu tất cả các bội số của số nguyên tố mới tìm được là "không phải nguyên tố".
5. Tiếp tục quá trình này cho đến khi bạn xử lý tất cả các số nguyên tố mà bình phương của chúng nhỏ hơn hoặc bằng N.

#include <vector>
#include <iostream> // Để in kết quả (ví dụ)

std::vector<bool> sieveOfEratosthenes(int n) {
    // Tạo vector boolean, ban đầu giả sử tất cả đều là nguyên tố
    std::vector<bool> is_prime(n + 1, true);

    // 0 và 1 không phải nguyên tố
    is_prime[0] = is_prime[1] = false;

    // Bắt đầu từ 2
    for (int p = 2; p * p <= n; p++) {
        // Nếu p vẫn được đánh dấu là nguyên tố
        if (is_prime[p] == true) {
            // Đánh dấu tất cả các bội số của p (lớn hơn hoặc bằng p*p) là không phải nguyên tố
            // Bắt đầu từ p*p vì các bội nhỏ hơn (p*2, p*3,... < p*p) đã bị đánh dấu
            // bởi các số nguyên tố nhỏ hơn p.
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }

    // Vector is_prime[i] = true nếu i là số nguyên tố
    return is_prime;
}

// Ví dụ sử dụng Sàng Eratosthenes
int main_sieve_example() {
    int limit = 100;
    std::vector<bool> primes = sieveOfEratosthenes(limit);

    std::cout << "Cac so nguyen to nho hon hoac bang " << limit << " la:" << std::endl;
    for (int p = 2; p <= limit; p++) {
        if (primes[p]) {
            std::cout << p << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

Giải thích code:

• Hàm sieveOfEratosthenes(int n) nhận giới hạn trên n.
• Tạo một std::vector<bool> có kích thước n + 1. is_prime[i] sẽ là true nếu i là số nguyên tố và false nếu không. Ban đầu gán tất cả là true.
• Gán is_prime[0] và is_prime[1] là false.
• Vòng lặp ngoài bắt đầu từ p = 2. Điều kiện lặp là p * p <= n. Chúng ta chỉ cần xử lý các số nguyên tố p mà p*p <= n vì nếu một số composite C <= n có ước nguyên tố q > sqrt(n), thì ước còn lại C/q phải nhỏ hơn sqrt(n), và C đã bị đánh dấu bởi ước nhỏ hơn này.
• Bên trong vòng lặp ngoài, nếu is_prime[p] vẫn là true, điều đó có nghĩa p là số nguyên tố (chưa bị đánh dấu bởi các số nguyên tố nhỏ hơn).
• Vòng lặp trong bắt đầu từ i = p * p và tăng i lên p mỗi lần lặp (i += p). Điều này đánh dấu tất cả các bội số của p (từ p*p trở đi) là không phải nguyên tố.
• Hàm trả về vector is_prime.
• Hàm main_sieve_example minh họa cách sử dụng: gọi hàm sàng và in ra các chỉ số p mà is_prime[p] là true.

Độ phức tạp: Sàng Eratosthenes có độ phức tạp xấp xỉ O(N log log N), nhanh hơn đáng kể so với O(N * sqrt(N)) khi N lớn. Đây là phương pháp hiệu quả nhất để tìm tất cả số nguyên tố trong một phạm vi.

II. Đồng Dư (Modular Congruence)

Đồng dư là một khái niệm trong số học mô đun (modular arithmetic). Nó liên quan đến phần dư của phép chia.

Chúng ta nói rằng hai số nguyên a và b là đồng dư theo mô đun m (ký hiệu a ≡ b (mod m)) nếu chúng có cùng phần dư khi chia cho số nguyên dương m. Một cách định nghĩa tương đương là a - b chia hết cho m.

Ví dụ:

• 17 ≡ 5 (mod 12) vì 17 chia 12 dư 5 và 5 chia 12 cũng dư 5. Hoặc 17 - 5 = 12, chia hết cho 12.
• 3 ≡ 10 (mod 7) vì 3 chia 7 dư 3 và 10 chia 7 dư 3. Hoặc 3 - 10 = -7, chia hết cho 7.
• 25 ≡ 0 (mod 5) vì 25 chia 5 dư 0. Hoặc 25 - 0 = 25, chia hết cho 5.

Mô đun m thường đại diện cho một "chu kỳ". Ví dụ phổ biến nhất là đồng hồ 12 giờ (mô đun 12). Nếu bây giờ là 3 giờ, sau 14 giờ nữa sẽ là 3 + 14 = 17 giờ. Trên đồng hồ 12 giờ, 17 giờ tương đương với 5 giờ chiều (17 mod 12 = 5).

1. Các tính chất của Đồng dư

Đồng dư có nhiều tính chất hữu ích giúp chúng ta thực hiện các phép tính số học trên phần dư: Cho a ≡ b (mod m) và c ≡ d (mod m):

• Phản xạ: a ≡ a (mod m)
• Đối xứng: Nếu a ≡ b (mod m) thì b ≡ a (mod m).
• Bắc cầu: Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m).
• Cộng: a + c ≡ b + d (mod m).
• Trừ: a - c ≡ b - d (mod m).
• Nhân: a * c ≡ b * d (mod m).
• Lũy thừa: a^k ≡ b^k (mod m) với k là số nguyên dương.

Những tính chất này cho phép chúng ta thực hiện các phép tính số học trước rồi mới lấy mô đun, hoặc lấy mô đun sau mỗi phép tính (đối với cộng, trừ, nhân) mà kết quả đồng dư vẫn được giữ nguyên. Điều này cực kỳ quan trọng khi làm việc với các số rất lớn mà không thể lưu trữ trực tiếp.

Ví dụ: Tính (123 + 456) mod 10.

• Cách 1 (Tính tổng trước): 123 + 456 = 579. 579 mod 10 = 9.
• Cách 2 (Lấy mô đun từng số rồi cộng): 123 mod 10 = 3, 456 mod 10 = 6. (3 + 6) mod 10 = 9 mod 10 = 9. Kết quả là như nhau.

Ví dụ: Tính (12 * 34) mod 10.

• Cách 1: 12 * 34 = 408. 408 mod 10 = 8.
• Cách 2: 12 mod 10 = 2, 34 mod 10 = 4. (2 * 4) mod 10 = 8 mod 10 = 8. Kết quả là như nhau.

2. Ứng dụng: Tính lũy thừa mô đun (Modular Exponentiation)

Một bài toán phổ biến là tính a^b mod m, trong đó a, b, và m có thể là các số rất lớn. Nếu tính a^b trước rồi mới lấy mô đun, giá trị a^b có thể vượt quá giới hạn lưu trữ của các kiểu dữ liệu thông thường.

Chúng ta sử dụng tính chất nhân của đồng dư: (x * y) mod m = ((x mod m) * (y mod m)) mod m. Áp dụng tính chất này liên tục trong quá trình tính lũy thừa.

Phương pháp ngây thơ

Tính a^b bằng cách nhân a với chính nó b lần, và sau mỗi lần nhân, lấy mô đun m.

long long powerNaive(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]

    for (int i = 0; i < exp; i++) {
        res = (res * base) % mod;
    }
    return res;
}

Giải thích code:

• Hàm powerNaive nhận cơ số base, số mũ exp, và mô đun mod.
• Khởi tạo res = 1.
• base %= mod đảm bảo base ban đầu không quá lớn.
• Vòng lặp exp lần, mỗi lần nhân res với base và lấy mô đun % mod.
• Trả về kết quả cuối cùng.

Độ phức tạp: O(exp), vẫn chậm nếu exp rất lớn.

Phương pháp tối ưu: Lũy thừa nhị phân (Binary Exponentiation / Exponentiation by Squaring)

Đây là một kỹ thuật rất hiệu quả để tính a^b trong O(log b) thời gian. Ý tưởng dựa trên biểu diễn nhị phân của số mũ b.

Giả sử b ở dạng nhị phân là b_k b_{k-1} ... b_1 b_0, nghĩa là b = b_k * 2^k + b_{k-1} * 2^{k-1} + ... + b_1 * 2^1 + b_0 * 2^0. Khi đó, a^b = a^(b_k * 2^k + ... + b_0 * 2^0) = a^(b_k * 2^k) * ... * a^(b_0 * 2^0). Mỗi thành phần a^(b_i * 2^i) chỉ khác 1 nếu bit b_i là 1. Chúng ta có thể tính các giá trị a^(2^0), a^(2^1), a^(2^2), ... bằng cách bình phương liên tiếp: a^(2^0) = a a^(2^1) = (a^(2^0))^2 = a^2 a^(2^2) = (a^(2^1))^2 = (a^2)^2 = a^4 a^(2^i) = (a^(2^(i-1)))^2

Trong quá trình tính, nếu bit hiện tại của b là 1, chúng ta nhân kết quả vào tích cuối cùng. Nếu bit là 0, chúng ta bỏ qua.

long long power(long long base, long long exp, long long mod) {
    long long res = 1; // Khởi tạo kết quả là 1
    base %= mod; // Đảm bảo base nằm trong khoảng [0, mod-1]

    while (exp > 0) {
        // Nếu bit cuối cùng của exp là 1 (exp là số lẻ)
        if (exp % 2 == 1) {
            res = (res * base) % mod; // Nhân base hiện tại vào kết quả
        }

        // Bình phương base và lấy mô đun cho bước tiếp theo (bit tiếp theo của exp)
        base = (base * base) % mod;

        // Dịch phải exp 1 bit (chia exp cho 2)
        exp /= 2;
    }

    return res;
}

// Ví dụ sử dụng lũy thừa nhị phân
int main_power_example() {
    long long base = 2;
    long long exp = 10;
    long long mod = 100;

    long long result = power(base, exp, mod); // Tính 2^10 mod 100
    std::cout << base << "^" << exp << " mod " << mod << " = " << result << std::endl; // Kết quả: 1024 mod 100 = 24

    base = 1000000007; // Một số lớn
    exp = 1000000000; // Số mũ rất lớn
    mod = 1000000009; // Mô đun lớn

    result = power(base, exp, mod);
    std::cout << base << "^" << exp << " mod " << mod << " = " << result << std::endl; // Sẽ in ra kết quả đúng mà không bị tràn số

    return 0;
}

Giải thích code:

• Hàm power nhận base, exp, mod.
• res = 1 là phần tử đơn vị cho phép nhân.
• base %= mod xử lý cơ số ban đầu.
• Vòng lặp while (exp > 0) xử lý từng bit của số mũ exp, từ bit thấp nhất đến bit cao nhất.
• if (exp % 2 == 1): Kiểm tra bit cuối cùng của exp. Nếu là 1 (tức exp lẻ), điều đó có nghĩa là base^(2^i) (với i là số lần lặp đã qua) là một thừa số trong kết quả cuối cùng. Ta nhân base hiện tại vào res. Phép nhân (res * base) % mod luôn giữ kết quả trong phạm vi mô đun.
• base = (base * base) % mod: Tính base^(2 * current_power_of_2) cho lần lặp tiếp theo. Lại lấy mô đun để tránh tràn số.
• exp /= 2: Dịch phải số mũ, loại bỏ bit đã xử lý và chuẩn bị cho bit tiếp theo.
• Khi exp trở thành 0, vòng lặp kết thúc, và res chứa kết quả base^original_exp mod mod.

Độ phức tạp: O(log exp), vì trong mỗi lần lặp, số mũ exp được chia đôi. Đây là phương pháp chuẩn khi cần tính lũy thừa mô đun với số mũ lớn.

III. Kết hợp Số Nguyên Tố và Đồng Dư trong Bài Toán

Số nguyên tố và đồng dư thường xuất hiện cùng nhau trong các bài toán yêu cầu tính toán trên số lớn hoặc các bài toán liên quan đến cấu trúc số học.

Ví dụ về một bài toán có thể sử dụng cả hai khái niệm:

Bài toán: Cho một số nguyên dương N và một mô đun M. Tính tổng của tất cả các số nguyên tố nhỏ hơn hoặc bằng N, lấy kết quả theo mô đun M.

Input: N, M Output: (p1 + p2 + ... + pk) mod M, trong đó p1, p2, ..., pk là tất cả số nguyên tố <= N.

Phân tích:

1. Cần tìm tất cả số nguyên tố <= N. Sàng Eratosthenes là lựa chọn hiệu quả nhất.
2. Cần tính tổng các số nguyên tố này. Vì tổng có thể rất lớn, chúng ta cần áp dụng tính chất đồng dư của phép cộng. Thay vì tính tổng S = p1 + p2 + ... + pk rồi mới lấy S mod M, chúng ta sẽ tính S = (S + pi) mod M cho từng số nguyên tố pi.

Giải thuật:

1. Sử dụng Sàng Eratosthenes để tạo danh sách/vector boolean is_prime cho các số từ 0 đến N.
2. Khởi tạo biến sum = 0.
3. Duyệt qua các số i từ 2 đến N.
4. Nếu is_prime[i] là true (nghĩa là i là số nguyên tố), cập nhật sum = (sum + i) % M.
5. Sau khi duyệt hết các số đến N, sum chính là kết quả cần tìm.

Code minh họa:

#include <iostream>
#include <vector>
#include <numeric> // Thư viện cho std::accumulate nếu cần, nhưng ở đây dùng vòng lặp

// Hàm Sàng Eratosthenes (copy từ phần trước)
std::vector<bool> sieveOfEratosthenes(int n) {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    return is_prime;
}

long long sumPrimesModulo(int n, int m) {
    // Bước 1: Tìm các số nguyên tố <= n bằng Sàng Eratosthenes
    std::vector<bool> is_prime = sieveOfEratosthenes(n);

    // Bước 2 & 3: Khởi tạo tổng và duyệt các số
    long long sum = 0;

    for (int i = 2; i <= n; ++i) {
        // Bước 4: Nếu i là số nguyên tố
        if (is_prime[i]) {
            // Cộng i vào tổng và lấy mô đun M ngay lập tức
            sum = (sum + i) % m;
        }
    }

    // Bước 5: Trả về kết quả cuối cùng
    return sum;
}

// Ví dụ sử dụng hàm sumPrimesModulo
int main_combined_example() {
    int n = 100;   // Tìm tổng các số nguyên tố <= 100
    int m = 1000;  // Lấy kết quả modulo 1000

    long long result = sumPrimesModulo(n, m);
    std::cout << "Tong cac so nguyen to nho hon hoac bang " << n
              << " modulo " << m << " la: " << result << std::endl;

    n = 10000; // Phạm vi lớn hơn
    m = 1000000007; // Mô đun lớn (thường dùng trong lập trình thi đấu)

    result = sumPrimesModulo(n, m);
    std::cout << "Tong cac so nguyen to nho hon hoac bang " << n
              << " modulo " << m << " la: " << result << std::endl; // Kết quả sẽ được tính đúng modulo M

    return 0;
}

Giải thích code:

• Chúng ta tái sử dụng hàm sieveOfEratosthenes đã viết ở trên.
• Hàm sumPrimesModulo(int n, int m) nhận giới hạn n và mô đun m.
• Gọi sieveOfEratosthenes(n) để có vector is_prime.
• Khởi tạo sum kiểu long long để tránh tràn số trước khi lấy mô đun (mặc dù với phép cộng từng bước thì long long có thể không bắt buộc nếu m không quá lớn, nhưng dùng long long là an toàn).
• Duyệt từ 2 đến N.
• Nếu is_prime[i] là true, ta cộng i vào sum. Phép tính quan trọng là sum = (sum + i) % m;. Điều này đảm bảo sum luôn nằm trong phạm vi [0, m-1], ngăn chặn tràn số ngay cả khi tổng các số nguyên tố rất lớn. Đây chính là ứng dụng trực tiếp của tính chất cộng của đồng dư.
• Hàm main_combined_example minh họa cách gọi hàm với các tham số khác nhau.

Độ phức tạp: Độ phức tạp chính là độ phức tạp của Sàng Eratosthenes, tức O(N log log N), cộng thêm một vòng lặp duyệt N số để tính tổng (O(N)). Tổng cộng vẫn là O(N log log N), rất hiệu quả.

Bài tập ví dụ:

Sinh vật trong sở thú

Trong một chuyến tham quan sở thú, FullHouse Dev được giao nhiệm vụ nghiên cứu về hai loài sinh vật đặc biệt. Họ nhận thấy rằng mỗi loài có số tay khác nhau và cần tìm ra cách để các sinh vật có thể nắm tay nhau một cách hợp lý nhất.

Bài toán

Trong sở thú có hai loại sinh vật, loại A có \(a\) tay và loại B có \(b\) tay. Nhiệm vụ là tìm ra số lượng sinh vật ít nhất sao cho chúng có thể nắm tay nhau theo các điều kiện sau:

• Mỗi sinh vật chỉ được nắm tay với sinh vật khác loại
• Mỗi sinh vật phải sử dụng hết số tay của mình
• Đảm bảo rằng với điều kiện đã cho, đáp án là duy nhất

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 hai số nguyên \(a\) và \(b\) - số tay của sinh vật loại A và loại B

OUTPUT FORMAT:

• \(T\) dòng, mỗi dòng chứa hai số nguyên \(x\) và \(y\) - số lượng sinh vật loại A và số lượng sinh vật loại B cần thiết. Lưu ý rằng tổng \(x + y\) phải là nhỏ nhất có thể

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq a, b \leq 100\)

Ví dụ

INPUT

1
20 2

OUTPUT

1 10

Giải thích

• Cần ít nhất 1 sinh vật loại A và 10 sinh vật loại B
• Một sinh vật loại A có 20 tay
• Mười sinh vật loại B có tổng cộng 20 tay
• Như vậy, các sinh vật có thể nắm tay nhau theo đúng yêu cầu đề bài ```cpp // Hướng dẫn giải bài "Sinh vật trong sở thú"

/*

1. Phân tích yêu cầu:

   • Có x sinh vật loại A (mỗi con có a tay) và y sinh vật loại B (mỗi con có b tay).
   • Tổng số tay loại A: x * a.
   • Tổng số tay loại B: y * b.
   • Mỗi sinh vật dùng hết tay.
   • Nắm tay chỉ xảy ra giữa loại A và loại B.
   • Điều này có nghĩa là tổng số tay của loại A phải bằng tổng số tay của loại B để không có tay nào bị thừa.
   • Phương trình cần giải: x * a = y * b.
   • Cần tìm cặp số nguyên dương (x, y) thỏa mãn phương trình và có tổng x + y nhỏ nhất.

2. Tìm giải pháp tối thiểu:

   • Từ phương trình x * a = y * b, ta có tỷ lệ x / y = b / a.
   • Để tìm cặp số nguyên dương (x, y) nhỏ nhất thỏa mãn tỷ lệ này, ta cần rút gọn phân số b/a về dạng tối giản.
   • Cách rút gọn phân số b/a là chia cả tử số b và mẫu số a cho ước chung lớn nhất (UCLN) của chúng.
   • Gọi g = UCLN(a, b).
   • Khi đó, b / a = (b / g) / (a / g).
   • Cặp số nguyên dương nhỏ nhất thỏa mãn x / y = (b/g) / (a/g) chính là x = b/g và y = a/g.

3. Các bước thực hiện:

   • Đọc số lượng test case T.
   • Lặp lại T lần:
     • Đọc hai số a và b.
     • Tính ước chung lớn nhất g của a và b. Có thể dùng thuật toán Euclid hoặc hàm std::gcd trong C++ (cần include <numeric>, có từ C++17).
     • Kết quả x là b / g.
     • Kết quả y là a / g.
     • In ra x và y, cách nhau một khoảng trắng, kết thúc bằng xuống dòng.

4. Hàm UCLN (nếu không dùng std::gcd):

   • Có thể viết một hàm int gcd(int p, int q) sử dụng thuật toán Euclid:

     int gcd(int p, int q) {
         while (q != 0) {
             int temp = q;
             q = p % q;
             p = temp;
         }
         return p;
     }
     

*/

// Gợi ý về cấu trúc code C++: /*

include <iostream>

include <numeric> // Cho std::gcd (C++17 trở lên), nếu không thì tự cài hàm gcd

// Viết hàm gcd nếu cần (trước C++17) // int gcd(int a, int b) { ... }

int main() { // Tắt đồng bộ cout và cin cho nhanh (tùy chọn) std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

int T;
std::cin >> T;
while (T--) {
    int a, b;
    std::cin >> a >> b;

    // Tính UCLN
    int common_divisor = std::gcd(a, b); // Hoặc dùng hàm gcd tự cài: gcd(a, b);

    // Tính số lượng sinh vật
    int x = b / common_divisor;
    int y = a / common_divisor;

    // In kết quả
    std::cout << x << " " << y << std::endl;
}
return 0;

} */ ```

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