Hiểu bài toán

Cho một số nguyên dương N. Yêu cầu tính tổng S = Σ_{i=1}^{N} floor(N/i). Ví dụ, với N=5, ta có: floor(5/1)=5, floor(5/2)=2, floor(5/3)=1, floor(5/4)=1, floor(5/5)=1. Tổng S = 5+2+1+1+1 = 10. N là số lớn (có thể lên tới 10^12), do đó cần thuật toán hiệu quả.

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

Cách Brute Force (Vét cạn)

#include <iostream>
using namespace std;

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

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

Thuật toán đơn giản nhất là lặp từ i = 1 đến N, cộng dồn kết quả của phép chia nguyên N/i vào biến tổng. Với N nhỏ, đây là cách làm trực quan và dễ hiểu nhất.

Cách Phép biến đổi số học (Math Trick)

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

int main() {
    long long n;
    cin >> n;
    long long ans = 0;
    long long i = 1;
    while (i <= n) {
        long long q = n / i;
        long long last = n / q;
        ans += q * (last - i + 1);
        i = last + 1;
    }
    cout << ans;
    return 0;
}

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

Giá trị của floor(N/i) chỉ thay đổi khi i vượt quá một ngưỡng nhất định. Cụ thể, nếu q = floor(N/i), thì giá trị q này sẽ giữ nguyên cho tất cả các i trong khoảng [i, floor(N/q)]. Ta có thể nhảy trực tiếp từ i đến floor(N/q) + 1 để bỏ qua các số có cùng kết quả chia. Số lượng các giá trị phân biệt của floor(N/i) là khoảng 2*sqrt(N), nên độ phức tạp là O(sqrt(N)).

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

Bài học kinh nghiệm

• floor(N/i) chỉ có O(√N) giá trị phân biệt.
• Sử dụng kỹ thuật 'nhảy số' (block method) để xử lý hàng loạt số cùng giá trị floor(N/i) một lúc.

Lỗi thường gặp

• Sử dụng biến kiểu int導致 overflow khi N lớn (ví dụ N=10^12). Cần dùng long long.
• Lặp sai điều kiện dừng (ví dụ dùng i < n thay vì i <= n).