AcWing 1221. 四平方和
原题链接
简单
作者:
暂时换个名字
,
2021-01-21 21:24:41
,
所有人可见
,
阅读 371
import java.util.Scanner;
public class 四平方和 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
yxc2(n);
}
public static void yxc(int n) {//方法一,三层枚举。会超时
for(int a=0;a*a<=n;a++) {
for(int b=a;a*a+b*b<=n;b++) {
for(int c=b;a*a+b*b+c*c<=n;c++) {
double d=Math.sqrt(n-a*a-b*b-c*c);
if(d%1==0) {System.out.println(a+" "+b+" "+c+" "+(int)d);return;}
}
}
}
}
static int[][] arr = new int[5000001][3];
public static void yxc2(int n) {//方法二 两次二层枚举
for(int c=0;c*c<=n;c++) {
for(int d=c;c*c+d*d<=n;d++) {
int temp=c*c+d*d;
if(arr[temp][0]==0) {
arr[temp][0]=1;
arr[temp][1]=c;
arr[temp][2]=d;
}
}
}
int num;
for(int a=0;a*a<=n;a++) {
for(int b=a;a*a+b*b<=n;b++) {
int temp=n-a*a-b*b;
if(arr[temp][0]==1) {
System.out.println(a+" "+b+" "+arr[temp][1]+" "+arr[temp][2]);
return;
}
}
}
}
}