4. 玩玩拉格朗日四平方和定理

常规
1

4. 玩玩拉格朗日四平方和定理

XJOI - 题目ID：8004选做题100分

最新提交：

Wrong Answer

60 分

历史最高：

Wrong Answer

60 分

时间限制: 200ms

空间限制: 32000kB

题目描述

时间：0.2 空间：32M

题目描述：

拉格朗日四平方和定理：

每一个非负整数都可以表示成四个非负整数的平方和。

例如 5 = 0^2 + 0^2 + 1^2 + 2^2

给定一个正整数n，请你将n拆成 a^2+b^2+c^2+d^2，问 a+b+c+d最小是多少。

输入格式：

一个正整数表示 n。

输出格式：

一个正整数表示答案。

样例输入1：

4

样例输出1：

2

约定：

1<=n<=90000

提示：

a^2 = a*a

下面是我的代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n*2;i++){
		for(int j=0;j<n*2;j++){
			for(int k=0;k<n*2;k++){
				for(int s=0;s<n*2;s++){
					if(i*i+j*j+k*k+s*s==n){
						cout<<i+j+k+s;
						return 0;	
					}
				}
			}
		}
	}
	cout<<0;
    return 0;
}

谁能告诉我为什么WA50分

3 个赞
2 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,b=1000000;
	scanf("%d",&n);
	for(int i=0;i*i<=n;i++){
		for(int j=0;j*j<=n-i*i;j++){
			for(int k=0;k*k<=n-i*i-j*j;k++){
				int z=n-k*k-j*j-i*i;
				z=sqrt(z);
				if(i*i+j*j+k*k+z*z==n&&i+j+k+z<b)b=i+j+k+z;
			}
		}
	}
	printf("%d",b);
	return 0;
}
5 个赞
3

希望能帮到你：
改long long祭

2 个赞
4

建议：用ans来存答案，使用min

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,ans=-1;
	cin>>n;
	for(int i=0;i<n*2;i++){
		for(int j=0;j<n*2;j++){
			for(int k=0;k<n*2;k++){
				for(int s=0;s<n*2;s++){
					if(i*i+j*j+k*k+s*s==n){
						if(ans==-1) ans=i+j+k+s;
						else ans=min(ans,i+j+k+s);
						return 0;	
					}
				}
			}
		}
	}
	if(ans==-1) cout<<0;
	else cout<<ans;
    return 0;
}
4 个赞