Hiểu bài toán

Bài toán yêu cầu tìm số lượng lớn nhất các bình phương (squares) cần thiết để biểu diễn bất kỳ số nguyên dương nào không vượt quá n. Cụ thể, với mỗi số k từ 1 đến n, ta cần tìm số lượng bình phương ít nhất để tạo thành k (theo định lý bốn bình phương của Lagrange, mỗi số tự nhiên là tổng của tối đa 4 bình phương). Câu hỏi là: Trong khoảng từ 1 đến n, số nào требует nhiều bình phương nhất, và số lượng đó là bao nhiêu? Ta cần in ra số lượng này (đáp án) sau khi chia cho 10^9 + 7.

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

Cách Phân tích theo tính chất số học (hàm số gia)

int main() {
    long long n;
    scanf("%lld", &n);
    printf("%lld", (n < 3 ? n : (n < 7 ? 3 : 4)));
    return 0;
}

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

Phân tích các số đầu tiên cho thấy:

• Các số 1, 2, 3 lần lượt cần 1, 2, 3 bình phương (sử dụng toàn số 1^2).
• Các số 4, 5, 6: Số 4 là 2^2 (cần 1). Số 5 là 2^2 + 1^2 (cần 2). Số 6 là 2^2 + 1^2 + 1^2 (cần 3). Do đó, max cần 3.
• Các số từ 7 trở lên: Do định lý Lagrange, mọi số ≥ 7 đều có thể biểu diễn bằng 4 bình phương hoặc ít hơn. Kiểm tra kỹ hơn cho thấy các số từ 7 đến 23 đều có thể biểu diễn bằng ≤ 3 bình phương. Tuy nhiên, các số lớn hơn như 28, 31, ... có thể yêu cầu 4 bình phương. Do đó, với mọi n ≥ 7, luôn t tồn tại ít nhất một số ≤ n yêu cầu 4 bình phương. Đồng thời, không có số nào yêu cầu quá 4 bình phương. Vậy giá trị lớn nhất cần tìm là 4.

Cách tiếp cận này đơn giản hóa vấn đề thành một hàm số gia:

• Nếu n < 3: đáp án là n.
• Nếu 3 ≤ n < 7: đáp án là 3.
• Nếu n ≥ 7: đáp án là 4. Code sử dụng toán tử 3 ngôi lồng nhau để xử lý logic này.

Cách Giải thích chi tiết Logic Phân loại

#include <cstdio>

int main() {
    long long n;
    scanf("%lld", &n);

    long long ans;
    if (n < 3) ans = n;
    else if (n < 7) ans = 3;
    else ans = 4;

    printf("%lld", ans);
    return 0;
}

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

Đây là phiên bản dễ đọc hơn của Approach 1, minh họa rõ ràng các trường hợp:

1. n = 1: Max squares = 1 (số 1).
2. n = 2: Max squares = 2 (số 2).
3. 3 <= n <= 6: Max squares = 3 (đến từ số 3).
4. n >= 7: Max squares = 4 (vì luôn t tồn tại số như 7, 15, 23... yêu cầu 4 bình phương).

Lưu ý: Đáp án được yêu cầu in ra sau khi chia cho 10^9 + 7. Với các giá trị đầu vào n ≤ 10^18, giá trị max squares chỉ là 1, 2, 3 hoặc 4. Do đó, phép chia lấy dư là không cần thiết về mặt giá trị nhưng là yêu cầu đầu ra.

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

Bài học kinh nghiệm

• Theo định lý Lagrange, mọi số nguyên dương là tổng của tối đa 4 bình phương.
• Các số nhỏ (1, 2, 3) là ngoại lệ khi chỉ có thể dùng bình phương 1^2, dẫn đến nhu cầu 1, 2, 3 bình phương tương ứng.
• Từ số 7 trở đi, luôn t tồn tại các số (như 7, 15, 23...) không thể biểu diễn bằng 3 bình phương, nên cần tối đa 4 bình phương.

Lỗi thường gặp

• Viết code quá phức tạp (dùng vòng lặp/quy hoạch động) dẫn đến TLE do n lên tới 10^18.
• Quên xử lý các trường hợp biên cho các số n rất nhỏ (1, 2).