Hiểu bài toán

Bài toán yêu cầu đếm số lượng ước số dương của một số nguyên a (khác 0). Dù a có thể là số âm, số ước của một số nguyên âm giống hệt số ước của số dương tương ứng (ví dụ: -4 có các ước dương là 1, 2, 4). Do đó, bước đầu tiên luôn là lấy giá trị tuyệt đối của a. Với giới hạn |a| <= 1000, ta có thể kiểm tra tất cả các số từ 1 đến |a| để xem số nào chia hết cho |a|.

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

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

#include <stdio.h>

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

    // Xử lý số âm bằng cách lấy giá trị tuyệt đối
    if (a < 0) a = -a;

    int count = 0;
    // Duyệt từ 1 đến a để tìm ước
    for (int i = 1; i <= a; i++) {
        if (a % i == 0) {
            count++;
        }
    }

    printf("%d", count);
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Sau khi chuẩn hóa a thành số dương, ta sử dụng một vòng lặp từ 1 đến a. Trong mỗi bước lặp, ta kiểm tra xem i có phải là ước của a không (dùng phép chia lấy dư a % i == 0). Nếu có, ta tăng biến đếm lên 1. Phương pháp này đảm bảo tìm được tất cả các ước.

Cách Tối ưu Brute Force (Duyệt đến căn bậc hai)

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

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

    // Xử lý số âm
    if (a < 0) a = -a;

    int count = 0;
    int root = (int)sqrt(a);

    // Duyệt từ 1 đến căn bậc hai của a
    for (int i = 1; i <= root; i++) {
        if (a % i == 0) {
            // Nếu a chia hết cho i, ta có 2 ước: i và a/i
            // Nếu i * i == a, thì i và a/i là một số, chỉ đếm 1 lần
            if (i * i == a) {
                count += 1;
            } else {
                count += 2;
            }
        }
    }

    printf("%d", count);
    return 0;
}

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

Với mỗi ước i của a nhỏ hơn hoặc bằng căn bậc hai của a, luôn t tồn tại một ước k khác (k = a/i) lớn hơn hoặc bằng căn bậc hai của a. Do đó, ta chỉ cần duyệt từ 1 đến sqrt(a). Nếu a % i == 0, ta tăng biến đếm lên 2 (tương ứng với i và a/i). Trường hợp đặc biệt là khi i*i == a (a là số chính phương), ta chỉ tăng 1. Cách này giảm đáng kể thời gian chạy.

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

Bài học kinh nghiệm

• Số lượng ước của một số nguyên âm giống hệt số lượng ước của số dương tương ứng. Do đó, cần chuẩn hóa input về số dương ngay từ đầu.
• Với số n, các ước luôn đến theo cặp (i, n/i). Điều này cho phép ta chỉ cần duyệt đến sqrt(n) thay vì n để tối ưu hóa thời gian.

Lỗi thường gặp

• Quên xử lý số âm (ví dụ: input -4 nếu không chuẩn hóa có thể gây lỗi hoặc sai kết quả nếu chỉ dùng phép chia % trực tiếp trong một số trường hợp lặp đặc biệt).
• Sử dụng biến kiểu int cho vòng lặp khi n lớn (dù bài này n nhỏ, nhưng logic thường gặp là for (int i = 1; i <= n; i++) sẽ rất chậm với n lớn).