要求出一个数最少能用几个完全平方数组成,有一个结论,一个数最多只要由四个完全平方数组成,有了这个结论就直接检查能不能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;
}