题目
四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多四个正整数的平方和。
如果把 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0 包括进去，就正好可以表示为四个数的平方和。
比如：
<math> <semantics> <mrow> <mstyle displaystyle="true" scriptlevel="0"> <mn> 5 </mn> <mo> = </mo> <msup> <mn> 0 </mn> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mn> 0 </mn> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mn> 1 </mn> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mn> 2 </mn> <mn> 2 </mn> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex"> \displaystyle 5 = 0^2 + 0^2 + 1^2 + 2^2 </annotation> </semantics> </math>5=02+02+12+22
<math> <semantics> <mrow> <mstyle displaystyle="true" scriptlevel="0"> <mn> 7 </mn> <mo> = </mo> <msup> <mn> 1 </mn> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mn> 1 </mn> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mn> 1 </mn> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mn> 2 </mn> <mn> 2 </mn> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex"> \displaystyle 7 = 1^2 + 1^2 + 1^2 + 2^2 </annotation> </semantics> </math>7=12+12+12+22
则对于一个给定的正整数 <math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application/x-tex"> n </annotation> </semantics> </math>n，可以表示为： <math> <semantics> <mrow> <mi> n </mi> <mo> = </mo> <msup> <mi> a </mi> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mi> b </mi> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mi> c </mi> <mn> 2 </mn> </msup> <mo> + </mo> <msup> <mi> d </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> n = a^2 + b^2 + c^2 + d^2 </annotation> </semantics> </math>n=a2+b2+c2+d2。
你需要求出 字典序 最小的一组解 <math> <semantics> <mrow> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo separator="true"> , </mo> <mi> c </mi> <mo separator="true"> , </mo> <mi> d </mi> </mrow> <annotation encoding="application/x-tex"> a,b,c,d </annotation> </semantics> </math>a,b,c,d。
字典序大小：从左到右依次比较，如果相同则比较下一项，直到有一项不同，较小的一方字典序更小，反之字典序更大，所有项均相同则二者字典序相同。
输入格式
程序输入为一个正整数 <math> <semantics> <mrow> <mi> N </mi> <mo> ( </mo> <mn> 1 </mn> <mo> ≤ </mo> <mi> N </mi> <mo> ≤ </mo> <mn> 5000000 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> N(1 \leq N \leq 5000000) </annotation> </semantics> </math>N(1≤N≤5000000)。
输出格式
输出四个非负整数 <math> <semantics> <mrow> <mi> a </mi> <mo separator="true"> , </mo> <mi> b </mi> <mo separator="true"> , </mo> <mi> c </mi> <mo separator="true"> , </mo> <mi> d </mi> </mrow> <annotation encoding="application/x-tex"> a,b,c,d </annotation> </semantics> </math>a,b,c,d，中间用空格分开。
样例输入
5
样例输出
0 0 1 2
样例输入
12
样例输出
0 2 2 2
题解
可以只遍历三个数，最后一个数用 n 减去前三个数的平方和再开根号得到，判断条件是，开出的根号正好是个整数
#include<iostream>
#include<math.h>
using namespace std;
int main(){
int n;
cin>>n;
for(int i=0;i<sqrt(n);i++)
for(int j=0;j<sqrt(n);j++)
for(int k=0;k<sqrt(n);k++)
if(sqrt(n-(i*i+j*j+k*k))==int(sqrt(n-(i*i+j*j+k*k)))){
cout<<i<<" "<<j<<" "<<k<<" "<<int(sqrt(n-(i*i+j*j+k*k)));
return 0;
}
return 0;
}
京公网安备 11010502036488号