[highlight]Solution[/highlight]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
/* import java.math.BigInteger; import java.util.Scanner; public class Main {public static void main(String[] args) { Scanner scanf = new Scanner(System.in); int time; time = scanf.nextInt(); System.out.println(""); for(int i = 0; i<time; i++){ BigInteger input = scanf.nextBigInteger(); if(i > 0) System.out.println(""); BigInteger previous = input; BigInteger distance, post, Two = BigInteger.valueOf(2), Negative = BigInteger.valueOf(-1); if(input.equals(BigInteger.ZERO)){ System.out.println("0"); continue; } while(true){ post = input.divide(previous); post = post.add(previous); post = post.divide(Two); distance = post.subtract(previous); if(distance.equals(BigInteger.ONE)){ System.out.println(previous); break; } int d = distance.compareTo(BigInteger.ZERO); if(d < 0) distance = distance.multiply(Negative); else if(distance.equals(BigInteger.ZERO)){ System.out.println(post); break; } previous = post; } } } } */ import java.util.*; import java.math.*; import java.math.BigInteger; import java.util.Scanner; public class Main{ static boolean didWork ; public static BigInteger sqrt(BigInteger A) { BigInteger temp = A.shiftRight(BigInteger.valueOf(A.bitLength()).shiftRight(1).intValue()), result = null; while (true) { result = temp.add(A.divide(temp)).shiftRight(1); if (!temp.equals(result)) temp = result; else break ; } didWork = false ; if (result.multiply(result).equals(A)) didWork = true ; return result; } public static void main(String []args) { Scanner scanf = new Scanner(System.in); int t= scanf.nextInt(); for(int i=0;i<t;i++) { BigInteger input = scanf.nextBigInteger(); if(i!=0) { System.out.println(""); } System.out.println(sqrt(input)); } } }; |