Square root

The Problem

You are to determinate X by given Y, from expression

The Input

The first line is the number of test cases, followed by a blank line.

Each test case of the input contains a positive integer Y (1<=Y<=10¹⁰⁰⁰), with no blanks or leading zeroes in it.
It is guaranteed, that for given Y, X will be always an integer.

Each test case will be separated by a single line.

The Output

For each test case, your program should print X in the same format as Y was given in input.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

1 7206604678144 

Sample Output

2684512

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
 public static void main(String[] args) {
 Scanner keyboard = new Scanner(System.in);
 String x;
 BigInteger l, r, m, n;
 int t = keyboard.nextInt();
 while(t != 0) {
 t--;
 x = keyboard.next();
 n = new BigInteger(x);
 l = BigInteger.valueOf(1);
 r = BigInteger.valueOf(10).pow(x.length()/2+1);
 m = BigInteger.valueOf(0);
 while(l.compareTo(r) <= 0) {
 m = l.add(r).shiftRight(1);
 if(m.multiply(m).compareTo(n) == 1) {
 r = m.subtract(BigInteger.valueOf(1));
 } else if(m.multiply(m).compareTo(n) == -1) {
 l = m.add(BigInteger.valueOf(1));
 } else
 break;
 }
 if(m.multiply(m).compareTo(n) > 0)
 m = l.subtract(BigInteger.valueOf(1));
 System.out.println(m.toString());
 if(t != 0)
 System.out.println("");
 }
 }
}
 

您可能以下文章有趣

[UVA][另MST] 11747 - Heavy Cycle Edges

[UVA] 394 - Mapmaker

[UVA][ST] 12532 - Interval Product

[UVA][map&set混用] 11239 - Open Source