- 拉格朗日四平方和定理
题目ID：8004必做题100分
最新提交：
Time Limit Exceeded
0 分
历史最高：
Wrong Answer
20 分
时间限制: 2000ms
空间限制: 32000kB
题目描述
拉格朗日四平方和定理：
每一个非负整数都可以表示成四个非负整数的平方和。
例如
5
0
2
+
0
2
+
1
2
+
2
2
5=0
2
+0
2
+1
2
+2
2
给定一个正整数
n
n，请你将
n
n拆成
a
2
+
b
2
+
c
2
+
d
2
a
2
+b
2
+c
2
+d
2
，问
a
+
b
+
c
+
d
a+b+c+d最小是多少。
输入格式：
一个正整数表示
n
n。
输出格式：
一个正整数表示答案。
样例输入1：
4
样例输出1：
2
数据范围：
1
≤
n
≤
90000
1≤n≤90000
提示：
在C++中，我们可以用
a
∗
a
a∗a表示
a
2
a
2
代码：
#include<bits/stdc++.h>
using namespace std;
int m[90005]={0};
int main(){
int n,maxn=1e9;
cin>>n;
for(int a=0;a<sqrt(n/2);a++){
for(int b=0;b<sqrt(n/2);b++){
for(int c=0;c<sqrt(n/2);c++){
double d=sqrt(n-aa-bb-cc);
if(abs(aa+bb+cc+d*d-n)<1e-6){
m[c]=a+b+c+d;
}
}
}
}
for(int i=0;i<n;i++){
if(m[i]!=0){
maxn=min(maxn,m[i]);
}
}
cout<<maxn;
return 0;
}