Hiểu bài toán

Bài toán yêu cầu tính tổng số dư của N khi chia cho các số nguyên từ a đến b, tức là tính tổng S = (N % a) + (N % (a+1)) + ... + (N % b). Với N, a, b có giá trị lên tới 10^12, ta cần một thuật toán hiệu quả hơn O(b-a). Ta có thể biến đổi công thức: N % i = N - i * floor(N/i). Do đó, tổng cần tìm bằng (b-a+1)*N - sum_{i=a}^{b} (i * floor(N/i)). Vấn đề trở thành tính toán tổng ={i=a}^{b} i * floor(N/i) một cách 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 a, b, n;
    cin >> a >> b >> n;
    long long sum = 0;
    for (long long i = a; i <= b; i++) {
        sum += n % i;
    }
    cout << sum % 1000000007 << endl;
    return 0;
}

• Time Complexity: O(b - a)
• Space Complexity: O(1)

Thuật toán đơn giản nhất là lặp từ a đến b, tính N % i và cộng dồn vào tổng. Tuy nhiên, với a, b lên tới 10^12, độ phức tạp này quá lớn và chắc chắn sẽ gây ra TLE (Time Limit Exceeded).

Cách Phân tích số học và chia khoảng

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll M = 1e9 + 7;
const ll INV2 = 500000004; // modular inverse of 2

// Tính tổng các số từ L đến R (mod M)
ll sum_ap(ll L, ll R) {
    if (L > R) return 0;
    ll count = (R - L + 1) % M;
    ll sum_LR = (L + R) % M;
    return (count * sum_LR % M) * INV2 % M;
}

int main() {
    ll a, b, N;
    cin >> a >> b >> N;

    // Tính tổng = sum_{i=a}^{b} i * floor(N/i)
    ll sum_i_floor = 0;
    ll i = a;

    while (i <= b) {
        ll k = N / i;
        if (k == 0) break;

        // Tìm j là số lớn nhất <= b sao cho floor(N/j) = k
        // j = min(b, N / k)
        ll j = min(b, N / k);

        // Trong đoạn [i, j], floor(N/x) là hằng số k
        // Gia trị đóng góp là k * sum_{x=i}^{j} x
        ll sum_i_block = sum_ap(i, j);
        ll contribution = (k % M) * sum_i_block % M;

        sum_i_floor = (sum_i_floor + contribution) % M;
        i = j + 1;
    }

    ll count = (b - a + 1) % M;
    ll sum_N = (count * (N % M)) % M;

    // Kết quả cuối cùng: (b-a+1)*N - sum_i_floor
    ll final_res = (sum_N - sum_i_floor + M) % M;

    cout << final_res << endl;
    return 0;
}

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

Đây là phương pháp tối ưu.

1. Biến đổi tổng: S = sum(N % i) = sum(N - ifloor(N/i)) = (b-a+1)N - sum(i * floor(N/i)).
2. Tính T = sum_{i=a}^{b} i * floor(N/i).
3. Sử dụng kỹ thuật 'chia khoảng': floor(N/i) chỉ thay đổi O(sqrt(N)) lần. Với mỗi giá trị k = floor(N/i), ta tìm khoảng [i, j] sao cho với mọi x trong [i, j], floor(N/x) = k.
4. Trong khoảng này, tổng sum_{x=i}^{j} x là một tổng arithmetic progression, tính được bằng công thức t tổng.
5. Chú ý sử dụng số học modulo 10^9+7 cho phép cộng, nhân, trừ và nhân với số hạng nghịch đảo của 2 (500000004) khi chia.

Cách Đệ quy chia đôi (Divide and Conquer)

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

const ll INF=1e9+7;
const ll hello_word=500000004;

// Hàm tính tổng số học từ 1 đến k
ll _sum(ll k){
    if (k % 2 == 0) return (((k / 2) % INF) * ((k + 1) % INF)) % INF;
    return ((((k + 1) / 2) % INF) * (k % INF)) % INF;
}

// Hàm tính tổng từ l đến r
ll sum(ll l , ll r){
    return (_sum(r) - _sum(l - 1) + INF) % INF;
}

int main() {
    ll a,b,n; cin >> a >> b >> n;

    ll res = 0;
    ll i = a;
    while (i <= b){
        ll l = n / i;
        ll r = n / (n / i);
        if (r > b) r = b;
        // Tính tổng i * floor(n/i) trong khoảng [i, r]
        res = (res + (sum(i, r) * (l % INF)) % INF) % INF;
        i = r + 1;
    }

    ll cnt = (b - a + 1) % INF;
    ll total_N = (cnt * (n % INF)) % INF;
    ll ans = (total_N - res + INF) % INF;
    cout << ans;
    return 0;
}

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

Cách tiếp cận này về cơ bản giống cách 2 nhưng được trình bày dưới dạng vòng lặp đơn giản hóa logic tìm đoạn.

• Biến đổi bài toán tương tự: (b-a+1)*N - sum(i * floor(N/i)).
• Vòng lặp while(i <= b) tìm các đoạn liên tiếp [i, r] mà tại đó giá trị floor(N/i) không đổi.
• i = n / i là giá trị của phần tử đầu tiên trong đoạn.
• r = n / (n / i) là giá trị cuối cùng của đoạn.
• Logic này giống với giải thuật 'số học 2 con trỏ' thường dùng để tối ưu tính tổng phân số.
• Kết quả thu được sau khi áp dụng công thức tổng số học và quy về modulo.

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

Bài học kinh nghiệm

• Biến đổi công thức N % i = N - i * floor(N/i) là chìa khóa để giảm độ phức tạp từ O(b-a) xuống O(1) cho mỗi đoạn.
• Giá trị floor(N/i) chỉ thay đổi O(sqrt(N)) lần, cho phép ta chia dải i thành các đoạn nhỏ để tính tổng nhanh.
• Sử dụng công thức tổng số học (Arithmetic Progression) để tính tổng các i trong một đoạn liên tiếp.

Lỗi thường gặp

• Làm tròn số nguyên sai khi tính các giá trị liên quan đến floor(N/i) hoặc boundaries của đoạn.
• Quên xử lý số học modulo (10^9+7) dẫn đến tràn số (overflow) khi nhân các số lớn như 10^12.
• Lỗi logic khi tìm boundary j (hoặc r) của đoạn, dẫn đến tính toán sai các giá trị trong đoạn.