Game of Taking Stones HDU - 5973

题目大意

给你两堆石子，分别有\(x\),\(y\)个，可以同时在两堆里取相同个数，也可以只在一堆里取不小于\(1\)个的石子。

\(x,y<10^{100}\)

解

首先，不考虑数据范围，这是个经典的威佐夫博弈，先手输只需满足如下式子即可：

\[(y-x)\times \dfrac{1+\sqrt{5}}{2}=x ,x<y \]

于是，不考虑数据范围的话，\(c++\)如下所示：

    ll a, b;
    while (cin >> a >> b) {
        if (a > b) 
            swap(a, b);
        ll temp = b - a;
        ll ans = temp * (1.0 + sqrt(5.0)) / 2.0;
        if (ans == a)
            printf("0\n");
        else
            printf("1\n");
    }

考虑数据范围，需要\(Java\)高精度。需要小数点至少后\(100\)位。所以我们需要高精度开方。普通的Math.sqrt()是不行的。

\(Java\)高精度开方板子如下：

    private static BigDecimal sqrt(BigDecimal x, int n) {
        BigDecimal ans = BigDecimal.ZERO;
        BigDecimal eps = BigDecimal.ONE;
        for (int i = 0; i < n; ++i) {
            while (ans.pow(2).compareTo(x) < 0) {
                ans = ans.add(eps);
            }
            ans = ans.subtract(eps);
            eps = eps.divide(BigDecimal.TEN);
        }
        return ans;
    }

于是代码就是：

import java.io.BufferedInputStream;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        while(cin.hasNext()){
            BigInteger a = cin.nextBigInteger();
            BigInteger b = cin.nextBigInteger();
            if(a.compareTo(b) > 0){
                BigInteger t = a;
                a = b;
                b = t;
            }
            BigDecimal tmp=new BigDecimal(b.subtract(a));
            BigDecimal y=sqrt(new BigDecimal(5.0),150);
            y=y.add(BigDecimal.valueOf(1.0)).divide(BigDecimal.valueOf(2.0));
            tmp=tmp.multiply(y);
            BigInteger x=tmp.toBigInteger();
            if(x.equals(a))
                System.out.println("0");
            else
                System.out.println("1");
        }
    }
    private static BigDecimal sqrt(BigDecimal x, int n) {
        BigDecimal ans = BigDecimal.ZERO;
        BigDecimal eps = BigDecimal.ONE;
        for (int i = 0; i < n; ++i) {
            while (ans.pow(2).compareTo(x) < 0) 
                ans = ans.add(eps);
            ans = ans.subtract(eps);
            eps = eps.divide(BigDecimal.TEN);
        }
        return ans;
    }
}