数论题解（非DP）

核心原理（基于定理）
根据拉格朗日四平方定理和相关推论，任意自然数 $n$ 的最少平方和个数只可能是 $1、2、3、4$，且满足以下判定规则：
若 $n$ 是完全平方数 → 答案为 $1$（如 $n$ =$16$ = $4^2$）；
若 $n$ 可表示为 $4^k×(8m+7)$ 的形式 → 答案为 $4$（这是勒让德三平方定理的推论，此类数无法用 $3$ 个平方数表示）；
若 $n$ 可表示为两个完全平方数的和 → 答案为 $2$（如 $n$ = $25$ = $3^2$ + $4^2$）；
其他情况 → 答案为 $3$。

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

bool isOneSquare(int n) 
{
    int x = sqrt(n);
    return x * x == n || (x + 1) * (x + 1) == n;
}

bool isFourSquare(int n)
{
    while (n % 4 == 0)
        n /= 4;
    return n % 8 == 7;
}

bool isTwoSquares(int n)
{
    for (int i = 0; i * i <= n; i++)
    {
        int x = n - i * i;
        if (isOneSquare(x))
            return true;
    }
    return false;
}

int solve(int n)
{
    if (isOneSquare(n))
        return 1;
    if (isFourSquare(n))
        return 4;
    if (isTwoSquares(n))
        return 2;
    return 3;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", solve(n));
    return 0;
}