四平方和

时间: 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;  
	}  

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