Hiểu bài toán

Cho một số nguyên dương N. Nhiệm vụ của bạn là kiểm tra xem N có thể được biểu diễn dưới dạng tổng của 4 số chính phương (số là bình phương của một số nguyên dương) hay không. Nếu có, in ra 1, ngược lại in ra -1.

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

Cách Brute Force 4 vòng lặp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool check(ll n) {
    if (n <= 0) return false;
    ll x = sqrt(n);
    return x * x == n;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    freopen("ssquare.inp", "r", stdin);
    freopen("ssquare.out", "w", stdout);
    ll n;
    cin >> n;
    ll limit = sqrt(n);
    for (ll i = 1; i <= limit; i++) {
        for (ll j = 1; j <= limit; j++) {
            for (ll k = 1; k <= limit; k++) {
                if (check(n - i * i - j * j - k * k)) {
                    cout << 1;
                    return 0;
                }
            }
        }
    }
    cout << -1;
    return 0;
}

• Time Complexity: O((sqrt(N))^3) ~ O(N^{1.5})
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất (Brute Force). Ta thử tất cả các bộ ba số chính phương (i^2, j^2, k^2) có tổng nhỏ hơn N. Sau đó, ta kiểm tra xem số còn lại (N - i^2 - j^2 - k^2) có phải là một số chính phương hay không. Để tối ưu hơn một chút, ta có thể thêm điều kiện để giảm số lần lặp, ví dụ i <= j <= k để tránh các trường hợp hoán vị của cùng một bộ ba số. Tuy nhiên, độ phức tạp vẫn thuộc loại cao và chỉ phù hợp với N nhỏ.

Cách Brute Force 2 vòng lặp kết hợp Hash Map (DP)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
    freopen("ssquare.inp", "r", stdin);
    freopen("ssquare.out", "w", stdout);

    int n;
    cin >> n;

    // Mảng đánh dấu các số có thể là tổng của 2 số chính phương
    // Kích thước tối đa N (vì tổng 2 số chính phương có thể lớn hơn N, ta chỉ cần quan tâm đến N)
    vector<bool> isSumOfTwoSquares(n + 1, false);

    for (int i = 1; i * i <= n; i++) {
        for (int j = 1; i * i + j * j <= n; j++) {
            isSumOfTwoSquares[i * i + j * j] = true;
        }
    }

    bool found = false;
    for (int i = 1; i * i <= n; i++) {
        for (int j = 1; j * j <= n; j++) {
            int rem = n - i * i - j * j;
            if (rem < 0) break;
            if (isSumOfTwoSquares[rem]) {
                found = true;
                break;
            }
        }
        if (found) break;
    }

    if (found) cout << 1;
    else cout << -1;
    return 0;
}

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

Cách tiếp cận này chia bài toán thành 2 phần:

1. Tính trước và đánh dấu tất cả các số có thể biểu diễn dưới dạng tổng của 2 số chính phương (i^2 + j^2). Ta lưu vào mảng boolean isSumOfTwoSquares.
2. Sau đó, duyệt qua các cặp số chính phương (i^2, j^2) một lần nữa. Với mỗi cặp, ta tính số còn lại là rem = N - i^2 - j^2. Nếu rem dương và đã được đánh dấu là tổng của 2 số chính phương ở bước 1, thì N là tổng của 4 số chính phương. Độ phức tạp thời gian giảm đáng kể so với 3 vòng lặp, khoảng O(N) do số lượng cặp (i, j) mà i^2 + j^2 <= N là O(N).

Cách Brute Force 2 vòng lặp (Tối ưu)

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    freopen("ssquare.inp", "r", stdin);
    freopen("ssquare.out", "w", stdout);
    int N;
    cin >> N;

    int limit = sqrt(N) + 1;
    for (int a = 1; a <= limit; ++a) {
        for (int b = a; b <= limit; ++b) {
            for (int c = b; c <= limit; ++c) {
                int remaining = N - (a*a + b*b + c*c);
                if (remaining <= 0) continue;
                int d = sqrt(remaining);
                if (d*d == remaining && d >= 1) {
                    cout << 1 << endl;
                    return 0;
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}

• Time Complexity: O(N^{1.5})
• Space Complexity: O(1)

Đây là phiên bản nâng cao của Brute Force 3 vòng lặp. Thay vì duyệt i, j, k từ 1 đến sqrt(N), ta duyệt a, b, c với điều kiện a <= b <= c để tránh lặp lại các bộ ba có cùng giá trị (số hoán vị). Điều này giảm số lượng bộ ba cần kiểm tra xuống đáng kể (khoảng 6 lần), nhưng về mặt độ phức tạp thuật toán lớn (Big O) vẫn là O((sqrt(N))^3). Tuy nhiên, trong thực tế với N vừa phải, nó chạy nhanh hơn nhiều so với Brute Force 3 vòng lặp không có điều kiện.

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

Bài học kinh nghiệm

• Bài toán có thể được biến đổi thành kiểm tra xem N có phải là tổng của 2 số, sao cho mỗi số đó lại là tổng của 2 số chính phương (N = (a^2+b^2) + (c^2+d^2)).
• Khi N khá lớn (ví dụ 10^5), số lượng cặp (i, j) sao cho i^2 + j^2 <= N chỉ rơi vào khoảng O(N), chứ không phải O(N^2). Điều này cho phép giải pháp O(N) (phương pháp Hash Map/DP) chạy rất nhanh.

Lỗi thường gặp

• Quên kiểm tra các số bị âm khi trừ các bình phương (ví dụ N - ii - jj - k*k < 0). Trong vòng lặp, cần phải break hoặc continue hợp lý.
• Sai lệch khi tính căn bậc hai do số nguyên (ví dụ int(sqrt(n)) có thể sai nếu n là số chính phương lớn do lỗi làm tròn float). Nên sử dụng long long và kiểm tra kỹ x*x == n hoặc dùng round/floor.
• Quên điều kiện số chính phương phải là bình phương của số nguyên dương (d >= 1).