Bài 3.2: Phân tích thừa số nguyên tố và ứng dụng

Chào mừng bạn đến với bài viết tiếp theo trong chuỗi blog về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ khám phá một khái niệm cực kỳ quan trọng và nền tảng trong lý thuyết số, có ứng dụng rộng rãi trong nhiều lĩnh vực của khoa học máy tính: Phân tích thừa số nguyên tố (Prime Factorization).

Tại sao một chủ đề toán học tưởng chừng đơn giản lại xuất hiện trong chuỗi bài về CTDL&GT? Bởi vì việc hiểu cách phân tích số và các tính chất liên quan sẽ mở ra cánh cửa đến nhiều giải thuật hiệu quả để giải quyết các bài toán liên quan đến số học, và là nền tảng cho nhiều ứng dụng phức tạp hơn.

Thừa số nguyên tố là gì?

Trước khi đi sâu vào phân tích, hãy nhắc lại một chút về số nguyên tố (prime number). Số nguyên tố là các số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Các số nguyên tố đầu tiên là 2, 3, 5, 7, 11, 13, ...

Phân tích thừa số nguyên tố của một số nguyên dương lớn hơn 1 là quá trình biểu diễn số đó dưới dạng tích của các số nguyên tố. Nói cách khác, chúng ta tìm kiếm những "viên gạch xây dựng" nguyên tố nhỏ nhất mà khi nhân chúng lại với nhau sẽ tạo thành số ban đầu.

Ví dụ:

12 = 2 2 3 = $2^2 * 3^1$
100 = 2 2 5 5 = $2^2 5^2$
56 = 2 2 2 7 = $2^3 7^1$
7 = $7^1$ (7 là số nguyên tố, nên phân tích của nó chính là nó)

Định lý cơ bản của số học khẳng định rằng: Mọi số nguyên dương lớn hơn 1 đều có thể được phân tích thành tích các thừa số nguyên tố một cách duy nhất (chỉ khác nhau về thứ tự các thừa số). Đây là một định lý mạnh mẽ, cho thấy các số nguyên tố thực sự là nền tảng của tập hợp các số tự nhiên.

Thuật toán phân tích thừa số nguyên tố

Có nhiều cách để phân tích một số thành thừa số nguyên tố. Phương pháp đơn giản và phổ biến nhất cho các số có kích thước vừa phải là phương pháp chia thử (Trial Division). Ý tưởng rất đơn giản: chúng ta lần lượt chia số đó cho các số nguyên tố bắt đầu từ số nhỏ nhất (là 2) cho đến khi không thể chia hết nữa.

Các bước thực hiện thuật toán chia thử:

Kiểm tra xem số $N$ có chia hết cho 2 hay không. Nếu có, đếm số lần chia hết và chia $N$ cho 2 tương ứng. Lặp lại cho đến khi $N$ không còn chia hết cho 2.
Sau khi xử lý hết thừa số 2, ta chỉ còn xét các thừa số nguyên tố lẻ. Bắt đầu từ số 3, kiểm tra xem $N$ có chia hết cho 3 hay không. Nếu có, đếm số lần và chia $N$ cho 3.
Tiếp tục quá trình này với các số lẻ tiếp theo (5, 7, 11, 13, ...) chỉ cần kiểm tra các số nguyên tố (nhưng việc kiểm tra mọi số lẻ cũng không ảnh hưởng đến tính đúng đắn, chỉ kém hiệu quả hơn một chút) cho đến khi số chia vượt quá căn bậc hai của $N$ hiện tại.
Tại sao chỉ cần kiểm tra đến $\sqrt{N}$? Giả sử $N$ có một thừa số nguyên tố $p$ lớn hơn $\sqrt{N}$. Khi đó, thừa số còn lại $N/p$ phải nhỏ hơn $\sqrt{N}$. Nếu $N/p$ là số nguyên tố, ta đã tìm thấy nó khi chia thử các số nhỏ hơn $\sqrt{N}$. Nếu $N/p$ là hợp số, nó phải có ít nhất một thừa số nguyên tố nhỏ hơn hoặc bằng $\sqrt{N}$, và ta cũng đã tìm thấy thừa số đó trong quá trình chia thử. Do đó, nếu sau khi chia thử tất cả các số nguyên tố (hoặc số lẻ) đến $\sqrt{N}$ mà số $N$ còn lại vẫn lớn hơn 1, thì số $N$ còn lại đó chính là một số nguyên tố (là thừa số nguyên tố cuối cùng, lớn hơn $\sqrt{N}$).
Nếu sau vòng lặp mà $N$ vẫn lớn hơn 1, thì giá trị $N$ cuối cùng này chính là một thừa số nguyên tố còn sót lại.

Triển khai bằng C++

Hãy cùng viết một hàm C++ để thực hiện việc phân tích thừa số nguyên tố. Chúng ta sẽ sử dụng std::map để lưu trữ các thừa số nguyên tố và số mũ tương ứng của chúng, giúp việc làm việc với kết quả dễ dàng hơn sau này.

#include <iostream>
#include <vector>
#include <cmath>
#include <map>

// Hàm phân tích thừa số nguyên tố cho số n
// Trả về một map lưu trữ { thừa số nguyên tố: số mũ }
std::map<long long, int> primeFactorize(long long n) {
    std::map<long long, int> factors;

    // Xử lý thừa số 2
    while (n % 2 == 0) {
        factors[2]++; // Tăng số mũ của thừa số 2
        n /= 2;       // Chia n cho 2
    }

    // Xử lý các thừa số lẻ từ 3 trở đi
    // Chỉ cần kiểm tra đến căn bậc hai của n hiện tại
    // i*i <= n thay vì i <= sqrt(n) để tránh số thực và có thể nhanh hơn
    for (long long i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors[i]++; // Tăng số mũ của thừa số i
            n /= i;       // Chia n cho i
        }
    }

    // Nếu n còn lại lớn hơn 2, thì n chính là một thừa số nguyên tố
    // (chỉ xảy ra nếu thừa số cuối cùng lớn hơn căn bậc hai ban đầu của số)
    if (n > 2) {
        factors[n]++;
    }

    return factors;
}

// Hàm in kết quả phân tích
void printFactors(const std::map<long long, int>& factors) {
    if (factors.empty()) {
        std::cout << "1 (special case)"; // Mặc dù hàm factorize xử lý n>1
        return;
    }

    bool first = true;
    for (const auto& pair : factors) {
        if (!first) {
            std::cout << " * ";
        }
        std::cout << pair.first;
        if (pair.second > 1) {
            std::cout << "^" << pair.second;
        }
        first = false;
    }
    std::cout << std::endl;
}

int main() {
    long long num1 = 12;
    long long num2 = 100;
    long long num3 = 56;
    long long num4 = 7;
    long long num5 = 999999937; // Một số nguyên tố lớn
    long long num6 = 1000000000000LL; // Số rất lớn

    std::cout << "Phan tich " << num1 << ": ";
    printFactors(primeFactorize(num1));

    std::cout << "Phan tich " << num2 << ": ";
    printFactors(primeFactorize(num2));

    std::cout << "Phan tich " << num3 << ": ";
    printFactors(primeFactorize(num3));

    std::cout << "Phan tich " << num4 << ": ";
    printFactors(primeFactorize(num4));

    std::cout << "Phan tich " << num5 << ": ";
    printFactors(primeFactorize(num5));

    std::cout << "Phan tich " << num6 << ": ";
    printFactors(primeFactorize(num6));

    return 0;
}

Giải thích code C++

#include directives: Chúng ta cần các thư viện chuẩn:
- <iostream>: Để nhập/xuất dữ liệu (in ra màn hình).
- <vector>: Mặc dù không dùng trực tiếp trong primeFactorize, nó thường hữu ích khi làm việc với các list số. (Có thể bỏ đi nếu chỉ dùng map).
- <cmath>: Chứa hàm sqrt, mặc dù chúng ta dùng mẹo i * i <= n để tránh nó.
- <map>: Để lưu trữ các cặp {thừa số nguyên tố: số mũ} một cách tiện lợi. std::map tự động sắp xếp các key (thừa số nguyên tố) theo thứ tự tăng dần.
primeFactorize(long long n) function:
- Hàm nhận vào một số nguyên dương n kiểu long long (để xử lý số lớn).
- std::map<long long, int> factors;: Khởi tạo một map rỗng để lưu kết quả. Key là thừa số nguyên tố (long long), value là số lần nó xuất hiện (int).
- Xử lý số 2:
  - while (n % 2 == 0): Vòng lặp này chạy miễn là n còn chia hết cho 2.
  - factors[2]++;: Tăng số đếm (số mũ) cho thừa số 2 trong map. Nếu 2 chưa có trong map, nó sẽ tự động được thêm vào với giá trị khởi tạo là 0 trước khi tăng lên 1.
  - n /= 2;: Chia n cho 2 để loại bỏ thừa số 2 vừa tìm được.
- Xử lý số lẻ:
  - for (long long i = 3; i * i <= n; i += 2): Bắt đầu vòng lặp từ i = 3, chỉ tăng i lên 2 mỗi lần (i += 2) vì chúng ta chỉ cần kiểm tra các số lẻ (số chẵn khác 2 không phải số nguyên tố). Điều kiện dừng là i * i <= n. Đây là cách hiệu quả để kiểm tra đến $\sqrt{N}$ mà không dùng hàm sqrt và tránh các vấn đề về độ chính xác của số thực.
  - while (n % i == 0): Vòng lặp bên trong này tương tự như xử lý số 2. Nó chạy miễn là n còn chia hết cho số lẻ i hiện tại.
  - factors[i]++;: Tăng số mũ của thừa số i trong map.
  - n /= i;: Chia n cho i.
- Xử lý thừa số cuối cùng:
  - if (n > 2): Sau khi vòng lặp for kết thúc, nếu n vẫn lớn hơn 2, điều đó có nghĩa là n hiện tại là một số nguyên tố còn sót lại (lớn hơn $\sqrt{N}$ ban đầu hoặc bằng số ban đầu nếu nó là nguyên tố).
  - factors[n]++;: Thêm số nguyên tố còn sót lại này vào map với số mũ là 1.
- return factors;: Trả về map chứa kết quả phân tích.
printFactors(const std::map<long long, int>& factors) function:
- Hàm này nhận vào map kết quả và in nó ra dưới dạng tích các lũy thừa (ví dụ: $2^2 * 3^1$).
- Nó lặp qua map, in từng thừa số và số mũ. Sử dụng cờ first để in dấu * ngăn cách giữa các thừa số.
main() function:
- Đây là điểm bắt đầu của chương trình.
- Chúng ta khai báo một vài biến long long để thử nghiệm với các số khác nhau.
- Gọi hàm primeFactorize cho từng số, sau đó gọi printFactors để hiển thị kết quả.

Kết quả chạy chương trình trên sẽ cho thấy phân tích của các số đã cho.

Ứng dụng của phân tích thừa số nguyên tố

Phân tích thừa số nguyên tố không chỉ là một bài tập toán học đơn thuần. Nó là công cụ mạnh mẽ giúp giải quyết nhiều bài toán trong lập trình và lý thuyết số. Dưới đây là một vài ứng dụng quan trọng:

1. Tìm ước số chung lớn nhất (GCD) và bội số chung nhỏ nhất (LCM)

Đây là một ứng dụng kinh điển. GCD và LCM của hai số có thể dễ dàng tìm được từ phân tích thừa số nguyên tố của chúng.

Giả sử ta có hai số $A$ và $B$, và phân tích thừa số nguyên tố của chúng là: $A = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ $B = p_1^{b_1} p_2^{b_2} ... p_k^{b_k}$ (ở đây, chúng ta xét tất cả các số nguyên tố $p_i$ xuất hiện trong phân tích của ít nhất một trong hai số, với số mũ bằng 0 nếu nó không xuất hiện trong số đó).

GCD(A, B): Là tích của các số nguyên tố chung, mỗi số được nâng lên lũy thừa bằng số mũ nhỏ nhất tìm thấy trong phân tích của $A$ và $B$. $GCD(A, B) = p_1^{min(a_1, b_1)} p_2^{min(a_2, b_2)} ... * p_k^{min(a_k, b_k)}$
LCM(A, B): Là tích của tất cả các số nguyên tố xuất hiện, mỗi số được nâng lên lũy thừa bằng số mũ lớn nhất tìm thấy trong phân tích của $A$ và $B$. $LCM(A, B) = p_1^{max(a_1, b_1)} p_2^{max(a_2, b_2)} ... * p_k^{max(a_k, b_k)}$

Ví dụ: Tìm GCD và LCM của 12 và 18. 12 = $2^2 3^1$ 18 = $2^1 3^2$

GCD(12, 18) = $2^{min(2, 1)} 3^{min(1, 2)}$ = $2^1 3^1$ = 2 * 3 = 6.
LCM(12, 18) = $2^{max(2, 1)} 3^{max(1, 2)}$ = $2^2 3^2$ = 4 * 9 = 36.

(Lưu ý: Mặc dù thuật toán Euclidean hiệu quả hơn để tính GCD trong thực tế, hiểu mối liên hệ với phân tích thừa số nguyên tố giúp ta hiểu sâu hơn về tính chất của GCD và LCM.)

2. Đếm số lượng ước của một số

Nếu phân tích thừa số nguyên tố của một số $N$ là $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$, thì bất kỳ ước nào của $N$ phải có dạng $d = p_1^{b_1} p_2^{b_2} ... p_k^{b_k}$, trong đó $0 \le b_i \le a_i$ cho mỗi $i$.

Để xây dựng một ước số của $N$, chúng ta có $(a_1 + 1)$ lựa chọn cho số mũ của $p_1$ (từ 0 đến $a_1$), $(a_2 + 1)$ lựa chọn cho số mũ của $p_2$, ..., $(a_k + 1)$ lựa chọn cho số mũ của $p_k$.

Tổng số ước của $N$ sẽ là tích số các lựa chọn cho mỗi thừa số nguyên tố: Số ước = $(a_1 + 1) (a_2 + 1) ... * (a_k + 1)$

Ví dụ: Số 12 = $2^2 3^1$. Số ước của 12 là $(2 + 1) (1 + 1) = 3 2 = 6$. Các ước của 12 là: $2^0 3^0 = 1$, $2^1 3^0 = 2$, $2^2 3^0 = 4$, $2^0 3^1 = 3$, $2^1 3^1 = 6$, $2^2 * 3^1 = 12$. Đúng là có 6 ước.

Hãy viết một hàm C++ để tính số ước dựa trên kết quả phân tích:

// Hàm tính số lượng ước dựa trên map phân tích thừa số nguyên tố
long long countDivisors(const std::map<long long, int>& factors) {
    if (factors.empty()) {
        return 1; // Số 1 có 1 ước
    }

    long long num_divisors = 1;
    for (const auto& pair : factors) {
        // Số mũ của mỗi thừa số là pair.second
        // Số lựa chọn cho số mũ là (pair.second + 1)
        num_divisors *= (pair.second + 1);
    }
    return num_divisors;
}

int main() {
    long long num = 100;
    std::map<long long, int> factors = primeFactorize(num);

    std::cout << "Phan tich " << num << ": ";
    printFactors(factors);

    long long divisor_count = countDivisors(factors);
    std::cout << "So luong uoc cua " << num << " la: " << divisor_count << std::endl; // 100 = 2^2 * 5^2. So uoc: (2+1)*(2+1) = 9.

    num = 56;
    factors = primeFactorize(num);
     std::cout << "Phan tich " << num << ": ";
    printFactors(factors);
    divisor_count = countDivisors(factors);
    std::cout << "So luong uoc cua " << num << " la: " << divisor_count << std::endl; // 56 = 2^3 * 7^1. So uoc: (3+1)*(1+1) = 8.

    return 0;
}

(Thêm main mới hoặc tích hợp vào main cũ để chạy thử)

3. Tính tổng các ước của một số

Tương tự như đếm số ước, chúng ta có thể tính tổng các ước dựa trên phân tích thừa số nguyên tố. Nếu $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$, thì tổng các ước của $N$ là tích của các tổng sau: Tổng ước = $(1 + p_1 + p_1^2 + ... + p_1^{a_1}) (1 + p_2 + p_2^2 + ... + p_2^{a_2}) ... (1 + p_k + p_k^2 + ... + p_k^{a_k})$

Mỗi tổng trong ngoặc là một cấp số nhân. Tổng của cấp số nhân $1 + p + p^2 + ... + p^a$ là $(p^{a+1} - 1) / (p - 1)$.

Vậy, Tổng các ước = $\frac{p_1^{a_1+1} - 1}{p_1 - 1} \frac{p_2^{a_2+1} - 1}{p_2 - 1} ... * \frac{p_k^{a_k+1} - 1}{p_k - 1}$

(Công thức này áp dụng cho $p_i > 1$. Với các số nguyên tố, điều này luôn đúng).

Hãy viết một hàm C++ để tính tổng ước:

#include <cmath> // Can dung pow

// Ham tinh a luy thua b cho so nguyen
long long power(long long base, int exp) {
    long long res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res *= base;
        base *= base;
        exp /= 2;
    }
    return res;
}

// Hàm tính tổng các ước dựa trên map phân tích thừa số nguyên tố
long long sumDivisors(const std::map<long long, int>& factors) {
    if (factors.empty()) {
        return 1; // Số 1 có tổng ước là 1
    }

    long long total_sum = 1;
    for (const auto& pair : factors) {
        long long p = pair.first; // Thua so nguyen to
        int a = pair.second;     // So mu

        // Tinh tong 1 + p + p^2 + ... + p^a
        // Cong thuc: (p^(a+1) - 1) / (p - 1)
        // Can can than voi kieu du lieu khi tinh luy thua lon
        long long sum_power = 0;
        // Cach 1: Dung cong thuc (p^(a+1) - 1) / (p - 1)
        // sum_power = (power(p, a + 1) - 1) / (p - 1); // Can power function an toan cho long long

        // Cach 2: Tinh tong truc tiep
        long long current_power = 1;
        for(int i = 0; i <= a; ++i) {
            sum_power += current_power;
            if (i < a) current_power *= p; // De phong tran so, chi nhan khi chua dat den luy thua cao nhat can tinh
        }


        total_sum *= sum_power;
    }
    return total_sum;
}

// Main function tuong tu phan truoc, them phan goi ham sumDivisors
int main() {
    long long num = 100;
    std::map<long long, int> factors = primeFactorize(num);

    std::cout << "Phan tich " << num << ": ";
    printFactors(factors);

    long long divisor_count = countDivisors(factors);
    std::cout << "So luong uoc cua " << num << " la: " << divisor_count << std::endl;

    long long divisor_sum = sumDivisors(factors);
    std::cout << "Tong cac uoc cua " << num << " la: " << divisor_sum << std::endl; // Uoc cua 100: 1, 2, 4, 5, 10, 20, 25, 50, 100. Tong = 217.

    num = 56;
    factors = primeFactorize(num);
    std::cout << "Phan tich " << num << ": ";
    printFactors(factors);
    divisor_count = countDivisors(factors);
    std::cout << "So luong uoc cua " << num << " la: " << divisor_count << std::endl;
    divisor_sum = sumDivisors(factors);
    std::cout << "Tong cac uoc cua " << num << " la: " << divisor_sum << std::endl; // Uoc cua 56: 1, 2, 4, 7, 8, 14, 28, 56. Tong = 120.

    return 0;
}

(Again, integrate this into your main function for testing. Included a simple power function, but calculating the sum of powers directly in a loop is often safer for large numbers to prevent overflow with pow and large exponents). Self-correction: Replaced the formula method with direct summation in the loop for safety and clarity for common programming scenarios.

4. Kiểm tra số chính phương, số lập phương, v.v.

Một số $N$ là số chính phương nếu và chỉ nếu trong phân tích thừa số nguyên tố của nó $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$, tất cả* các số mũ $a_i$ đều là số chẵn. Tương tự, nó là số lập phương nếu tất cả các số mũ đều chia hết cho 3, v.v.

Ví dụ:

36 = $2^2 * 3^2$. Số mũ là 2 và 2 (đều chẵn). 36 là số chính phương ($6^2$).
100 = $2^2 * 5^2$. Số mũ là 2 và 2 (đều chẵn). 100 là số chính phương ($10^2$).
8 = $2^3$. Số mũ là 3 (chia hết cho 3). 8 là số lập phương ($2^3$).
72 = $2^3 * 3^2$. Số mũ là 3 và 2. Không phải chính phương, không phải lập phương.

Ứng dụng này rất hữu ích trong các bài toán liên quan đến căn bậc hai hoặc căn bậc ba của các số nguyên.

5. Rút gọn phân số

Để rút gọn một phân số $\frac{A}{B}$ về dạng tối giản, chúng ta có thể phân tích cả $A$ và $B$ thành thừa số nguyên tố. Sau đó, loại bỏ các thừa số nguyên tố chung (với số mũ bằng số mũ nhỏ nhất) ở cả tử và mẫu. Phần còn lại sẽ là phân số tối giản. Về cơ bản, đây là cách khác để tìm và chia cả tử và mẫu cho GCD của chúng.

Ví dụ: Rút gọn $\frac{12}{18}$. 12 = $2^2 3^1$ 18 = $2^1 3^2$ Thừa số chung là 2 (với số mũ nhỏ nhất là 1) và 3 (với số mũ nhỏ nhất là 1). GCD(12, 18) = $2^1 3^1 = 6$. Chia cả tử và mẫu cho 6: $\frac{12 \div 6}{18 \div 6} = \frac{2}{3}$. Dùng phân tích: Tử mới = $2^{2-1} 3^{1-1} = 2^1 3^0 = 2$. Mẫu mới = $2^{1-1} 3^{2-1} = 2^0 * 3^1 = 3$. Kết quả là $\frac{2}{3}$.

6. Ứng dụng trong mật mã học

Đây là một lĩnh vực cực kỳ quan trọng mà phân tích thừa số nguyên tố đóng vai trò nền tảng. Các hệ thống mật mã hóa khóa công khai hiện đại như RSA dựa trên sự khó khăn trong việc phân tích các số nguyên rất lớn thành thừa số nguyên tố. Việc nhân hai số nguyên tố lớn để tạo ra một số hợp số là dễ dàng, nhưng quá trình ngược lại (tìm ra hai số nguyên tố ban đầu từ tích của chúng) là cực kỳ khó khăn về mặt tính toán đối với các số đủ lớn. Sự bất đối xứng về độ khó này là cốt lõi của tính bảo mật trong RSA.

Giới hạn của phương pháp chia thử

Thuật toán chia thử mà chúng ta đã triển khai hiệu quả đối với các số có kích thước vừa phải (ví dụ, trong phạm vi long long của C++ đối với hầu hết các bài toán lập trình thi đấu). Tuy nhiên, khi đối mặt với các số cực lớn (ví dụ, hàng trăm chữ số) như trong mật mã học, phương pháp chia thử trở nên quá chậm. Thời gian chạy của nó tăng theo $\sqrt{N}$, và $\sqrt{N}$ vẫn là một số rất lớn khi $N$ có nhiều chữ số.

Đối với việc phân tích các số rất lớn, các thuật toán phức tạp hơn nhiều được sử dụng, chẳng hạn như Pollard's rho algorithm, Quadratic Sieve, và General Number Field Sieve. Đây là những chủ đề nâng cao hơn nằm ngoài phạm vi bài viết này, nhưng điều quan trọng là phải biết rằng phương pháp chia thử có giới hạn của nó.

Ngoài ra, việc kiểm tra một số có phải là nguyên tố hay không (primality testing) cũng là một vấn đề liên quan chặt chẽ. Đối với số lớn, chúng ta không thể dùng chia thử đến $\sqrt{N}$. Các thuật toán kiểm tra nguyên tố xác suất như Miller-Rabin thường được sử dụng để kiểm tra tính nguyên tố của một số lớn một cách nhanh chóng (mặc dù có một xác suất nhỏ trả lời sai).

Bài tập ví dụ:

Phân phối chuối

Trong một buổi thực tập tại vườn trái cây, FullHouse Dev được giao nhiệm vụ phân phối chuối cho nhân viên. Để đảm bảo tính công bằng, họ phải tuân theo một số quy tắc đặc biệt. Với tinh thần nhiệt huyết, FullHouse Dev bắt đầu tìm cách giải quyết bài toán này.

Bài toán

FullHouse Dev cần phân phối $n$ quả chuối theo các điều kiện sau:

Có thể chọn số lượng người nhận chuối
Mỗi người phải nhận nhiều hơn một quả
Không được để một người nhận tất cả số chuối
Tất cả số chuối phải được phân phối
Mỗi người chỉ được nhận số chuối nguyên

Nhiệm vụ là xác định xem liệu có thể phân phối số chuối này theo đúng quy tắc hay không.

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$ - số lượng chuối cần phân phối

OUTPUT FORMAT:

Với mỗi test case, in ra "Yes" nếu có thể phân phối được, ngược lại in ra "No"

Ràng buộc:

$1 \leq T \leq 100$
$1 \leq n \leq 10^9$

Ví dụ

INPUT

2
2
4

OUTPUT

No
Yes

Giải thích

Ở test case đầu tiên: Không thể phân phối $2$ quả chuối. Nếu chọn $1$ người, người đó sẽ nhận tất cả chuối (vi phạm quy tắc). Nếu chọn $2$ người, mỗi người chỉ nhận được $1$ quả (vi phạm quy tắc mỗi người phải nhận nhiều hơn một quả).
Ở test case thứ hai: Có thể phân phối $4$ quả chuối cho $2$ người, mỗi người nhận $2$ quả. Tuyệt vời! Bài toán Phân phối chuối có thể được giải quyết bằng cách phân tích các ràng buộc và tìm ra điều kiện đơn giản nhất. Dưới đây là hướng dẫn giải ngắn gọn bằng C++:

Hiểu rõ các quy tắc:
- Mỗi người > 1 quả chuối.
- Số người nhận > 1 (không ai nhận tất cả).
- Tất cả chuối phải được phân phối.
- Số chuối mỗi người nhận là số nguyên.
Tìm điều kiện tối thiểu:
- Để có thể phân phối cho nhiều hơn 1 người (>1 người) mà mỗi người nhận nhiều hơn 1 quả (>1 quả), số người ít nhất phải là 2.
- Số chuối ít nhất mỗi người nhận là 2 (vì > 1 và là số nguyên).
- Vậy, để thỏa mãn cả hai điều kiện trên (ít nhất 2 người, mỗi người ít nhất 2 quả), tổng số chuối (n) tối thiểu cần phải là 2 người * 2 quả/người = 4 quả.
Kết luận cho các giá trị nhỏ của n:
- Nếu n < 4, ta không thể tìm được ít nhất 2 người mà mỗi người nhận > 1 quả, vì tổng số chuối không đủ 4. Do đó, không thể phân phối được.
Kết luận cho các giá trị lớn của n:
- Nếu n >= 4, ta luôn có thể tìm được một cách phân phối thỏa mãn. Ví dụ đơn giản nhất là chia cho 2 người:
  - Người 1 nhận 2 quả. (Thỏa mãn > 1 quả)
  - Người 2 nhận n - 2 quả. (Vì n >= 4, nên n - 2 >= 2, cũng thỏa mãn > 1 quả)
  - Tổng cộng là 2 + (n - 2) = n quả. (Thỏa mãn phân phối hết)
  - Có 2 người. (Thỏa mãn > 1 người)
  - Không ai nhận tất cả (2 < n và n-2 < n khi n >= 4). (Thỏa mãn không để 1 người nhận tất cả)
- Như vậy, với mọi n >= 4, luôn có cách phân phối hợp lệ.
Điều kiện cuối cùng: Dựa trên phân tích, số chuối n có thể phân phối theo đúng quy tắc khi và chỉ khi n >= 4.
Cách cài đặt trong C++:
- Đọc số lượng test case T.
- Sử dụng vòng lặp while (T--) hoặc for để xử lý từng test case.
- Trong mỗi test case:
  - Đọc số lượng chuối n.
  - Kiểm tra điều kiện: Nếu n >= 4, in ra "Yes".
  - Ngược lại (n < 4), in ra "No".

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

Comments

There are no comments at the moment.