Hiểu bài toán

Cho một số nguyên dương n. nhiệm vụ là tính tổng S = [n/1] + [n/2] + ... + [n/n], trong đó [x] là phần nguyên của x (tức là floor(x)). Với n lên tới 10^9, cách tiếp cận trực tiếp tính từng số hạng sẽ quá chậm.

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

Cách Brute Force (Lặp thông thường)

long long s = 0;
for (long long i = 1; i <= n; i++) {
    s += n / i;
}

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

Duyệt tuần tự từ i = 1 đến n, tính giá trị n / i và cộng vào tổng. Vì n có thể lên tới 10^9, độ phức tạp O(n) sẽ dẫn đến TLE (Time Limit Exceeded).

Cách Phân loại giá trị (Math)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, s = 0;
    cin >> n;
    for (long long i = 1, j; i <= n; i = j + 1) {
        long long q = n / i;
        j = n / q;
        s += (j - i + 1) * q;
    }
    cout << s;
}

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

Tính chất: Với n cố định, giá trị của n / i chỉ thay đổi O(sqrt(n)) lần. Cụ thể, nếu k = n / i thì i nằm trong khoảng [n/(k+1)+1, n/k]. Ta có thể nhóm các i lại thành các đoạn liên tục mà giá trị n/i không đổi. Vòng lặp chạy từ i=1, tính q = n/i, tìm j = n/q là chỉ số cuối cùng của đoạn. Sau đó cộng dồn q(j-i+1) và nhảy i về j+1. Số lần lặp chỉ khoảng 2sqrt(n).

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

Bài học kinh nghiệm

• Giá trị của n/i chỉ thay đổi O(sqrt(n)) lần khi i chạy từ 1 đến n.
• Đoạn [i, j] mà n/k không đổi có thể xác định nhanh chóng bằng j = n / (n/i).

Lỗi thường gặp

• Sử dụng biến kiểu int导致 overflow khi n = 10^9 (n*n có thể xảy ra ở cách khác, nhưng ở đây cần long long cho biến tích累)
• Quên cập nhật đúng bước nhảy i = j + 1 có thể gây ra vòng lặp vô hạn hoặc sai kết quả.