Editorial for lamp: Thắp sáng bóng đèn

Hiểu bài toán

Bài toán yêu cầu tìm số bóng đèn còn bật sau N thao tác. Ban đầu tất cả đều tắt. Thao tác i sẽ đảo trạng thái của các bóng đèn ở vị trí chia hết cho i. Ta cần đếm số bóng đèn bật (trạng thái 1) sau khi hoàn thành N thao tác.

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

Cách Mô phỏng

#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long n;
    cin >> n;
    vector<bool> lights(n + 1, false);
    for (long long i = 1; i <= n; i++) {
        for (long long j = i; j <= n; j += i) {
            lights[j] = !lights[j];
        }
    }
    int count = 0;
    for (long long i = 1; i <= n; i++) {
        if (lights[i]) count++;
    }
    cout << count << endl;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Mô phỏng trực tiếp quá trình: tạo mảng trạng thái, lặp i từ 1 đến N, với mỗi i, lặp qua các bội số của i và đảo trạng thái. Đếm số lượng true sau cùng. Với N lớn (10^18) thì không khả thi về thời gian và bộ nhớ.

Cách Tối ưu hóa

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    for (long long i = 1; i * i <= n; i++) {
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

Một bóng đèn tại vị trí k được thao tác đúng số lần bằng số ước của k. Để đèn bật, số ước phải là số lẻ. Các số có số ước lẻ chính là các số chính phương (ví dụ: 1, 4, 9, 16...). Do đó, số lượng bóng đèn bật sau cùng bằng số lượng số chính phương nhỏ hơn hoặc bằng N,也就是 floor(sqrt(N)).

Cách Phương pháp tối ưu

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long ans = sqrtl(n);
    while ((ans + 1) * (ans + 1) <= n) ans++;
    while (ans * ans > n) ans--;
    cout << ans << endl;
    return 0;
}

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

Sử dụng hàm sqrtl(n) để tính căn bậc hai của n một cách chính xác. Sau đó điều chỉnh kết quả để đảm bảo ans^2 <= n < (ans+1)^2. Đây là cách hiệu quả nhất để đếm số lượng số chính phương <= n với N lên tới 10^18.

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

Bài học kinh nghiệm

• Số lần một bóng đèn tại vị trí k được thao tác bằng số lượng ước của k
• Bóng đèn bật sau cùng nếu và chỉ nếu số ước của vị trí đó là số lẻ
• Chỉ có các số chính phương mới có số ước lẻ
• Số lượng số chính phương <= N bằng floor(sqrt(N))

Lỗi thường gặp

• Sử dụng kiểu int thay vì long long cho N <= 10^18
• Tính sqrt(N) không chính xác do làm tròn số thực
• Quên kiểm tra biên khi điều chỉnh kết quả