Editorial for thetich: Tổng thể tích

Hiểu bài toán

Bài toán yêu cầu tính tổng thể tích của n khối lập phương, trong đó độ dài cạnh của khối thứ i là i. Thể tích của một khối lập phương cạnh i là i^3. Do đó, ta cần tính tổng S = 1^3 + 2^3 + 3^3 + ... + n^3. Với giới hạn n ≤ 1000, kết quả có thể lên tới khoảng (1000^4)/4 ~ 2.5 * 10^11, vượt quá giới hạn của kiểu int 32-bit, nên cần sử dụng kiểu dữ liệu lớn hơn (long long) để lưu kết quả.

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 += (long long)i * i * i;
    }
    printf("%lld\n", 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 chạy từ 1 đến n. Tại mỗi bước lặp, nó tính giá trị i^3 (bằng cách nhân i * i * i) và cộng dồn vào biến tổng. Để tránh tràn số trong quá trình tính toán trung gian, ta ép kiểu i sang kiểu long long trước khi nhân. Đây là cách tiếp cận trực quan và dễ hiểu nhất.

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

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int main() {
    long long n;
    scanf("%lld", &n);
    long long tong = (n * (n + 1) / 2) * (n * (n + 1) / 2);
    printf("%lld", tong);
    return 0;
}

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

Phương pháp này dựa trên định thức toán học: tổng các số mũ ba từ 1 đến n bằng bình phương của tổng các số tự nhiên từ 1 đến n. Cụ thể, tổng S = (n(n+1)/2)^2. Thay vì chạy vòng lặp, ta chỉ cần thực hiện một vài phép toán số học đơn giản. Phương pháp này hiệu quả nhất về mặt thời gian tính toán, đặc biệt với n lớn.

Cách Hàm phụ trợ (Modular)

#include "stdio.h"

int a(int n);
long long int b ( int n);
int main () {
    int n = 0;
    scanf("%d",&n);
    printf("%lld",b(n));
    return 0;
}

long long int b ( int n)
{
    int i = 0;
    long long int tong = 0 ;
    for ( i = 1; i <= n ; i++)
    {
        tong = tong + a(i);
    }
    return tong;
}

int a(int n)
{
    return n*n*n;
}

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

Đây là biến thể của phương pháp vòng lặp cơ bản, nhưng logic được chia thành các hàm phụ trợ (hàm 'a' để tính lập phương và hàm 'b' để tính tổng). Về bản chất, độ phức tạp vẫn là O(n).

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

Bài học kinh nghiệm

• Định thức toán học: Tổng bình phương các số tự nhiên bằng bình phương của tổng các số tự nhiên, tương tự như tổng các số lũy thừa bậc 3.
• Kiểu dữ liệu: Với n lên tới 1000, kết quả có thể vượt quá 2^31 - 1, do đó bắt buộc phải sử dụng kiểu long long (64-bit integer) để lưu trữ kết quả.

Lỗi thường gặp

• Tràn số (Overflow): Tính i^3 bằng cách nhân ba số int liên tiếp nếu không ép kiểu có thể gây tràn số, ví dụ i = 1000 thì 100010001000 = 10^9 vẫn an trong int nhưng nếu n lớn hơn 1290 thì sẽ tràn. Với n=1000 thì int (2*10^9) là vừa đủ nhưng để an toàn nên dùng long long.
• Sai công thức: Nhầm lẫn giữa tổng các số mũ 2 và tổng các số mũ 3 (ví dụ: dùng công thức n(n+1)(2n+1)/6).