Chương trình C++ tính tổng bình phương n số tự nhiên đầu tiên

Tính S = 1² + 2² + 3² + ... + n².

Phương pháp 1: Vòng lặp O(n)

long squareSumLoop(int n) {
    long sum = 0;
    for(int i = 1; i <= n; i++)
        sum += 1L * i * i;
    return sum;
}

Phương pháp 2: Công thức toán học O(1)

Công thức: S = n(n+1)(2n+1) / 6

long squareSumFormula(int n) {
    return 1L * n * (n + 1) * (2 * n + 1) / 6;
}

Code hoàn chỉnh

#include <iostream>
using namespace std;

long squareSumLoop(int n) {
    long sum = 0;
    for(int i = 1; i <= n; i++)
        sum += 1L * i * i;
    return sum;
}

long squareSumFormula(int n) {
    return 1L * n * (n + 1) * (2 * n + 1) / 6;
}

int main() {
    int n;
    cout << "Nhap n: ";
    cin >> n;
    
    cout << "Vong lap O(n): " << squareSumLoop(n) << endl;
    cout << "Cong thuc O(1): " << squareSumFormula(n) << endl;
    
    return 0;
}

Kết quả

Nhap n: 4
Vong lap O(n): 30
Cong thuc O(1): 30

Chứng minh công thức (Induction)

• Cơ sở n=1: 1(2)(3)/6 = 1 ✓
• Giả sử đúng cho n=k.
• Chứng minh n=k+1: S(k+1) = S(k) + (k+1)² = k(k+1)(2k+1)/6 + (k+1)² = (k+1)(k+2)(2k+3)/6 ✓

Lưu ý tràn số (Overflow)

• int (32-bit): an toàn đến n ≈ 1600.
• long long (64-bit): an toàn đến n ≈ 10⁶.
• Dùng 1LL * n * (n+1) * (2*n+1) / 6 để ép tính toán 64-bit.

Mở rộng: Tổng các lũy thừa khác