Hiểu bài toán

Cho một số nguyên dương $n$. Nhiệm vụ là tính tổng của tất cả các số nguyên dương nhỏ hơn $n$. Ví dụ, nếu $n = 5$, thì các số nhỏ hơn 5 là 1, 2, 3, 4, và tổng của chúng là 10.

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

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

#include <bits/stdc++.h>
using namespace std;
int main()
{
    freopen("TONG.INP", "r", stdin);
    freopen("TONG.OUT", "w", stdout);
    int n;
    cin >> n;
    long long tong = 0;
    for(int i = 1; i < n; i++)
    {
        tong += i;
    }
    cout<<tong;
    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 tất cả các số nguyên từ 1 đến $n-1$. Tại mỗi bước lặp, nó cộng số đó vào biến tổng. Đây là cách tiếp cận trực quan nhất, mô phỏng lại quá trình tính tổng thủ công.

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

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen("tong.inp","r")){
        freopen("tong.inp","r",stdin);
        freopen("tong.out","w",stdout);
    }
    ll n;
    cin>>n;
    cout<<(n-1)*n/2;
}

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

Thay vì lặp qua từng số, ta sử dụng công thức tổng quát cho tổng các số hạng của một cấp số cộng. Tổng các số từ 1 đến $k$ là $\frac{k(k+1)}{2}$. Trong bài toán này, ta cần tổng các số từ 1 đến $n-1$. Do đó, thay $k = n-1$ vào công thức, ta được: $\frac{(n-1)((n-1)+1)}{2} = \frac{(n-1)n}{2}$. Phương pháp này tính toán ngay lập tức không cần lặp.

Cách Công thức biến đổi

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define task "TONG"
int main()
{
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }
  ll n;
  cin>>n;
  ll s=0;
  cout<<(n+1)*n/2-n;
}

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

Đây là một biến thể của cách dùng công thức. Thay vì tính tổng từ 1 đến $n$ rồi trừ đi $n$, ta có thể rút gọn: $\frac{n(n+1)}{2} - n = \frac{n^2 + n - 2n}{2} = \frac{n^2 - n}{2} = \frac{n(n-1)}{2}$. Cách này cho kết quả tương tự nhưng có thể gây nhầm lẫn nếu không cẩn thận với phép trừ.

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

Bài học kinh nghiệm

• Bài toán có thể được quy về bài toán tính tổng các số tự nhiên từ 1 đến $n-1$.
• Việc sử dụng công thức tổng quát $\frac{k(k+1)}{2}$ giúp giảm thời gian thực thi từ tuyến tính O(n) xuống hằng số O(1).

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int cho biến tổng khi $n$ lớn có thể gây tràn số (overflow). Nên dùng long long.
• Trong vòng lặp, cần chú ý điều kiện dừng: i < n (tính đến $n-1$) thay vì i <= n (sẽ tính thừa $n$).