[蓝桥杯] 四平方和

峰值内存消耗 < 256M　　CPU消耗  < 3000ms

【题目描述 - Problem Description】

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

 

比如：

5 = 0^2 + 0^2 + 1^2 + 2^2

7 = 1^2 + 1^2 + 1^2 + 2^2

（^符号表示乘方的意思）

 

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对4个数排序：

0 <= a <= b <= c <= d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法

程序输入为一个正整数N (N<5000000)

要求输出4个非负整数，按从小到大排序，中间用空格分开

 

输入	5	12	773535
输出	0 0 1 2	0 2 2 2	1 1 267 838

 

 

 

【题解】

　　搜索，注意剪枝。

　　四层循环的速度可以……因为强迫症自己又写了个DFS版本……

 

【代码 C++】

1 #include 
      
        2 int main() { 3     int i1, i2, i3, i4, s1, s2, s3, s4, n; 4     scanf("%d", &n); 5     for (i1 = 0;; ++i1){ 6         s1 = i1*i1; 7         for (i2 = i1; s1 + i2*i2 * 3 <= n; ++i2){ 8             s2 = s1 + i2*i2; 9             for (i3 = i2; s2 + i3*i3 * 2 <= n; ++i3){10                 s3 = s2 + i3*i3;11                 for (i4 = i3; s3 + i4*i4 <= n; ++i4){12                     s4 = s3 + i4*i4;13                     if (s4 == n){14                         printf("%d %d %d %d\n", i1, i2, i3, i4);15                         goto ed;16                     }17                 }18             }19         }20     }21 ed:;22     return 0;23 }
      

1 #include 
      
        2 int n, q[5]; 3 bool isFid; 4 void DFS(int lst, int i, int sum){ 5     if (isFid) return; 6     if (i){ 7         int tmp; 8         while (sum + lst*lst*i <= n){ 9             q[i] = lst;10             DFS(lst, i - 1, sum + lst*lst);11             ++lst;12         }13     }14     else if (sum == n){15         printf("%d %d %d %d\n", q[4], q[3], q[2], q[1]);16         ++isFid;17     }18 }19 int main() {20     scanf("%d", &n);21     DFS(0, 4, 0);22     return 0;23 }