Editorial for ptit063: Số vui vẻ

Hiểu bài toán

Một số nguyên dương được gọi là 'số vui vẻ' nếu nó có số lượng ước số (divisors) là một số lẻ. Nhiệm vụ là đếm số lượng các số vui vẻ trong khoảng từ l đến r (bao gồm l và r). Dựa vào định lý về số lượng ước số, ta biết rằng số lượng ước số của một số là lẻ khi và chỉ khi số đó là một số chính phương (perfect square). Do đó, bài toán quy về việc đếm số lượng số chính phương trong đoạn [l, r].

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

Cách Brute Force (Đếm trực tiếp)

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

int cp(int n) {
    int p = sqrt(n);
    return (p * p == n);
}

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    int sum = 0;
    for (int i = a; i <= b; i++) {
        if (cp(i)) sum++;
    }
    printf("%d", sum);
    return 0;
}

• Time Complexity: O((r - l) * sqrt(r))
• Space Complexity: O(1)

Phương pháp này duyệt qua từng số i từ l đến r. Với mỗi số i, nó kiểm tra xem i có phải là số chính phương hay không bằng cách tính căn bậc hai của nó, làm tròn xuống, rồi bình phương lại và so sánh với số ban đầu. Nếu khớp, ta tăng biến đếm. Cách này đơn giản để hiểu nhưng chậm do phải duyệt qua toàn bộ khoảng giá trị và thực hiện phép chia cho mỗi số.

Cách Quy hoạch động / Bảng kê (Prefix Sum)

#include <stdio.h>
#include <stdbool.h>

#define MAX 100005

int dp[MAX];

void precompute() {
    // dp[i] sẽ lưu số lượng số vui vẻ từ 1 đến i
    for (int i = 1; i < MAX; i++) {
        dp[i] = dp[i-1];
        // Kiểm tra xem i có phải là số chính phương không
        // Số chính phương có số lượng ước là số lẻ
        int s = 1;
        for (int j = 1; j * j <= i; j++) {
            if (j * j == i) {
                s = 0;
                break;
            }
        }
        if (s == 0) dp[i]++; // i là số chính phương
    }
}

int main() {
    precompute();
    int l, r;
    scanf("%d%d", &l, &r);
    // Số lượng số vui vẻ trong [l, r] là dp[r] - dp[l-1]
    printf("%d", dp[r] - dp[l-1]);
    return 0;
}

• Time Complexity: O(N * sqrt(N)) (với N=10^5)
• Space Complexity: O(N)

Phương pháp này xây dựng một mảng dp trước khi xử lý truy vấn. dp[i] lưu số lượng số vui vẻ từ 1 đến i. Sau đó, kết quả cho khoảng [l, r] được tính bằng dp[r] - dp[l-1]. Tuy nhiên, code mẫu vẫn sử dụng vòng lặp kiểm tra căn bậc hai bên trong vòng lặp chính, dẫn đến độ phức tạp cao. Đây là bước tiền xử lý để chuyển đổi truy vấn thành O(1) nhưng cách kiểm tra số chính phương chưa tối ưu.

Cách Tối ưu Toán học (Math)

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

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

    // Đếm số lượng số chính phương trong [l, r]
    // Số chính phương từ 1 đến r là floor(sqrt(r))
    // Số chính phương từ 1 đến l-1 là floor(sqrt(l-1))

    int count = (int)sqrt(r) - (int)sqrt(l - 1);

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

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

Đây là phương pháp tối ưu nhất. Một số có số lượng ước là số lẻ nếu và chỉ khi nó là số chính phương. Số lượng số chính phương trong đoạn [1, n] là floor(sqrt(n)). Do đó, số lượng số chính phương trong đoạn [l, r] bằng số lượng số chính phương <= r trừ đi số lượng số chính phương <= l-1. Công thức là floor(sqrt(r)) - floor(sqrt(l-1)). Phương pháp này bỏ qua vòng lặp và chỉ thực hiện vài phép toán số học, chạy ngay lập tức ngay cả với giới hạn lớn.

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

Bài học kinh nghiệm

• Một số có số lượng ước số lẻ khi và chỉ khi nó là số chính phương.
• Đếm số lượng số vui vẻ trong khoảng [l, r] tương đương với đếm số lượng số chính phương trong khoảng đó.
• Số lượng số chính phương từ 1 đến N là floor(sqrt(N)).

Lỗi thường gặp

• Việc kiểm tra một số có phải là số chính phương bằng cách lặp từ 1 đến n là quá chậm, nên dùng hàm sqrt hoặc kiểm tra trong khoảng căn bậc hai.
• Đoạn code tham khảo số 1 và 2 thực hiện vòng lặp từ a+1 đến b-1 (nghĩa là loại trừ a và b). Nếu làm theo yêu cầu bài toán 'trong khoảng [l, r]', cần duyệt từ l đến r (bao gồm cả hai đầu mút). Tuy nhiên, logic toán học (công thức sqrt) đã xử lý chính xác việc bao gồm đầu mút.
• Cần chú ý số 0: sqrt(0) bằng 0, nhưng bài toán giới hạn số nguyên dương từ 1. Công thức sqrt(l-1) sẽ an toàn nếu l >= 1.