四平方和

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去，就正好可以表示为4个数的平方和。

CPU消耗  < 3000ms

______________________________________________________________________________________________________

/*由于这里 N<5000000 ，所以要进行一般的时间复杂度优化。一般算法时间上慢是因为 执行了太多不必要的语句情况。所以，一个方法是可以用一些条件去掉一些情况。比如这里 if(i*i+j*j>n)break;i 和 j 后面是增大的所以后面情况必然不能满足 平方和==n。这个改进后我算的平均优化了 2*2*2*2=16；然后因为比如1 1 2 2和2 2 1 1 是同一种情况，所以在循环的时候，j=i 开始循环。这样改进后，又优化了 2。所以总共是 16*2=32。所以，最坏时间复杂度是 n^3，这里最差情况大概是 10^10.  （我分析的很可能错误，如果您有想说的想法，欢迎在下方留言评论 ^_^) */#include<iostream>#include<cmath>using namespace std;int n;int a,b,c,d;void h(){int nn=sqrt(n)+1;for(int i=0;i<=nn;i++){for(int j=i;j<=nn;j++){if(i*i+j*j>n)break;for(int k=j;k<=nn;k++){if(i*i+j*j+k*k>n)break;for(int l=k;l<=nn;l++){if(i*i+j*j+k*k+l*l>n)break;int sum=i*i+j*j+k*k+l*l;if(n==sum){a=i;b=j;c=k;d=l;return; }}}}}}int main(){scanf("%d",&n);h();cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;return 0;}