题解 | #最少的完全平方数#
最少的完全平方数
https://www.nowcoder.com/practice/4b2f5d4c00f44a92845bdad633965c04
借鉴左神的思路：
采用方法一：
根据四平方和定理：
1.一个数最多可以被4个平方和累加得到。
2.任何数消掉4的因子结论不变。
3.如果一个数模8等于7，则这个数一定被4个平方数累加得到
import java.util.*;
public class Main{
//四平方和定理
//任何数消掉4的因子结论不变
public static int process(int n){
while(n%4==0){
n/=4;
}
if(n%8==7)
return 4;
for(int i=0;i*i<=n;i++){
int b=(int)Math.sqrt(n-i*i);
if(i*i+b*b==n)
return ( i>0 && b>0 )?2:1;
}
return 3;
}
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.print(process(n));
}
}
paypal工作强度 6人发布