Hiểu bài toán

Bài toán yêu cầu tính tổng các số nguyên từ 1 đến n. Input là một số nguyên dương n (n ≤ 10^9), và output là tổng S = 1 + 2 + 3 + ... + n. Đây là bài toán kinh điển về tổng của một cấp số cộng.

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 sum = n * (n + 1) / 2;
    cout << sum;
    return 0;
}

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

Đây là cách hiệu quả nhất. Dựa vào công thức tổng quát của cấp số cộng: S = (n * (n + 1)) / 2. Ta chỉ cần thực hiện phép nhân và chia một lần. Để tránh tràn số (overflow) khi n lớn, biến n và biến lưu kết quả nên được khai báo kiểu long long.

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

#include <iostream>
using namespace std;

int main() {
    long long n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    cout << sum;
    return 0;
}

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

Phương pháp này sử dụng vòng lặp để cộng dồn từng số từ 1 đến n. Mặc dù đúng về mặt logic, nhưng với n lớn (ví dụ 10^9), thời gian chạy sẽ vượt quá giới hạn cho phép của bài toán (Time Limit Exceeded).

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

Bài học kinh nghiệm

• Biết công thức toán học giúp giải quyết bài toán trong thời gian hằng số O(1).
• Luôn chú ý đến giới hạn dữ liệu (constraints). Nếu n có thể lên tới 10^9, kết quả tính được có thể lên tới ~5*10^17, đòi hỏi kiểu dữ liệu 64-bit (long long).

Lỗi thường gặp

• Sử dụng kiểu int để lưu kết quả cuối cùng gây ra tràn số (integer overflow) khi n đủ lớn.
• Lỗi cú pháp khi viết công thức (ví dụ: thiếu dấu ngoặc hoặc sai thứ tự tính toán).