【题解】完全平方数最少拆分（四平方和）

题目大意

给定一个正整数 $n$，将其拆分为若干个完全平方数之和，求最少需要多少个平方数。

样例解释

输入 18，最优拆法是 $9 + 9 = 3^2 + 3^2$，所以输出 2。

核心定理：拉格朗日四平方和定理

任意正整数都可以表示为不超过4个正整数的平方和。

也就是说，答案只可能是 $1$、$2$、$3$ 或 $4$，不用考虑更多了。

解法：从小到大枚举验证

既然答案最多为$4$，我们按 $1→2→3→4$ 的顺序检查，找到即最优。

判 $1$ 个

遍历 $i^2$，看有没有 $i^2 = n$。

判 $2$ 个

双重循环，看有没有 $i^2 + j^2 = n$。

判 $3$ 个

三重循环，看有没有 $i^2 + j^2 + k^2 = n$。

判 $4$ 个

根据定理，前三个都不成立时，答案一定是 $4$。

#include <bits/stdc++.h>
using namespace std;
int c;
int main() {
	cin >> c;
	for(int i = 0; i * i <= c; i++)
		if(i * i == c) { cout << 1; return 0; }
	for(int i = 0; i * i <= c; i++){
		for(int j = i; j * j + i * i <= c; j++)
			if(i * i + j * j == c) { cout << 2; return 0; }
	}
	for(int i = 0; i * i <= c; i++){
		for(int j = i; j * j + i * i <= c; j++){
			for(int k = j; i * i + j * j + k * k <= c; k++)
				if(i * i + j * j + k * k == c) { cout << 3; return 0; }
		}
	}
	cout << 4;
}