Hiểu bài toán

Bài toán yêu cầu tính tổng bình phương của các số tự nhiên liên tiếp từ 1 đến n, được ký hiệu là Sn = 1^2 + 2^2 + ... + n^2. Dữ liệu vào là một số nguyên dương n (1 ≤ n ≤ 10^6). Đầu ra là giá trị tổng Sn (dạng số nguyên lớn, cần dùng kiểu dữ liệu 64-bit).

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

Cách Vòng lặp cơ bản (Brute Force)

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

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

Phương pháp này sử dụng một vòng lặp for để chạy từ 1 đến n. Tại mỗi bước lặp, nó tính bình phương của số hiện tại và cộng vào biến tổng. Với n lên tới 10^6, số lượng phép tính là khoảng 1 triệu, hoàn toàn chấp nhận được trong thời gian chạy của hầu hết các hệ thống chấm tự động (thường là vài mili giây). Lưu ý dùng 1ll * i * i hoặc ép kiểu để tránh tràn số nếu i là kiểu int khi tính bình phương.

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

#include <stdio.h>

int main() {
    long long n;
    scanf("%ld",&n);
    long long res = n * (n + 1) * (2 * n + 1) / 6;
    printf("%ld", res);
    return 0;
}

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

Phương pháp này dựa vào công thức tổng quát: 1^2 + 2^2 + ... + n^2 = n(n + 1)(2n + 1) / 6. Thay vì chạy vòng lặp, chỉ cần thực hiện phép tính trực tiếp. Phương pháp này nhanh hơn đáng kể, đặc biệt với n lớn, và tránh hoàn toàn rủi ro tràn số nếu khai báo biến đúng (dùng long long).

Cách Sử dụng hàm pow (Tham khảo)

#include<stdio.h>
#include<math.h>
int main (){
    int n  ;
    long long tong = 0;
    scanf("%d",&n);
    for (int i = 1 ;i<=n ; i++){
        tong += pow(i,2);
    }
    printf("%lld",tong);
    return 0;
}

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

Tương tự phương pháp 1, nhưng sử dụng hàm pow(i, 2) từ thư viện math.h để tính bình phương. Tuy nhiên, hàm pow làm việc với số thực double, có thể gây sai số làm tròn đối với các số lớn và thường chậm hơn phép nhân trực tiếp.

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

Bài học kinh nghiệm

• Phương pháp công thức toán học (O(1)) là tối ưu nhất về thời gian.
• Kiểu dữ liệu long long (64-bit) là bắt buộc để lưu kết quả do giới hạn n ≤ 10^6.

Lỗi thường gặp

• Tràn số (Integer Overflow) khi tính bình phương hoặc nhân các số lớn nếu dùng int.
• Sai công thức tính tổng bình phương.