Hiểu bài toán

Số hoàn hảo là một số nguyên dương n mà tổng всех các ước số nguyên dương của nó (không tính chính nó) bằng chính nó. Nhiệm vụ là kiểm tra xem một số nguyên n được nhập từ bàn phím có phải là số hoàn hảo hay không. Với giới hạn |n| ≤ 10^9, chúng ta cần một giải pháp hiệu quả.

Các cách tiếp cận

Cách Brute Force (Duyệt toàn bộ)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n; 
    scanf("%d", &n);

    if (n <= 0) {
        printf("NO\n"); 
        return 0; 
    } 

    int sum = 0;  
    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            sum += i;  
        }
    }

    if (n == sum) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }

    return 0; 
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Phương pháp này duyệt qua tất cả các số từ 1 đến n-1. Với mỗi số i, nó kiểm tra xem i có phải là ước của n không (n % i == 0). Nếu là ước thì cộng dồn vào biến tổng. Cuối cùng so sánh tổng với n.

Vì n có thể lên tới 10^9, độ phức tạp O(n) là quá chậm và chắc chắn sẽ gây ra lỗi quá thời gian (Time Limit Exceeded). Ví dụ, với n = 10^9, máy tính không thể nào chạy hết 10^9 vòng lặp trong thời gian cho phép (thường là 1-2 giây).

Cách Optimized Brute Force (Tối ưu hóa vòng lặp)

#include <stdio.h>

int main(){
    long long n;

    scanf("%lld", &n);
    if (n <= 0){
        printf("NO");
        return 0;
    }
    long long sum = 0;
    for (int i = 1; i <= n/2; ++i) 
        if (n % i == 0) sum += i;
    if (sum == n) printf("YES");
    else printf("NO");

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cải tiến nhỏ từ phương pháp Brute Force. Thay vì duyệt đến n, ta chỉ cần duyệt đến n/2. Lý do là không thể t tồn tại ước thực sự nào của n lớn hơn n/2 (trừ chính n).

Ví dụ: Với n = 1000, vòng lặp chạy từ 1 đến 500. Vẫn chưa đủ nhanh cho n = 10^9 (vì 5 * 10^8 vẫn là một số lượng vòng lặp rất lớn). Tuy nhiên, đây là cách tiếp cận đúng hướng.

Cách Square Root Optimization (Tối ưu hóa căn bậc hai)

#include <stdio.h>
#include <math.h>

int main() {
    long long n;
    scanf("%lld", &n);

    if (n <= 0) {
        printf("NO");
        return 0;
    }
    if (n == 1) {
        printf("NO");
        return 0;
    }

    long long sum = 1; // 1 luôn là ước của mọi số > 1
    long long limit = (long long)sqrt(n);

    for (long long i = 2; i <= limit; ++i) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) { // Tránh cộng 2 lần nếu i là căn bậc hai của n
                sum += n / i;
            }
        }
    }

    if (sum == n) printf("YES");
    else printf("NO");

    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất. Nếu ab là ước của n thì a và b là một cặp ước. Ví dụ với n = 100, ước là 1-100, 2-50, 4-25, 5-20, 10-10.

Ta chỉ cần duyệt i từ 2 đến căn bậc hai của n (sqrt(n)).

• Nếu i là ước của n (n % i == 0), ta cộng i vào tổng.
• Đồng thời, n/i cũng là ước, ta cộng n/i vào tổng.
• Trường hợp đặc biệt nếu n là số chính phương (ví dụ 100 = 10 * 10), ta chỉ cộng 10 một lần.

Với n = 10^9, sqrt(n) ≈ 31622, vòng lặp chỉ chạy khoảng 3 vạn lần, chạy rất nhanh.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Chỉ cần duyệt đến căn bậc hai của n (sqrt(n)) thay vì toàn bộ n. Nếu i là ước thì n/i cũng là ước.
• Phải kiểm tra trường hợp n là số chính phương để không cộng trùng ước.
• Biến tổng (sum) và n có thể vượt quá giới hạn của kiểu int (2 * 10^9) nếu n lớn, nên dùng kiểu dữ liệu lớn hơn (long long).

Lỗi thường gặp

• Quên kiểm tra n <= 0 (vì định nghĩa số hoàn hảo chỉ dành cho số nguyên dương).
• Quên kiểm tra n = 1 (1 không phải số hoàn hảo vì tổng ước không bao gồm chính nó là 0).
• Sử dụng biến int cho n hoặc sum khi n lên tới 10^9, dẫn đến tràn số (overflow).