【HDU-5973 Game of Taking Stones】
题意：标准的威佐夫博弈, 只不过数据范围特别大, 要使用高精度. 威佐夫博弈详情见
分析：只要根据威佐夫博弈的条件进行判断即可, 高精度需要计算sqrt(5), 这里使用二分求解.
import java.math.BigDecimal;
import java.util.Scanner;public class Main {public static BigDecimal getGoldNumber (){BigDecimal eps = new BigDecimal("0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001");BigDecimal l = BigDecimal.valueOf(2);BigDecimal r = BigDecimal.valueOf(3);BigDecimal mid, pre = BigDecimal.valueOf(5);//get sqrt(5.0)while (l.multiply(l).subtract(pre).abs().compareTo(eps) > 0) {mid = l.add(r).divide(BigDecimal.valueOf(2));if (mid.multiply(mid).compareTo(pre) < 0) l = mid;else r = mid;}BigDecimal b = BigDecimal.ONE.add(l).divide(BigDecimal.valueOf(2));return b;}public static String toInt(String s) {String ans = "";for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '.') break;else {ans += s.charAt(i);}}return ans;}public static void main (String args[]) {Scanner sc = new Scanner(System.in);BigDecimal a, b;BigDecimal bt = getGoldNumber();while (sc.hasNext()){a = sc.nextBigDecimal();b = sc.nextBigDecimal();if (a.compareTo(b) > 0) {BigDecimal c;c = a;a = b;b = c;}String p = toInt(bt.multiply(b.subtract(a)).toString());String q = toInt(a.toString());if (p.compareTo(q) == 0) System.out.println("0");else System.out.println("1");}sc.close();}
}