ACM-ICPC2018焦作网络赛 Participate in E-sports（大数开方）

Participate in E-sports

11.44%
1000ms
65536K

Jessie and Justin want to participate in e-sports. E-sports contain many games, but they don't know which one to choose, so they use a way to make decisions.

They have several boxes of candies, and there are $i^{th}ith box, each candy is wrapped in a piece of candy paper. Jessie opens the candy boxes in turn from the first box. Every time a box is opened, Jessie will take out all the candies inside, finish it, and hand all the candy papers to Justin.$

When Jessie takes out the candies in the $N^{th}Nth box and hasn't eaten yet, if the amount of candies in Jessie's hand and the amount of candy papers in Justin's hand are both perfect square numbers, they will choose Arena of Valor. If only the amount of candies in Jessie's hand is a perfect square number, they will choose Hearth Stone. If only the amount of candy papers in Justin's hand is a perfect square number, they will choose Clash Royale. Otherwise they will choose League of Legends.$

Now tell you the value of

Input

The first line contains an integer

Each test case contains one line with a single integer: $10^{200})N(1≤N≤10200) .$

Output

For each test case, output one line containing the answer.

样例输入

样例输出

Arena of Valor
Clash Royale
League of Legends
Hearth Stone

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

听说牛顿迭代法也能过，这里粘个板子：https://blog.csdn.net/f_zyj/article/details/77852787

public static BigInteger sqrt(String x) {
        int mlen = x.length();    //被开方数的长度
        int len;    //开方后的长度
        BigInteger beSqrtNum = new BigInteger(x);//被开方数
        BigInteger sqrtOfNum;    //存储开方后的数
        BigInteger sqrtOfNumMul;    //开方数的平方
        String sString;//存储sArray转化后的字符串
        if(mlen%2 == 0)    len = mlen/2;
        else    len = mlen/2+1;
        char[] sArray = new char[len];
        Arrays.fill(sArray, '0');//开方数初始化为0
        for(int pos=0; pos<len; pos++){
         //从最高开始遍历数组，每一位都转化为开方数平方后刚好不大于被开方数的程度
            for(char num='1'; num<='9'; num++){
                sArray[pos] = num;
                sString = String.valueOf(sArray);
                sqrtOfNum = new BigInteger(sString);
                sqrtOfNumMul = sqrtOfNum.multiply(sqrtOfNum);
                if(sqrtOfNumMul.compareTo(beSqrtNum) == 1){
                    sArray[pos]-=1;
                    break;    
                }    
            }
        }
        return new BigInteger(String.valueOf(sArray));
}

大数开方模板

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

class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int T = cin.nextInt();
        for (int cas = 1; cas <= T; ++cas) {
            String str = cin.next();
            BigInteger n = new BigInteger(str);
            BigInteger m = n.multiply(n.subtract(BigInteger.ONE)).shiftRight(1);
            //System.out.println(n);
            //System.out.println(m);
            boolean nIsSquare = isSquare(n);
            boolean mIsSquare = isSquare(m);
            if (nIsSquare && mIsSquare) {
                System.out.println("Arena of Valor");
            } else if (nIsSquare && !mIsSquare) {
                System.out.println("Hearth Stone");
            } else if (!nIsSquare && mIsSquare) {
                System.out.println("Clash Royale");
            } else {
                System.out.println("League of Legends");
            }
        }
    }
    
    public static boolean isSquare(BigInteger n) {
        BigInteger low = BigInteger.ZERO;
        BigInteger high = n;
        while (low.compareTo(high) <= 0) {
            BigInteger mid = low.add(high).shiftRight(1);
            BigInteger square = mid.multiply(mid);
            int result = square.compareTo(n);
            if (result == 0) {
                return true;
            } else if (result > 0) {
                high = mid.subtract(BigInteger.ONE);
            } else {
                low = mid.add(BigInteger.ONE);
            }
        }
        return false;
    }
}