SGU 111 Very simple problem(大数開方)
意味は、1つの大きい整数(範囲10^1000)を与えて、2次方がこの数の最大数より大きくないことを求めます
最初はCの高精度と筆算の処方を使っていましたが、一日中結果が出なかったので、私の類は行きましょう・・・
仕方なくjavaのコードを探して、先に息を吐いて......
考え方は簡単で、1~10^500、区間二分から平方を求めて目標数と比較します.
初めてjavaを書きます・・・
原題リンク:http://acm.sgu.ru/problem.php?contest=0&problem=111
コード:
最初はCの高精度と筆算の処方を使っていましたが、一日中結果が出なかったので、私の類は行きましょう・・・
仕方なくjavaのコードを探して、先に息を吐いて......
考え方は簡単で、1~10^500、区間二分から平方を求めて目標数と比較します.
初めてjavaを書きます・・・
原題リンク:http://acm.sgu.ru/problem.php?contest=0&problem=111
コード:
import java.io.*;
import java.math.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
BigInteger r = new BigInteger("10");
BigInteger l = new BigInteger("1");
BigInteger one = new BigInteger("1");
int tmp,cmp;
BigInteger x,mid,ans;
r = r.pow(500);
Scanner cin = new Scanner(new BufferedInputStream(System.in));
x = cin.nextBigInteger();
ans = new BigInteger("-1");
cmp = l.compareTo(r);
while(cmp<=0){
mid = (l.add(r)).shiftRight(1);
tmp = (mid.pow(2)).compareTo(x);
if(tmp<=0){
ans=mid;
l=mid.add(one);
}
else r=mid.subtract(one);
cmp = l.compareTo(r);
}
System.out.println(ans);
}
}