要求出一个数最少能用几个完全平方数组成,有一个结论,一个数最多只要由四个完全平方数组成,有了这个结论就直接检查能不能1个数 2个数 3个数组成,都不行就只能用4个数了
代码:
#include <bits/stdc++.h>
using namespace std;
int n;
bool check1(int n){
int a=int(sqrt(n));
return a*a==n;
}
bool check2(int n){
for(int i=1;i*i<=n;i++){
if(check1(n-i*i)){
return true;
}
}
return false;
}
bool check3(int n){
for(int i=1;i*i<=n;i++){
if(check2(n-i*i)){
return true;
}
}
return false;
}
int main(void){
while(~scanf("%d",&n) && n!=-1){
if(check1(n)){
printf("1\n");
}
else if(check2(n)){
printf("2\n");
}
else if(check3(n)){
printf("3\n");
}
else{
printf("4\n");
}
}
return 0;
}