解法一:直接遍历找平方根
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
/**
* 1≤n,m≤10^1000
* 注意此题范围值超级大,远远超过long的范围
* int 2^31 - 1 ~ 10^9
* long 2^63 - 1 ~ 10^19
* @author abc
*
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String n = scan.next();//String类可以动态扩展,它可以存储非常大的数字
String m = scan.next();
System.out.println(sqrt(n).multiply(sqrt(m)));//如果是int或者long类型可以直接调用Math.sqrt;但10的1000次方太大了,不能直接使用
//在此输入您的代码...
scan.close();
}
private static BigInteger sqrt(String n) {
// TODO Auto-generated method stub
int length = n.length();//首先判断长度是奇数还偶数,100的平方根为10,1000的平方根为100
int len = 0;//由此可知,当长度为奇数是,平方根之后,长度为原来的一半再加1,偶数时为原来的一般
if(length % 2 == 0) len = length / 2;
else len = length / 2 + 1;
char[] s = new char[len];//确定平方根后结果的位数,开始寻找最接近其值的数
Arrays.fill(s, '0');
BigInteger target = new BigInteger(n);
for(int i = 0;i < len;i++) {//可以采用二分来寻找,也可以从第一位遍历来找
for(char c = '1';c <= '9';c++) {
s[i] = c;
BigInteger val = new BigInteger(String.valueOf(s)).pow(2);//平方
/**
* 如果调用 compareTo() 方法的 BigInteger 对象大于参数对象,则返回值为正数;如果小于参数对象,则返回值为负数;如果两者相等,则返回值为0。
*/
if(val.compareTo(target) > 0 ) {//val大于target
s[i]-= 1;
break;
}
}
}
return new BigInteger(String.valueOf(s));
}
}
解法二:二分找平方根
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
/**
* 1≤n,m≤10^1000
* 注意此题范围值超级大,远远超过long的范围
* int 2^31 - 1 ~ 10^9
* long 2^63 - 1 ~ 10^19
* @author abc
*
*/
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String n = scan.next();//String类可以动态扩展,它可以存储非常大的数字
String m = scan.next();
System.out.println(sqrt(n).multiply(sqrt(m)));//如果是int或者long类型可以直接调用Math.sqrt;但10的1000次方太大了,不能直接使用
//在此输入您的代码...
scan.close();
}
private static BigInteger sqrt(String n) {
//确定左边界
BigInteger l = new BigInteger("0");
int length = n.length();//首先判断长度是奇数还偶数,100的平方根为10,1000的平方根为100
int len = 0;//由此可知,当长度为奇数是,平方根之后,长度为原来的一半再加1,偶数时为原来的一般
if(length % 2 == 0) len = length / 2;
else len = length / 2 + 1;//假如len = 3;
char[] s = new char[len + 1];//确定平方根后结果的位数,开始寻找最接近其值的数1~999寻找
s[0] = '1';
for(int i = 1;i < s.length;i++) s[i] = '0';//s[i] = 1000;
//确定右边界
BigInteger r = new BigInteger(String.valueOf(s)).add(new BigInteger("-1"));//r = 999
BigInteger target = new BigInteger(n);
//System.exit(0);
while(l.compareTo(r) < 0) {
BigInteger mid = l.add(r).add(new BigInteger("1")).divide(new BigInteger("2"));//mid = l + r + 1 >> 1;
BigInteger res = mid.multiply(mid);//算出mid的平方//a[mid]
if(res.compareTo(target) <= 0) {//a[mid] <= target
l = mid;
}else{
r = mid.subtract(new BigInteger("1"));//r = mid - 1;
}
}
return l;
}
}