Hiểu bài toán

Bài toán yêu cầu tính tổng giá trị: $$\sum_{i=a}^{b} \left\lfloor \frac{n}{i} \right\rfloor$$ Trong đó $a, b, n$ là các số nguyên dương, với $1 \le a \le b \le n \le 10^{12}$. Hàm $\lfloor x \rfloor$ (trong đề bài là $[x]$) là hàm lấy phần nguyên của $x$. Với $n$ lớn lên tới $10^{12}$, không thể lặp qua từng số $i$ từ $a$ đến $b$ để tính trực tiếp. Cần một phương pháp tối ưu hơn.

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

Cách Tối ưu hóa vòng lặp (Math)

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, n;
    cin >> a >> b >> n;
    int l = a;
    int ans = 0;
    while(l <= b){
        if(l > n){
            break;
        }
        int q = n / l;
        int r = n / q;
        r = min(r, b);
        ans += q * (r - l + 1);
        l = r + 1;
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(\sqrt{n})
• Space Complexity: O(1)

Phương pháp này dựa trên nhận xét rằng với $i$ trong một khoảng liên tiếp, giá trị của $\lfloor \frac{n}{i} \rfloor$ là không đổi. Cụ thể, nếu ta biết giá trị $q = \lfloor \frac{n}{i} \rfloor$, thì $i$ có thể nằm trong khoảng từ $i$ đến $\lfloor \frac{n}{q} \rfloor$.

Cách làm:

1. Bắt đầu từ $l = a$.
2. Tính $q = \lfloor \frac{n}{l} \rfloor$. Nếu $q = 0$ (tức $l > n$), ta có thể dừng lại vì các số tiếp theo cũng sẽ cho giá trị 0.
3. Xác định giới hạn trên $r$ của đoạn số mà ở đó giá trị $q$ không đổi: $r = \lfloor \frac{n}{q} \rfloor$.
4. Giới hạn $r$ lại để không vượt quá $b$ (vì chỉ cần tính tổng đến $b$).
5. Giá trị $q$ được cộng vào tổng với số lần xuất hiện là $(r - l + 1)$.
6. Cập nhật $l = r + 1$ để sang đoạn tiếp theo.
7. Lặp lại cho đến khi $l > b$.

Vì giá trị $q$ giảm dần và số lượng các đoạn cần xét là $O(\sqrt{n})$, độ phức tạp là $O(\sqrt{n})$.

Cách Hàm số học (Divide and Conquer / Math)

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

long long a, b, n;

// Tính tổng floor(n/i) cho i tu 1 den m
long long sum_n_div_i(long long m) {
    if (m <= 0) return 0;
    long long ans = 0;
    long long i;
    // Vong lap cho i <= sqrt(n)
    for (i = 1; i * i <= n && i <= m; ++i) {
        ans += n / i;
    }
    // Vong lap cho i > sqrt(n)
    // luc nay n/i < sqrt(n)
    // ta chay tu k = 1 den ...
    // i tuong ung la n/k
    for (long long k = 1; k * k <= n; ++k) {
        long long x = n / k;
        if (x < i) { // Chi tinh nhung phan tu ma vong lap truoc chua tinh
            long long upper = min((long long)n / (k + 1) + 1, m + 1);
            long long lower = i;
            if (upper > lower) {
                ans += k * (upper - lower);
            }
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b >> n;
    long long ans = sum_n_div_i(b) - sum_n_div_i(a - 1);
    cout << ans;
    return 0;
}

• Time Complexity: O(\sqrt{n})
• Space Complexity: O(1)

Phương pháp này chia bài toán thành 2 phần dựa trên giá trị của $i$:

1. Khi $i \le \sqrt{n}$: Lặp trực tiếp từ $1$ đến $\sqrt{n}$ để cộng dồn.
2. Khi $i > \sqrt{n}$: Khi đó $q = \lfloor \frac{n}{i} \rfloor < \sqrt{n}$. Ta có thể lặp theo $q$ (từ $1$ đến $\sqrt{n}$). Với mỗi $q$, ta tìm khoảng giá trị $i$ tương ứng: $\frac{n}{q+1} < i \le \frac{n}{q}$.

Cách tiếp cận này chia dải $[1, m]$ thành 2 phần và xử lý riêng. Để tính tổng từ $a$ đến $b$, ta tính tổng từ $1$ đến $b$ và trừ đi tổng từ $1$ đến $a-1$ (tính hàm số học).

Độ phức tạp: $O(\sqrt{n})$ do có 2 vòng lặp chạy đến $\sqrt{n}$.

Cách Brute Force (Không khả thi)

long long ans = 0;
for (long long i = a; i <= b; i++) {
    ans += n / i;
}

• Time Complexity: O(b - a) ~ O(10^12)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất: lặp qua từng số $i$ trong khoảng từ $a$ đến $b$, tính $\lfloor \frac{n}{i} \rfloor$ và cộng vào tổng.

Tuy nhiên, với ràng buộc $n \le 10^{12}$ và $a, b$ có thể bằng $1, 10^{12}$, số lượng iterations có thể lên tới $10^{12}$, vượt quá giới hạn thời gian cho phép (thường là 1-2 giây) của hầu hết các kỳ thi lập trình.

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

Bài học kinh nghiệm

• Giá trị của $\lfloor \frac{n}{i} \rfloor$ chỉ thay đổi $O(\sqrt{n})$ lần khi $i$ chạy từ $1$ đến $n$. Đây là chìa khóa để giảm độ phức tạp.
• Bài toán có thể biến đổi thành tổng tiền tố (prefix sum): $S(b) - S(a-1)$, giúp tái sử dụng code cho các đoạn khác nhau.

Lỗi thường gặp

• Sử dụng biến kiểu int (32-bit) sẽ gây tràn số khi $n = 10^{12}$. Phải dùng long long (64-bit).
• Sai lệch khi tính toán các chỉ số mảng hoặc điều kiện vòng lặp do chế độ số nguyên chia lấy phần tử.
• Quên kiểm tra trường hợp $a > n$ hoặc $b > n$. Nếu $l > n$, giá trị $\lfloor \frac{n}{l} \rfloor$ là 0 và không cần tính thêm.