四平方和

四平方和

时间： 1ms        内存：128M

描述：

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

 1 1 267 838

输入：

为一个正整数N (N<5000000)

输出：

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

示例输入：

5

示例输出：

0 0 1 2

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
int what(int n)
{
	int i,j,k,l;
		for(i=0;i*i<3000;i++)
	{
		for(j=i;j*j<3000;j++)
		{
			for(k=j;k*k<3000;k++)
			{
				for(l=k;l*l<3000;l++)
				{
					if(l*l+k*k+j*j+i*i==n)
					{
					printf("%d %d %d %d\n",i,j,k,l);
					return 0;
					}
				}
			}
		}
	}
}
int main()
{
	int n,i,j,k,l;
	scanf("%d",&n);
	what(n);
}

参考答案（时间最优[0]）：

	#include <stdio.h>  
	#include <math.h>  
	int main()  
	{  
	    int n;  
	    int flag = 0;  
	    scanf("%d",&n);  
	    for(int i = 0 ; i * i <= n ; i ++)  
	    {  
	        for(int j = 0 ; j * j <= n ; j ++){  
	            for(int k = 0 ; k * k <= n ; k ++)  
	            {  
	                int temp = n - i*i - j*j - k*k;  
	                double l = sqrt((double) temp);  
	                if(l == (int)l )  
	                {  
	                    printf("%d %d %d %d\n",i,j,k,(int)l);  
	                    flag = 1;  
	                    break;  
	                }  
	            }  
	            if(flag)break;  
	        }  
	        if(flag)break;  
	    }  
	    return 0;  
	}  

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。