【hdu5973】高精度威佐夫博弈

题意：输入a, b表示两堆石头数目，威佐夫博弈，问：先手胜负？

a, b <= 1e100.

高精度。当a > b时， a = (a-b)*黄金分割比时是先手败状态。因为a, b <= 1e100，所以黄金分割比至少要保留小数点后100位。

BigDecimal没有开方操作，所以二分算出黄金分割比。

 1 import java.util.*;
 2 import java.io.BufferedInputStream;
 3 import java.math.*;
 4 public class Main {
 5     public static void main(String[] args){
 6         Scanner cin = new Scanner(new BufferedInputStream(System.in)); 
 7         BigDecimal L = new BigDecimal(1.6180339887), R = new BigDecimal(1.6180339888);
 8         BigDecimal eps = new BigDecimal(0.1).pow(101);
 9         while( R.subtract(L).subtract(eps).compareTo(BigDecimal.ZERO) > 0){
10             BigDecimal M = L.add(R).divide(BigDecimal.valueOf(2));
11             BigDecimal ret = M.multiply(BigDecimal.valueOf(2)).subtract(BigDecimal.ONE).pow(2);
12             if(ret.compareTo(BigDecimal.valueOf(5)) > 0)
13                 R = M;
14             else 
15                 L = M;
16         }
17         BigDecimal t = L;//黄金分割数精确到1e-100
18         while(cin.hasNext()){
19             BigInteger a = cin.nextBigInteger(), b = cin.nextBigInteger();
20             int com = a.compareTo(b), ccom = 0;
21             if(com == 0){
22                 ccom = a.compareTo(BigInteger.ZERO);
23                 if(ccom == 0)
24                     System.out.println(0);
25                 else 
26                     System.out.println(1);
27                 continue ;
28             }
29             if(com == -1){
30                 BigInteger c = a;
31                 a = b;
32                 b = c;
33             }
34             BigInteger k = a.subtract(b);
35             BigDecimal kk = new BigDecimal(k).multiply(t).setScale(0,  BigDecimal.ROUND_DOWN);
36             k = kk.toBigInteger();
37             ccom = k.compareTo(b);
38             if(ccom == 0)
39                 System.out.println(0);
40             else 
41                 System.out.println(1);
42         }
43     }
44 }