四方定理 c++做法

题目中n<=100 纯暴力做法O(n^4)可能会超时
所以我这里用3个for循环 最后一个数算出判断是否递增或递减(注意:要判断是否为完全平方数)
整体代码较简洁,无需在每个循环中额外判断,提前break(当然这样做更快)

AC代码如下:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        int x=sqrt(n),ans=0;
        for(int i=0;i<=x;i++){
            for(int j=i;j<=x;j++){
                for(int k=j;k<=x;k++){
                    int l=n-i*i-j*j-k*k;
                    double a=sqrt(l);
                    int b=a;
                    if(a>=k&&a==b){
                        ans++;
                        
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
}