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

冷不防 2023-07-04 04:56 53阅读 0赞

## 问题描述 ##

四平方和定理，又称为拉格朗日定理：  
每个正整数都可以表示为至多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  
**输出**

0 0 1 2  
**输入**

12  
**输出**

0 2 2 2  
**输入**

773535  
**输出**

1 1 267 838  
**题目限制**

单输出时间限制< 1s  
峰值内存消耗 < 256M  
CPU消耗 < 3000ms

**思路**：作为蓝桥省赛的第8题，略显简单，暴力循环解决就ok了，但是题目要求限制在1s内，因此设置循环条件的时候要多加注意。

代码如下;

#include <stdio.h>
    int main ()
    { 
    	int a,b,c,d;
    	int sum=0;
    	int n;
    	scanf("%d",&n);
    	for(a=0;a<50;a++)
    	{ 
    		int flag=0;
    		sum=0;
    		if(a*a>n)continue;//加这些条件是为了避免多余的计算，减少运行时间 
    		for(b=a;b<500;b++)
    		{ 
    			if(b*b>n)continue;//加这些条件是为了避免多余的计算，减少运行时间
    			for(c=b;c<5000;c++)
    			{ 
    				if(c*c>n)continue;//加这些条件是为了避免多余的计算，减少运行时间
    				for(d=c;d<50000;d++)
    				{ 
    					sum=a*a+b*b+c*c+d*d;;
    					if(sum==n)
    					{ 
    						printf("%d %d %d %d\n",a,b,c,d);
    						return 0;
    					}
    					
    					if(sum>n)
    					{ 
    					    break;
    					    flag=1;
    					}
    				}
    				if(flag==1)break;//加这些条件是为了避免多余的计算，减少运行时间
    			}
    			if(flag==1)break;//加这些条件是为了避免多余的计算，减少运行时间
    		}
    		if(flag==1)break;//加这些条件是为了避免多余的计算，减少运行时间
    	}
    	
    }

*运行示例*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200208153944257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MjgxODA3,size_16,color_FFFFFF,t_70