在焦作站的acm网络赛中遇到了一个高精度开根的水题……但是那时候WA了
后面学写java补题还T了orz
所以写一篇文章来记录一下java的大整数类型的基础和开根还有一点心得体会吧
首先给那一题的题面和模板
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 ii candies in the 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 * Royale. Otherwise they will choose League of Legends.
Now tell you the value of NN, please judge which game they will choose.
Input
The first line contains an integer T(1 \le T \le 800)T(1≤T≤800) , which is the number of test cases.
Each test case contains one line with a single integer: N(1 \le N \le 10^{200})N(1≤N≤10200) .
Output
For each test case, output one line containing the answer.
传送门：https://nanti.jisuanke.com/t/31719
样例输入复制
- 4
- 1
- 2
- 3
- 4
样例输出复制
- Arena of Valor
- * Royale
- League of Legends
- Hearth Stone
题目来源
1 import java.math.BigInteger;
2 import java.util.Scanner;
3 import java.util.TreeSet;
4
5 public class Main
6 {
7
8 static BigInteger n,mod;
9 public static BigInteger Sqrt(BigInteger c)
10 {
11 if(c.compareTo(BigInteger.ONE)<=0)//0返回0 1返回1
12 return c;
13
14 BigInteger temp=null,x;
15 x=c.shiftRight((c.bitLength()+1)/2);//初始猜值为二进制右移至位数只剩一半
16 while(true)//以下为牛顿迭代法
17 {
18 temp=x;
19 x=x.add(c.divide(x)).shiftRight(1);
20 if(temp.equals(x)||x.add(BigInteger.ONE).equals(temp))//两次迭代相等或只差一
21 break;
22 }
23 return x;
24 }
25 public static boolean judge(BigInteger c)
26 {
27 BigInteger x=Sqrt(c);
28 if(x.multiply(x).equals(c))//平方回去是否还是本身
29 return true;
30 else
31 return false;
32 }
33 public static void main(String[] args)
34 {
35 Scanner sc=new Scanner(System.in);
36 int t=sc.nextInt();
37 while(t>0)
38 {
39 t--;
40 n=sc.nextBigInteger();
41 boolean x,y;
42 x=judge(n);
43 y=judge(n.multiply(n.subtract(BigInteger.ONE)).shiftRight(1));
44 if(x&&y)
45 System.out.println("Arena of Valor");
46 else if(!x&&y)
47 {
48 System.out.println("* Royale");
49 }
50 else if(x&&!y)
51 {
52 System.out.println("Hearth Stone");
53 }
54 else
55 {
56 System.out.println("League of Legends");
57 }
58 }
59 }
60 }
这个还是比较好理解的，但是在自己用同样思路写的时候就T了。有几个细节可以优化：
- 除二（divide(two)） 用算术右移shiftRight(1) 可以快很多很多
- 还有就是通过数学方法 这题里面有个n*（n-1）/2 是可以简化的
然后还有就是一些别人的判定方法
1 public static boolean check(BigInteger now){
2 if (now.compareTo(BigInteger.ZERO) == 0 || now.compareTo(BigInteger.ONE) == 0) return true;//同样的特判0，1，2，3
3 if (now.mod(BigInteger.valueOf(3)).compareTo(BigInteger.valueOf(2)) == 0) return false;
4
5
6 String s = now.toString();
7 if(s.length()%2==0) s = s.substring(0,s.length()/2+1);
8 else s = s.substring(0,(1+s.length())/2);//也是拆成一半
9
10 BigInteger res = BigInteger.ZERO;
11 BigInteger m = new BigInteger(s);
12 BigInteger two = new BigInteger("2");
13 if(s == "1") res = BigInteger.ONE;
14 else{
15 while(now.compareTo(m.multiply(m)) < 0){
16 m = (m.add(now.divide(m))).divide(two);
17 }
18 res = m;
19 }
20
21 if (res.multiply(res).compareTo(now) == 0) return true;
22 return false;
23 }
从这个可以看出 牛顿迭代法的起始非常重要。
还有最后一点点。。这题可以通过数学方法简化（n-1）*n/2的规模，同样可以不T噢~
最后再存一点点java高精度常用的东西吧
import java.util.*;
import java.io.*;
import java.math.*; import java.math.*; public class Main { public static BigInteger sqrt2(BigInteger x) {
BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
BigInteger div2 = div;
// Loop until we hit the same value twice in a row, or wind
// up alternating.
for(;;) {
BigInteger y = div.add(x.divide(div)).shiftRight(1);
if (y.equals(div) || y.equals(div2))
return y;
div2 = div;
div = y;
}
}
public static void main(String []args) { Scanner sc=new Scanner(System.in);
BigInteger a=sc.nextBigInteger();
BigInteger b=sc.nextBigInteger();
int n=sc.nextInt();
BigInteger c=BigInteger.ONE;
BigDecimal d=sc.nextBigDecimal();
BigInteger e=sc.nextBigInteger();
String str=sc.nextLine(); /*
//d为int型，a,b,c都为大数
c=a.add(b); // 相加
c=a.subtract(b); // 相减
c=a.multiply(b); // 相乘
c=a.divide(b); // 相除取整 用shiftRight(1)快很多
c=a.gcd(b); // 最大公约数
c=a.remainder(b); // 取余
c=a.mod(b); // a mod b
c=a.abs(); // a的绝对值
c=a.negate(); // a的相反数
c=a.pow(d); // a的b次幂 d为int型
c=a.max(b); // 取a，b中较大的
c=a.min(b); // 取a，b中较小的
d=a.compareTo(b); // 比较a与b的大小 d=-1小于 d=0等于 d=1大于 d为int型
a.equals(b); // 判断a与b是否相等 相等返回true 不相等返回false
*/ //加减乘除add,subtract,multiply,divide
System.out.println(a.add(b));
System.out.println(a.subtract(b));
System.out.println(a.multiply(b));
System.out.println(a.divide(b)); //阶乘
//注意BigInteger.valueOf()的使用
for(int i=1;i<=n;i++) {
c=c.multiply(BigInteger.valueOf(i));
}
System.out.println(c);
//比较大小
int flag=a.compareTo(b);
if(flag==-1) {
System.out.println("a<b");
} else if(flag==0) {
System.out.println("a=b");
} else {
System.out.println("a>b");
}
//高精度幂
//stripTrailingZeros():返回数值上等于此小数，但从该表示形式移除所有尾部0的BigDecimal
//toPlainString():将BigDecimal转换为字符串
//stratswith("c"):判断该字符串是不是以字符c开头的
//substring(st,en):返回该字符串减去下标在[st,en)的字符串
String res=d.pow(n).stripTrailingZeros().toPlainString();
if(res.startsWith("0")) {
res=res.substring(0,1);
}
System.out.println(res);
//大数的进制转换
//先将字符串转化为10进制大数，然后将大数转化为2进制字符串
e=new BigInteger(str,10);
String tmp=e.toString(2);
/*
d=a.intValue(); // 将大数a转换为 int 类型赋值给 d
e=a.longValue(); // 将大数a转换为 long 类型赋值给 e
f=a.floatValue(); // 将大数a转换为 float 类型赋值给 f
g=a.doubleValue(); // 将大数a转换为 double 类型赋值给 g
s=a.toString(); // 将大数a转换为 String 类型赋值给 s
a=BigInteger.valueOf(e); // 将 e 以大数形式赋值给大数 a e只能为long或int
*/
sc.close();
}
}
谢谢ACM贴吧交流群和bin巨的ACM交流群的巨巨们指导啦~
还有就是 CSDN上和*的博主们啦