费马四平方数猜想指出，任意自然数都可以分解成不超过四个完全平方数的和。 例如：144 = 12
2 ，14 = 1
2 + 2
2 + 3
2。 现在给出自然数
N（
N ≤ 60000），_gXX希望知道N最少可以分解成多少个完全平方数。
Input
输入文件包含多组数据。 第一行，一个整数
T（
T ≤ 10000），表示数据的组数。 第2~
T+1行，每行一个自然数
N。
Output
对于每组数据输出一个自然数，表示自然数
N最少可以分解成多少个完全平方数。
Sample Input
1
144
Sample Output
1
简单的哈希，因为最多只有4总，枚举这四种状况即可
#include
#include
#include
#include
using namespace std; int hash[60005]; int main() { int t,n,i,j,flag; memset(hash,0,sizeof(hash)); for(i = 1; i*i<=60000; i++) hash[i*i] = 1; scanf("%d",&t); while(t--) { scanf("%d",&n); flag = 0; if(hash[n]) { printf("1\n"); continue; } for(i = 1; i*i<=n; i++) { if(hash[n-i*i]) { printf("2\n"); flag = 1; break; } } if(flag) continue; flag = 0; for(i = 1; i*i<=n; i++) { for(j = 1; j*j+i*i<=n; j++) { if(hash[n-i*i-j*j]) { printf("3\n"); flag = 1; break; } } if(flag) break; } if(flag) continue; printf("4\n"); } return 0; }