Hiểu bài toán

Bài toán yêu cầu tính tổng S là tổng các số nguyên từ 1 đến n (1 + 2 + 3 + ... + n). Với n có thể lên tới 10^9, cần một cách tính hiệu quả thay vì vòng lặp.

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

Cách Công thức toán học

#include <iostream>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long S = n * (n + 1) / 2;
    cout << S << endl;
    return 0;
}

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

Sử dụng công thức tổng quát S = n * (n + 1) / 2. Đây là cách hiệu quả nhất, tính toán trong thời gian hằng số. Phải dùng kiểu dữ liệu 64-bit (long long) để tránh tràn số khi n lớn.

Cách Vòng lặp For

#include <iostream>
using namespace std;
int main() {
    long long n;
    cin >> n;
    long long S = 0;
    for (long long i = 1; i <= n; i++) {
        S += i;
    }
    cout << S << endl;
    return 0;
}

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

Dùng vòng lặp để cộng dồn từng số. Cách này đúng với n nhỏ nhưng quá chậm với n = 10^9 (vượt quá giới hạn thời gian chạy).

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

Bài học kinh nghiệm

• Bài toán tổng quát có công thức toán học trực tiếp, nên ưu tiên công thức thay vì mô phỏng.
• Kiểu dữ liệu (data type) rất quan trọng: n = 10^9 thì n(n+1)/2 ≈ 510^17, vượt quá giới hạn của int (khoảng 2*10^9), cần dùng long long.

Lỗi thường gặp

• Dùng biến kiểu int導致 tràn số (overflow) khi tính toán, dẫn đến kết quả sai.
• Quên không chia 2 cho phép chẵn (n(n+1) chẵn nên có thể chia 2 trước) nhưng trong C++ với long long thì n(n+1)/2 an toàn do phép nhân chẵn.