Hiểu bài toán

Viết chương trình đọc vào một số nguyên n (với |n| <= 10^4) và in ra tất cả các ước số nguyên dương của |n| (tức là giá trị tuyệt đối của n) theo thứ tự giảm dần. Nếu n = 0, do 0 chia hết cho mọi số khác 0 nên có vô số ước, in ra 'INF'. Ví dụ với n = 8, các ước là 1, 2, 4, 8, in ra '8 4 2 1'.

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

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

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

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

    if (n == 0) {
        printf("INF");
        return 0;
    }

    // Chuyển về số dương để xử lý ước
    n = abs(n);

    // Duyệt từ n về 1, in ra nếu là ước
    for (int i = n; i >= 1; i--) {
        if (n % i == 0) {
            printf("%d ", i);
        }
    }

    return 0;
}

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

Phương pháp này đơn giản nhất là duyệt từ n xuống 1. Với mỗi số i, ta kiểm tra xem nó có phải là ước của n không (n % i == 0). Nếu có thì in ra. Vì ta duyệt giảm dần, thứ tự in ra sẽ giảm dần đúng theo yêu cầu. Với n tối đa 10^4, số lần lặp tối đa là 10^4, hoàn toàn chấp nhận được.

Cách Tối ưu bằng cách chỉ duyệt đến căn bậc hai

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

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

    if (n == 0) {
        printf("INF");
        return 0;
    }

    n = abs(n);
    int sqrt_n = (int)sqrt(n);

    // In các ước từ n về căn bậc hai (bao gồm cả căn bậc hai nếu có)
    for (int i = n; i > sqrt_n; i--) {
        if (n % i == 0) {
            printf("%d ", i);
        }
    }

    // In căn bậc hai nếu nó là ước
    if (n == sqrt_n * sqrt_n) {
        printf("%d ", sqrt_n);
    }

    // In các ước còn lại (từ căn bậc hai về 1)
    for (int i = sqrt_n - 1; i >= 1; i--) {
        if (n % i == 0) {
            printf("%d ", i);
        }
    }

    return 0;
}

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

Phương pháp này tối ưu hơn. Thay vì duyệt toàn bộ từ n về 1, ta chỉ cần duyệt đến căn bậc hai của n (sqrt(n)). Nếu i là ước của n thì n/i cũng là ước. Khi duyệt từ n xuống sqrt(n), ta in ra các ước lớn. Sau đó ta in ra sqrt(n) nếu nó là ước, cuối cùng duyệt từ sqrt(n)-1 xuống 1 để in các ước nhỏ. Độ phức tạp giảm từ O(n) xuống O(sqrt(n)).

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

Bài học kinh nghiệm

• Nếu i là ước của n thì n/i cũng là ước. Điều này cho phép ta chỉ cần kiểm tra các số từ 1 đến sqrt(n) để tìm tất cả các ước.
• Với giá trị |n| <= 10^4, độ phức tạp O(n) của Brute Force là hoàn toàn chấp nhận được, nhưng O(sqrt(n)) là tốt hơn.
• Cần xử lý trường hợp n = 0 đặc biệt (in 'INF') và n âm (dùng abs(n)).

Lỗi thường gặp

• Quên xử lý trường hợp n = 0, dẫn đến vòng lặp vô hạn hoặc lỗi logic.
• Xử lý sai số âm: cần lấy giá trị tuyệt đối của n để tìm ước số nguyên dương.
• In thừa dấu cách ở cuối dòng: một số implementation in ra dấu cách sau số cuối cùng, tuy nhiên trong bài này thường được chấp nhận, nhưng tốt nhất nên kiểm soát.