四平方和 【暴力但是剪枝】

蓝桥杯 四平方和 JAVA

暴力但是剪枝+注意组合数

因为是组合情况，所以从下一层的for应要从上一层的起始开始。

　　四平方和定理，又称为拉格朗日定理：

　　每个正整数都可以表示为至多4个正整数的平方和。
　　如果把0包括进去，就正好可以表示为4个数的平方和。

for(int i=0;i<=n;i++) {  //注意数据范围，每个数值一定会小于N的开根号。

    for(int j=i;j<=n;j++) { //注意 从i开始

         for(int k=j;k<=n;k++) {

            for(int m=k;m<=n;m++) {

                int cur = i*i+j*j+k*k+m*m;

                if(cur>N) break; //剪枝，不然过不了

                    if(cur==N) {

                            System.out.println(i+" "+j+" "+k+" "+m);

                         return ;

                        }

                }

            }

        }

    }