Hiểu bài toán

Xét dãy số Tn được định nghĩa bởi công thức Tn = n^2 - (n-1)^2. Yêu cầu tính tổng S = T1 + T2 + ... + T_n với n là số nguyên dương (1 ≤ n ≤ 10^6). Ta cần tìm giá trị S cho trước n.

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

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

#include <stdio.h>
int main()
{
    long long int n, T = 0;
    scanf("%lld", &n);
    for (long long int i = 1; i <= n; i++)
    {
        T = T + 2*i - 1;
    }
    printf("%lld",T);
}

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

Phương pháp này mô phỏng lại quá trình tính tổng các số hạng. Biến đổi T_n = n^2 - (n-1)^2 = n^2 - (n^2 - 2n + 1) = 2n - 1. Do đó, tổng S = Σ(2i - 1) từ i = 1 đến n. Code sử dụng vòng lặp for để lặp từ 1 đến n, mỗi lần lặp cộng dồn giá trị (2*i - 1) vào biến T. Với n lên tới 10^6, số lượng thao tác là khoảng 10^6, hoàn toàn chấp nhận được trong thời gian chạy.

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

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    long long S = n * n;
    cout << S;
    return 0;
}

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

Đây là phương pháp hiệu quả nhất. Ta có tổng S = Σ(2i - 1) từ i = 1 đến n. Đây là tổng của n số hạng là các số lẻ liên tiếp bắt đầu từ 1. Một tính chất quan trọng của dãy số lẻ là tổng của n số lẻ đầu tiên bằng bình phương của n đó, tức là 1 + 3 + 5 + ... + (2n-1) = n^2. Do đó, kết quả chỉ cần tính n * n. Phương pháp này bỏ qua vòng lặp và tính kết quả ngay lập tức, phù hợp với mọi giá trị n (kể cả n rất lớn).

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

Bài học kinh nghiệm

• Phép biến đổi Tn = n^2 - (n-1)^2 = 2n - 1 cho thấy Tn là một số lẻ.
• Tổng S là tổng của n số lẻ đầu tiên, bằng n^2.
• Với n ≤ 10^6, kết quả n^2 có thể lên tới 10^12, nên cần sử dụng kiểu dữ liệu 64-bit (long long) để tránh tràn số.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int (32-bit) dẫn đến tràn số (overflow) khi n lớn (ví dụ n = 10^6 thì n^2 = 10^12 > 2^31 - 1).
• Viết sai công thức T_n (ví dụ nhầm dấu trừ) dẫn đến vòng lặp tính sai.