Editorial for sumodd: Tính tổng các số lẻ

Hiểu bài toán

Bài toán yêu cầu tính tổng tất cả các số lẻ nằm trong khoảng từ ~l~ đến ~r~ (bao gồm ~l~ và ~r~). Dải giá trị ~l, r~ có thể lên tới ~10^9~, nghĩa là khoảng cách (số lượng phần tử) có thể rất lớn.

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

Cách Brute Force (Lặp qua tất cả)

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

int main() {
    long long l, r;
    cin >> l >> r;
    long long sum = 0;
    for (long long i = l; i <= r; i++) {
        if (i % 2 != 0) sum += i;
    }
    cout << sum;
    return 0;
}

• Time Complexity: O(r - l) ~ O(10^9)
• Space Complexity: O(1)

Phương pháp này sử dụng vòng lặp để duyệt qua từng số trong đoạn từ ~l~ đến ~r~. Nếu số đó là số lẻ (dư 2 khác 0), ta cộng vào biến tổng. Tuy nhiên, với ~r - l~ lên tới 10^9, vòng lặp này sẽ thực hiện khoảng 1 tỷ lần lặp, dẫn đến lỗi 'Time Limit Exceeded' (Quá giới hạn thời gian).

Cách Công thức toán học (Math Formula)

#include <iostream>
using namespace std;

long long sum_odd(long long n) {
    if (n < 1) return 0;
    long long cnt = (n + 1) / 2;
    return cnt * cnt;
}

int main() {
    long long l, r;
    cin >> l >> r;
    long long ans = sum_odd(r) - sum_odd(l - 1);
    cout << ans;
    return 0;
}

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

Đây là phương pháp tối ưu. Ta nhận thấy dãy số lẻ từ 1 đến ~n~ là một cấp số cộng: 1, 3, 5, ..., (2k-1) với ~k~ là số lượng số lẻ. Tổng của một cấp số cộng là (Đầu + Cuối) * Số phần tử / 2 = (1 + (2k-1)) * k / 2 = 2k * k / 2 = k^2. Với ~n~, số lượng số lẻ là k = (n + 1) / 2. Do đó, tổng các số lẻ từ 1 đến ~n~ là k^2. Tổng các số lẻ từ ~l~ đến ~r~ sẽ bằng Tổng(1->r) - Tổng(1->(l-1)). Phương pháp này chạy ngay lập tức với mọi giá trị đầu vào.

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

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán tính tổng dãy số lẻ từ 1 đến n bằng công thức lũy thừa.
• Tổng các số lẻ từ 1 đến n là một số chính phương (perfect square).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int hoặc long thay vì long long会导致 overflow vì tổng các số lẻ có thể lên tới ~10^18.
• Việc lặp trực tiếp (brute force) chắc chắn bị TLE với giới hạn ~10^9.