[蓝桥杯 2016 省 AB] 四平方和
题目描述
四平方和定理,又称为拉格朗日定理:
每个正整数都可以表示为至多 $4$ 个正整数的平方和。
如果把 $0$ 包括进去,就正好可以表示为 $4$ 个数的平方和。
比如:
$5=0^2+0^2+1^2+2^2$。
$7=1^2+1^2+1^2+2^2$。
对于一个给定的正整数,可能存在多种平方和的表示法。
要求你对 $4$ 个数排序使得 $0 \le a \le b \le c \le d$。
并对所有的可能表示法按 $a,b,c,d$ 为联合主键升序排列,最后输出第一个表示法。
输入格式
程序输入为一个正整数 $N(N<5\times10^6)$。
输出格式
要求输出 $4$ 个非负整数,按从小到大排序,中间用空格分开。
样例 #1
样例输入 #1
5
样例输出 #1
0 0 1 2
样例 #2
样例输入 #2
12
样例输出 #2
0 2 2 2
样例 #3
样例输入 #3
773535
样例输出 #3
1 1 267 838
提示
时限 3 秒, 256M。蓝桥杯 2016 年第七届省赛
蓝桥杯 2016 年省赛 A 组 H 题(B 组 H 题)。
Java代码
import java.util.*;
class Sum implements Comparable<Sum>
{
int sum,c,d;
public Sum (int sum,int c,int d)
{
this.sum=sum;
this.c=c;
this.d=d;
}
public int compareTo(Sum s)
{
if(this.sum!=s.sum) return this.sum-s.sum; //先按sum升序排
if(this.c!=s.c) return this.c-s.c; //再按c升序排
else return this.d-s.d; //最后按d升序排
}
}
class Main
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Sum[] sum = new Sum[n];
int a,b,c,d=0;
int cnt=0;
//先存下c,d以及他们的平方和
for(c=0;c*c<=n;c++)
{
for(d=c;c*c+d*d<=n;d++)
{
sum[cnt++] = new Sum(c*c+d*d,c,d);
}
}
//按字典序排序
Arrays.sort(sum,0,cnt);
for(a=0;a*a<=n;a++)
{
for(b=a;a*a+b*b<=n;b++)
{
//二分法
int t = n-a*a-b*b;
int l=0,r=cnt-1;
while(l<r)
{
int m=l+r>>1;
if(sum[m].sum>=t) r=m;
else l=m+1;
}
if(sum[l].sum==t)
{
System.out.println(a+" "+b+" "+sum[l].c+" "+sum[l].d);
return;
}
}
}
}
}
ps:还不如暴力快