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ừ số nguyên l đến r (bao gồm cả l và r). Dữ liệu đầu vào có thể rất lớn (lên đến ~10^9), do đó cần một giải pháp hiệu quả về thời gian thực thi và bộ nhớ.

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

Cách Vòng lặp (Brute Force)

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

int main() {
    long long l, r;
    cin >> l >> r;

    // Tìm số lẻ đầu tiên >= l
    if (l % 2 == 0) l++;

    long long sum = 0;
    for (long long x = l; x <= r; x += 2) {
        sum += x;
    }

    cout << sum;
    return 0;
}

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

Phương pháp này sử dụng một vòng lặp để duyệt qua các số lẻ từ số lẻ đầu tiên >= l đến r, mỗi bước nhảy 2 đơn vị.

1. Kiểm tra nếu l là số chẵn, tăng l lên 1 để biến thành số lẻ.
2. Khởi tạo biến sum = 0.
3. Lặp từ l đến r với bước nhảy 2 (x += 2), cộng dồn vào sum.
4. In ra kết quả.

Cách này rất trực quan và dễ hiểu. Tuy nhiên, với r lên tới 10^9, số lượng số lẻ trong đoạn có thể lên tới 5*10^8, vòng lặp sẽ chạy quá lâu và gây ra lỗi 'Time Limit Exceeded'. Do đó, giải pháp này chỉ khả thi với dữ liệu nhỏ.

Cách Công thức tổng quát (Optimal)

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

int main() {
    long long l, r;
    cin >> l >> r;

    long long first = (l % 2 == 1) ? l : l + 1;
    long long last  = (r % 2 == 1) ? r : r - 1;

    if (first > last) {
        cout << 0;
        return 0;
    }

    long long n = (last - first) / 2 + 1;
    long long sum = n * (first + last) / 2;

    cout << sum;
    return 0;
}

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

Phương pháp này sử dụng công thức toán học để tính tổng không cần vòng lặp, do đó có độ phức tạp hằng số thời gian O(1).

1. Tìm số lẻ đầu tiên (first) trong đoạn: Nếu l là số lẻ thì first = l, ngược lại first = l + 1.
2. Tìm số lẻ cuối cùng (last) trong đoạn: Nếu r là số lẻ thì last = r, ngược lại last = r - 1.
3. Kiểm tra điều kiện: Nếu first > last (ví dụ đoạn [2, 3] nhưng 2 là chẵn -> first=3, last=2 -> không có số lẻ), in ra 0.
4. Nếu có số lẻ, tính số lượng các số lẻ: n = (last - first) / 2 + 1.
5. Tính tổng các số lẻ bằng công thức tổng của cấp số cộng: sum = n * (first + last) / 2.

Đây là giải pháp tối ưu nhất.

Cách Tối ưu vòng lặp (Cải tiến)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long l,r,ssh;
    cin>>l>>r;
    if(l%2==0)
    {
        l++;
    }
    if(r%2==0)
    {
        r--;
    }
    ssh=(r-l)/2+1;
    cout<<(l+r)*ssh/2;
}

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

Đây là biến thể của phương pháp công thức tổng quát, có cấu trúc mã nguồn gọn hơn.

1. Chuẩn hóa l: Nếu l là chẵn, l++ để lấy số lẻ đầu tiên.
2. Chuẩn hóa r: Nếu r là chẵn, r-- để lấy số lẻ cuối cùng.
3. Tính ssh (số lượng số lẻ): (r - l) / 2 + 1. Lưu ý ở đây biến ssh chính là n trong phương pháp trước.
4. Tính tổng: (l + r) * ssh / 2.

Giải pháp này cũng mang lại hiệu quả O(1) và là cách tiếp cận thường thấy trong các bài toán tính tổng theo quy luật.

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

Bài học kinh nghiệm

• Bài toán có thể biến về bài toán tính tổng của một cấp số cộng (arithmetic progression) với公差 (common difference) là 2.
• Vì r có thể lên tới 10^9, tuyệt đối không được sử dụng vòng lặp duyệt qua từng phần tử mà phải dùng công thức toán học để tính tổng O(1).
• Cần xử lý đúng trường hợp đoạn [l, r] không chứa số lẻ (ví dụ l=2, r=3) để tránh lỗi logic.

Lỗi thường gặp

• Sử dụng biến kiểu int thay vì long long: Với r lên tới 10^9, tổng các số lẻ có thể vượt quá giới hạn của kiểu int (2*10^9), gây tràn số (overflow).
• Lỗi chia hết trong công thức: Khi tính (last - first) / 2 hoặc (l + r) * ssh / 2, cần đảm bảo phép chia là số nguyên (vì last - first và ssh hoặc l+r đều chẵn). Trong C++, nếu chia hai số nguyên cho nhau, kết quả là số nguyên, nên không sao. Nhưng nếu dùng số thực thì có thể mất độ chính xác.
• Quên kiểm tra trường hợp không có số lẻ: Nếu không kiểm tra if (first > last) hoặc logic tương tự, chương trình có thể tính toán sai (ví dụ n bị âm hoặc tính toán lộn xộn).