Bài 3.1. Kiểm tra số nguyên tố và sàng Eratosthenes

Chào mừng quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của chúng ta! Hôm nay, chúng ta sẽ khám phá một chủ đề kinh điển nhưng vô cùng quan trọng trong lập trình và toán học: số nguyên tố. Chúng ta sẽ không chỉ tìm hiểu cách kiểm tra xem một số có phải là nguyên tố hay không, mà còn khám phá một giải thuật cực kỳ hiệu quả để tìm tất cả các số nguyên tố trong một phạm vi nhất định: Sàng Eratosthenes. Hãy cùng bắt đầu hành trình khám phá này!

Số Nguyên Tố Là Gì?

Trước khi đi sâu vào các giải thuật, hãy làm rõ định nghĩa. Một số nguyên tố là một số nguyên dương lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Ví dụ:

2 là số nguyên tố (ước: 1, 2)
3 là số nguyên tố (ước: 1, 3)
4 không phải là số nguyên tố (ước: 1, 2, 4)
5 là số nguyên tố (ước: 1, 5)
6 không phải là số nguyên tố (ước: 1, 2, 3, 6)
7 là số nguyên tố (ước: 1, 7)

Các số 0 và 1 theo định nghĩa không phải là số nguyên tố. Số 1 chỉ có một ước dương duy nhất là 1, còn số 0 có vô số ước.

Số nguyên dương lớn hơn 1 mà không phải là số nguyên tố được gọi là hợp số.

Việc kiểm tra và tìm kiếm số nguyên tố có rất nhiều ứng dụng trong thực tế, từ mã hóa (cryptography) cho đến các bài toán trong lý thuyết số và tin học. Do đó, việc nắm vững các phương pháp hiệu quả là cực kỳ cần thiết.

Phương Pháp 1: Kiểm Tra Số Nguyên Tố "Ngây Ngô" (Naive Check)

Phương pháp đơn giản nhất để kiểm tra một số n có phải là số nguyên tố hay không dựa trực tiếp vào định nghĩa. Nếu n <= 1, chắc chắn nó không phải số nguyên tố. Nếu n > 1, ta chỉ cần kiểm tra xem nó có ước nào khác 1 và n hay không. Các ước có thể có chỉ nằm trong khoảng từ 2 đến n-1.

Chúng ta có thể duyệt từ 2 đến n-1. Nếu tìm thấy bất kỳ số i nào trong khoảng này mà n chia hết cho i (tức là n % i == 0), thì n có ít nhất 3 ước là 1, i, và n, do đó nó là hợp số. Nếu duyệt hết khoảng này mà không tìm thấy ước nào, thì n là số nguyên tố.

Đây là code minh họa bằng C++:

#include <iostream>

// Hàm kiểm tra số nguyên tố theo phương pháp ngây ngô
bool isPrimeNaive(int n) {
    // Số nhỏ hơn hoặc bằng 1 không phải số nguyên tố
    if (n <= 1) {
        return false;
    }

    // Duyệt từ 2 đến n-1
    for (int i = 2; i < n; ++i) {
        // Nếu n chia hết cho i, thì n không phải số nguyên tố
        if (n % i == 0) {
            return false;
        }
    }

    // Nếu không tìm thấy ước nào trong khoảng từ 2 đến n-1, n là số nguyên tố
    return true;
}

int main() {
    int num1 = 7;
    int num2 = 10;
    int num3 = 1;

    cout << num1 << " is prime? " << (isPrimeNaive(num1) ? "Yes" : "No") << endl;
    cout << num2 << " is prime? " << (isPrimeNaive(num2) ? "Yes" : "No") << endl;
    cout << num3 << " is prime? " << (isPrimeNaive(num3) ? "Yes" : "No") << endl;

    return 0;
}

Giải thích code:

#include <iostream>: Thư viện nhập xuất cơ bản trong C++.
bool isPrimeNaive(int n): Định nghĩa một hàm nhận vào số nguyên n và trả về true nếu n là nguyên tố, false nếu ngược lại.
if (n <= 1) { return false; }: Xử lý trường hợp đặc biệt: số <= 1 không phải nguyên tố.
for (int i = 2; i < n; ++i): Vòng lặp duyệt qua các số i từ 2 đến n-1.
if (n % i == 0): Kiểm tra xem n có chia hết cho i hay không. Toán tử % là toán tử lấy phần dư. Nếu phần dư bằng 0, tức là n chia hết cho i.
return false;: Nếu tìm thấy ước i, hàm kết thúc ngay lập tức và trả về false.
return true;: Nếu vòng lặp kết thúc mà không tìm thấy ước nào (tức là không có lần nào return false được gọi), thì n là số nguyên tố, hàm trả về true.
Hàm main chỉ đơn giản là gọi isPrimeNaive với vài ví dụ và in kết quả ra màn hình.

Đánh giá: Phương pháp này đúng, nhưng hiệu quả không cao lắm. Đối với một số n, trong trường hợp xấu nhất (khi n là số nguyên tố hoặc là hợp số của hai số nguyên tố lớn gần n/2), ta phải thực hiện gần n phép chia. Độ phức tạp thời gian của giải thuật này là O(n). Với các số n lớn, điều này có thể rất chậm.

Phương Pháp 2: Cải Tiến Kiểm Tra Số Nguyên Tố (Optimized Check)

Chúng ta có thể nhận thấy một điểm quan trọng: Nếu i là một ước của n, thì n/i cũng là một ước của n. Ví dụ, nếu n = 100, các cặp ước là (1, 100), (2, 50), (4, 25), (5, 20), (10, 10).

Quan sát các cặp ước (trừ trường hợp căn bậc hai chính xác): trong mỗi cặp (i, n/i), một số sẽ nhỏ hơn hoặc bằng căn bậc hai của n, và số kia sẽ lớn hơn hoặc bằng căn bậc hai của n. Ví dụ với n=100, sqrt(100)=10. Các cặp là (2, 50), (4, 25), (5, 20) - trong mỗi cặp, một số <= 10, một số >= 10. Cặp (10, 10) cả hai đều bằng 10.

Điều này có nghĩa là, nếu n có bất kỳ ước nào khác 1 và n, nó nhất định phải có một ước nhỏ hơn hoặc bằng căn bậc hai của n. Ngược lại, nếu n không có ước nào trong khoảng từ 2 đến sqrt(n), thì nó cũng sẽ không có ước nào lớn hơn sqrt(n) (vì nếu có ước j > sqrt(n), thì n/j sẽ là ước và n/j < sqrt(n), mâu thuẫn với giả định ban đầu).

Do đó, để kiểm tra số nguyên tố n, ta chỉ cần duyệt các số i từ 2 đến phần nguyên của sqrt(n). Nếu tìm thấy ước nào trong khoảng này, n không phải là nguyên tố. Nếu duyệt hết mà không thấy, n là nguyên tố.

Đây là code minh họa bằng C++:

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

// Hàm kiểm tra số nguyên tố theo phương pháp cải tiến
bool isPrimeOptimized(int n) {
    // Số nhỏ hơn hoặc bằng 1 không phải số nguyên tố
    if (n <= 1) {
        return false;
    }

    // Số 2 là số nguyên tố duy nhất chẵn
    if (n == 2) {
        return true;
    }

    // Các số chẵn lớn hơn 2 không phải số nguyên tố
    if (n % 2 == 0) {
        return false;
    }

    // Duyệt từ 3 đến sqrt(n), chỉ xét các số lẻ
    // i*i <= n tương đương với i <= sqrt(n)
    for (int i = 3; i * i <= n; i += 2) {
        // Nếu n chia hết cho i, thì n không phải số nguyên tố
        if (n % i == 0) {
            return false;
        }
    }

    // Nếu không tìm thấy ước nào trong khoảng này, n là số nguyên tố
    return true;
}

int main() {
    int num1 = 7;
    int num2 = 10;
    int num3 = 1;
    int num4 = 97; // Một số nguyên tố lớn hơn

    cout << num1 << " is prime? " << (isPrimeOptimized(num1) ? "Yes" : "No") << endl;
    cout << num2 << " is prime? " << (isPrimeOptimized(num2) ? "Yes" : "No") << endl;
    cout << num3 << " is prime? " << (isPrimeOptimized(num3) ? "Yes" : "No") << endl;
    cout << num4 << " is prime? " << (isPrimeOptimized(num4) ? "Yes" : "No") << endl;

    return 0;
}

Giải thích code:

#include <cmath>: Thêm thư viện cmath để sử dụng hàm sqrt (căn bậc hai).
if (n <= 1) { return false; }: Vẫn xử lý trường hợp <= 1.
if (n == 2) { return true; }: Xử lý trường hợp số 2 riêng. Số 2 là số nguyên tố chẵn duy nhất.
if (n % 2 == 0) { return false; }: Sau khi xử lý số 2, bất kỳ số chẵn nào lớn hơn 2 đều không phải nguyên tố (vì nó chia hết cho 2), nên ta loại bỏ ngay. Điều này giúp ta chỉ cần kiểm tra các ước lẻ sau này.
for (int i = 3; i * i <= n; i += 2): Vòng lặp bắt đầu từ 3, chỉ tăng i thêm 2 mỗi lần (i += 2) để chỉ xét các số lẻ (3, 5, 7, 9...). Điều kiện dừng là i * i <= n. Việc sử dụng i * i <= n thay vì i <= sqrt(n) thường được ưu tiên hơn trong lập trình nguyên vì nó tránh việc tính toán căn bậc hai với số thực, có thể gây sai số nhỏ hoặc chậm hơn trên một số kiến trúc máy tính.
if (n % i == 0) { return false; }: Kiểm tra chia hết cho các số lẻ i.
return true;: Nếu vòng lặp kết thúc, n là nguyên tố.

Đánh giá: Phương pháp này hiệu quả hơn đáng kể. Thay vì duyệt n lần, ta chỉ duyệt khoảng sqrt(n) lần. Hơn nữa, việc loại bỏ các số chẵn (trừ 2) giúp giảm số lượng phép chia xuống gần một nửa. Độ phức tạp thời gian của giải thuật này là O(sqrt(n)). Với các số n rất lớn (ví dụ, hàng tỷ), sqrt(n) nhỏ hơn n rất nhiều (sqrt(1 tỷ) khoảng 31622), giúp việc kiểm tra trở nên khả thi hơn nhiều.

Tuy nhiên, cả hai phương pháp trên đều chỉ dùng để kiểm tra một số duy nhất. Điều gì xảy ra nếu chúng ta cần tìm tất cả các số nguyên tố trong một phạm vi lớn, ví dụ từ 1 đến 1.000.000? Việc gọi isPrimeOptimized cho từng số từ 1 đến 1.000.000 vẫn sẽ rất tốn kém. Lúc này, chúng ta cần một giải thuật tối ưu hơn cho bài toán tìm kiếm hàng loạt: Sàng Eratosthenes.

Phương Pháp 3: Sàng Eratosthenes

Sàng Eratosthenes (Sieve of Eratosthenes) là một giải thuật cổ xưa (khoảng thế kỷ thứ 3 TCN) dùng để 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 cho trước. Ý tưởng chính rất đơn giản và thông minh: thay vì kiểm tra từng số xem nó có phải nguyên tố hay không, ta sẽ đánh dấu các số không phải nguyên tố (hợp số) một cách có hệ thống. Những số còn lại không bị đánh dấu chính là số nguyên tố.

Các bước thực hiện Sàng Eratosthenes để tìm số nguyên tố đến giới hạn N:

Tạo một danh sách (hoặc mảng) các số nguyên liên tiếp từ 0 đến N. Ban đầu, giả định tất cả các số (trừ 0 và 1) đều là số nguyên tố. Ta thường dùng một mảng boolean isPrime[0...N] và khởi tạo tất cả các giá trị từ isPrime[2] trở đi là true. isPrime[0] và isPrime[1] được đánh dấu false.
Bắt đầu với số nguyên tố nhỏ nhất là p = 2.
Đánh dấu bội số: Duyệt qua tất cả các bội số của p lớn hơn p*p và nhỏ hơn hoặc bằng N, và đánh dấu chúng là hợp số (gán isPrime[bội_số] = false). Tại sao lại bắt đầu từ p*p? Bởi vì các bội số nhỏ hơn p*p (tức là p * k với k < p) đã bị đánh dấu là hợp số bởi các số nguyên tố nhỏ hơn p (ví dụ, 4 và 6 bị đánh dấu bởi 2; 9 bị đánh dấu bởi 3; 10 bị đánh dấu bởi 2...).
Tìm số tiếp theo lớn hơn p mà chưa bị đánh dấu là hợp số. Gán số đó cho p.
Nếu p * p > N, dừng giải thuật. Tất cả các số còn lại trong danh sách chưa bị đánh dấu là số nguyên tố. (Tại sao lại dừng ở p*p > N? Giống như ý tưởng tối ưu ở phương pháp 2, nếu một số m nhỏ hơn hoặc bằng N là hợp số, nó phải có một ước nguyên tố p nhỏ hơn hoặc bằng sqrt(m). Nếu m <= N, thì sqrt(m) <= sqrt(N). Do đó, nếu ta đã xử lý tất cả các số nguyên tố p sao cho p <= sqrt(N) (tức là p*p <= N), thì tất cả các hợp số đến N đã bị đánh dấu.)
Nếu p * p <= N, quay lại bước 3.

Kết thúc giải thuật, những chỉ số i mà isPrime[i] vẫn là true chính là các số nguyên tố nhỏ hơn hoặc bằng N.

Hãy xem code C++ minh họa Sàng Eratosthenes:

#include <iostream>
#include <vector>
#include <cmath> // Cần cho sqrt, mặc dù ta dùng i*i <= n để tránh
#include <numeric> // Để sử dụng iota nếu muốn khởi tạo mảng số

// Hàm thực hiện Sàng Eratosthenes để tìm tất cả số nguyên tố đến N
vector<bool> sieveOfEratosthenes(int N) {
    // 1. Tạo mảng boolean và khởi tạo
    // Kích thước N+1 để bao gồm cả số N
    vector<bool> isPrime(N + 1, true);

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

    // 2. Bắt đầu sàng từ p = 2
    // Chỉ cần duyệt đến sqrt(N)
    // i*i <= N tương đương i <= sqrt(N)
    for (int p = 2; p * p <= N; ++p) {
        // Nếu isPrime[p] vẫn là true, tức là p là số nguyên tố
        if (isPrime[p] == true) {
            // 3. Đánh dấu tất cả các bội số của p là hợp số
            // Bắt đầu từ p*p, vì các bội nhỏ hơn đã được xử lý bởi các số nguyên tố nhỏ hơn p
            // Tăng lên p mỗi lần (p*p + p, p*p + 2p, ...)
            for (int i = p * p; i <= N; i += p)
                isPrime[i] = false;
        }
    }

    // Mảng isPrime[0...N] bây giờ chứa kết quả:
    // isPrime[i] == true nghĩa là i là số nguyên tố
    return isPrime;
}

int main() {
    int limit = 100; // Tìm tất cả số nguyên tố đến 100

    vector<bool> primes = sieveOfEratosthenes(limit);

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

    // Ví dụ khác: tìm số nguyên tố đến 30
    int limit2 = 30;
    vector<bool> primes2 = sieveOfEratosthenes(limit2);
    cout << "So nguyen to nho hon hoac bang " << limit2 << " la:" << endl;
    for (int p = 2; p <= limit2; ++p) {
        if (primes2[p]) {
            cout << p << " ";
        }
    }
    cout << endl;


    return 0;
}

Giải thích code:

#include <vector>: Thư viện cần thiết để sử dụng vector.
vector<bool> sieveOfEratosthenes(int N): Hàm nhận vào giới hạn N và trả về một vector<bool> có kích thước N+1. Phần tử tại chỉ số i của vector này sẽ là true nếu i là số nguyên tố, và false nếu ngược lại.
vector<bool> isPrime(N + 1, true);: Khởi tạo vector isPrime với N+1 phần tử, tất cả đều là true ban đầu. Chỉ số của vector tương ứng với số nguyên mà ta đang xét.
isPrime[0] = isPrime[1] = false;: Đánh dấu 0 và 1 không phải là số nguyên tố.
for (int p = 2; p * p <= N; ++p): Vòng lặp ngoài duyệt qua các số p bắt đầu từ 2. Ta chỉ cần duyệt đến sqrt(N) như đã giải thích.
if (isPrime[p] == true): Kiểm tra xem số p hiện tại có còn được đánh dấu là nguyên tố không. Nếu có, nó là một số nguyên tố thực sự (chưa bị các số nhỏ hơn sàng loại).
for (int i = p * p; i <= N; i += p): Nếu p là nguyên tố, vòng lặp trong sẽ duyệt qua tất cả các bội số của p từ p*p trở đi, tăng p mỗi lần (p*p, p*p + p, p*p + 2p, ...).
isPrime[i] = false;: Đánh dấu các bội số này là hợp số.
return isPrime;: Sau khi vòng lặp ngoài kết thúc, vector isPrime chứa kết quả sàng.

Đánh giá: Sàng Eratosthenes cực kỳ hiệu quả khi cần tìm nhiều số nguyên tố trong một phạm vi.

Độ phức tạp thời gian: O(N log log N). Nghe có vẻ phức tạp, nhưng trên thực tế, log log N tăng trưởng rất chậm. Đối với các giá trị N thông thường trong lập trình thi đấu hoặc ứng dụng thực tế, độ phức tạp này gần như là tuyến tính với N. Nó nhanh hơn rất nhiều so với việc gọi isPrimeOptimized cho từng số từ 1 đến N (độ phức tạp sẽ là O(N * sqrt(N))).
Độ phức tạp không gian: O(N). Sàng Eratosthenes yêu cầu một mảng boolean có kích thước N+1 để lưu trữ trạng thái của mỗi số. Điều này có nghĩa là bộ nhớ sử dụng tăng tuyến tính theo N. Đối với các giới hạn N rất lớn (ví dụ, hàng tỷ), bộ nhớ có thể trở thành vấn đề. Tuy nhiên, với các giới hạn N phổ biến (ví dụ, đến 10^6 hoặc 10^7), O(N) bộ nhớ là hoàn toàn chấp nhận được.

Sàng Eratosthenes là giải thuật tiêu chuẩn khi bạn cần một danh sách các số nguyên tố lên đến một giới hạn nhất định.

Khi Nào Sử Dụng Phương Pháp Nào?

Kiểm tra MỘT số duy nhất: Sử dụng phương pháp cải tiến O(sqrt(n)) (isPrimeOptimized). Nó nhanh và không tốn nhiều bộ nhớ.
Tìm TẤT CẢ số nguyên tố trong một phạm vi đến N: Sử dụng Sàng Eratosthenes O(N log log N). Mặc dù tốn O(N) bộ nhớ, nhưng thời gian tính toán để tìm tất cả các số nguyên tố trong phạm vi là vượt trội so với việc kiểm tra từng số riêng lẻ.

Phương pháp ngây ngô O(n) hiếm khi được sử dụng trong thực tế khi n có thể lớn, nó chủ yếu mang tính giới thiệu về ý tưởng cơ bản.

Bài tập ví dụ:

Sức khỏe của mọi người

Trong một dự án về dinh dưỡng cộng đồng, FullHouse Dev được giao nhiệm vụ theo dõi sức khỏe của người dân trong thành phố thông qua việc đi bộ. Với kinh nghiệm trong việc phân tích dữ liệu, nhóm bắt đầu nghiên cứu mô hình để tối ưu hóa việc theo dõi sức khỏe của từng người dân.

Bài toán

Có \(N\) người trong thành phố. Người thứ \(i\) có \(H_i\) điểm sức khỏe. FullHouse Dev sẽ tổ chức đi bộ trong \(D\) ngày. Vào ngày thứ \(j\), mỗi lần đi bộ sẽ làm giảm \(L_j\) điểm sức khỏe của người tham gia. Trong ngày thứ \(j\), một người chỉ có thể tham gia đi bộ nếu họ vẫn còn khỏe mạnh và \(j\) là bội số của \(i\). Mỗi người chỉ có thể đi bộ một lần mỗi ngày.

Một người được coi là không khỏe nếu điểm sức khỏe của họ nhỏ hơn hoặc bằng 0. Cuối mỗi ngày, điểm sức khỏe sẽ được phục hồi về mức ban đầu nếu họ chưa rơi vào trạng thái không khỏe.

INPUT FORMAT:

Dòng đầu tiên: Số nguyên \(T\) là số lượng test case
Với mỗi test case:
- Dòng đầu: Hai số nguyên \(N\) và \(D\) lần lượt là số người và số ngày đi bộ
- Dòng tiếp theo: \(N\) số nguyên, số thứ \(i\) biểu thị điểm sức khỏe của người thứ \(i\)
- Dòng tiếp theo: \(D\) số nguyên, số thứ \(j\) biểu thị mức giảm sức khỏe trong ngày thứ \(j\)

OUTPUT FORMAT:

In ra \(N\) dòng, dòng thứ \(i\) chứa một số nguyên biểu thị ngày mà người thứ \(i\) trở nên không khỏe. Nếu người đó luôn khỏe mạnh, in ra -1.

Ràng buộc:

\(1 \leq T \leq 100\)
\(1 \leq N, D \leq 100\)
\(1 \leq H_i \leq 100\)
\(1 \leq L_j \leq 100\)

Ví dụ

INPUT

2
6 5
2 1 6 4 3 7
2 3 7 3 4
3 3
2 1 3
2 2 2

OUTPUT

Giải thích

Trong test case đầu tiên:

Người thứ 1 và 2 trở nên không khỏe vào ngày 1
Người thứ 3 trở nên không khỏe vào ngày 3
Người thứ 4 luôn khỏe mạnh
Người thứ 5 trở nên không khỏe vào ngày 5
Người thứ 6 trở nên không khỏe vào ngày 3 Tuyệt vời! Dưới đây là hướng giải ngắn gọn cho bài toán "Sức khỏe của mọi người" bằng C++:

Phân tích bài toán và quy tắc:
- Có N người, người i có sức khỏe ban đầu H_i.
- Có D ngày, ngày j có mức giảm sức khỏe L_j.
- Quy tắc mấu chốt: Người i (với chỉ số/số thứ tự i từ 1 đến N) chỉ có thể tham gia đi bộ vào ngày j (với chỉ số ngày j từ 1 đến D) nếu i là bội số của j (nghĩa là i % j == 0) VÀ người đó chưa không khỏe.
- Nếu tham gia, sức khỏe giảm đi L_j.
- Người đó trở nên không khỏe vĩnh viễn nếu sức khỏe <= 0 sau khi đi bộ.
- Cuối mỗi ngày, sức khỏe phục hồi về mức ban đầu (H_i) nếu người đó chưa rơi vào trạng thái không khỏe. Điều này ngụ ý rằng mỗi lần một người tham gia đi bộ vào ngày j (khi i % j == 0), ta kiểm tra xem H_i - L_j <= 0 hay không. Nếu có, ngày j là ngày đầu tiên họ trở nên không khỏe.
Cách tiếp cận:
- Với ràng buộc N, D <= 100, chúng ta có thể sử dụng phương pháp mô phỏng (simulation) trực tiếp từng ngày một.
- Duyệt qua từng ngày từ ngày 1 đến ngày D.
- Trong mỗi ngày, duyệt qua từng người từ người 1 đến người N.
- Kiểm tra xem người i có đủ điều kiện để đi bộ vào ngày j hay không dựa trên quy tắc (i % j == 0) và trạng thái sức khỏe hiện tại của họ (chưa không khỏe).
- Nếu đủ điều kiện, tính toán xem việc đi bộ trong ngày j có làm cho sức khỏe của họ (H_i) giảm xuống <= 0 hay không (tức là H_i - L_j <= 0).
- Nếu có, ghi nhận ngày j là ngày mà người i trở nên không khỏe và đánh dấu người này là đã không khỏe để không xét họ trong các ngày tiếp theo.
Lưu trữ trạng thái:
- Cần lưu trữ điểm sức khỏe ban đầu của N người (ví dụ: trong một mảng hoặc vector H).
- Cần lưu trữ mức giảm sức khỏe của D ngày (ví dụ: trong một mảng hoặc vector L).
- Cần lưu trữ kết quả: ngày mà mỗi người trở nên không khỏe. Khởi tạo mảng/vector kết quả với giá trị -1 cho tất cả N người, biểu thị họ vẫn khỏe mạnh. Khi một người không khỏe vào ngày j, cập nhật giá trị tại vị trí tương ứng trong mảng kết quả thành j.
- Cần một cách để đánh dấu những người đã không khỏe để không xử lý họ nữa (ví dụ: một mảng boolean is_unhealthy).
Thuật toán chi tiết:
- Đọc số lượng test case T.
- Lặp T lần:
  - Đọc N và D.
  - Đọc N giá trị sức khỏe ban đầu vào vector H (kích thước N).
  - Đọc D giá trị mức giảm sức khỏe vào vector L (kích thước D).
  - Khởi tạo vector unhealthy_day kích thước N với tất cả giá trị là -1.
  - Khởi tạo vector boolean is_unhealthy kích thước N với tất cả giá trị là false.
  - Lặp qua các ngày j từ 1 đến D:
    - Lặp qua các người i từ 1 đến N:
      - Sử dụng chỉ số 0-based cho các vector (H, L, unhealthy_day, is_unhealthy). Người i tương ứng với chỉ số i-1, ngày j tương ứng với chỉ số j-1.
      - Nếu người i-1 chưa không khỏe (is_unhealthy[i-1] là false):
        
        Kiểm tra điều kiện đi bộ: i % j == 0.
        
        Nếu điều kiện đúng:
        
        Kiểm tra xem việc đi bộ ngày hôm nay có làm họ không khỏe không: H[i-1] - L[j-1] <= 0. Nếu đúng: Ghi nhận ngày không khỏe: unhealthy_day[i-1] = j; Đánh dấu là không khỏe: is_unhealthy[i-1] = true;
  - In ra các giá trị trong vector unhealthy_day, mỗi giá trị trên một dòng.
Lưu ý cài đặt:
- Sử dụng vector để lưu trữ dữ liệu.
- Cẩn thận với chỉ số mảng/vector (0-based vs. 1-based). Người i (1-based) tương ứng với chỉ số i-1 (0-based). Ngày j (1-based) tương ứng với chỉ số j-1 (0-based).
- Để tăng tốc độ nhập/xuất trong C++, có thể thêm ios_base::sync_with_stdio(false); cin.tie(NULL); ở đầu hàm main.

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

Comments

There are no comments at the moment.