威佐夫游戏

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1072

有2堆石子，A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。
假设A B都非常聪明，拿石子的过程中不会出现失误。给出2堆石子的数量，问最后谁能赢得比赛。

例如：2堆石子分别为3颗和5颗。那么不论A怎样拿，B都有对应的方法拿到最后1颗。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数分别是2堆石子的数量，中间用空格分隔。(1 <= N <= 2000000)

Output

共T行，如果A获胜输出A，如果B获胜输出B。

Input示例

3
3 5
3 4
1 9

Output示例

B
A
A

分析：

当 k = bk - ak，当 ak == [φ * k] 时，先手输。
黄金比例 φ = 1.618033（不知道为什么不能用，只能用 (Math.sqrt(5) + 1) / 2.0 代替）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int T = (int) in.nval;
		int[] a = new int[T];
		int[] b = new int[T];
		for (int i = 0; i < T; i++) {
			in.nextToken();
			a[i] = (int) in.nval;
			in.nextToken();
			b[i] = (int) in.nval;
		}

		for (int i = 0; i < T; i++) {
			if (a[i] > b[i]) {
				swap(a, b, i);
			}
			int k = b[i] - a[i];
			int t = (int) (k * (Math.sqrt(5) + 1) / 2.0);
			out.println(a[i] == t ? "B" : "A");
		}
		out.flush();
	}

	static void swap(int[] a, int[] b, int i) {
		int t = a[i];
		a[i] = b[i];
		b[i] = t;
	}
}

威佐夫游戏 V2

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1185

有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。
假设A B都非常聪明，拿石子的过程中不会出现失误。给出2堆石子的数量，问最后谁能赢得比赛。

例如：2堆石子分别为3颗和5颗。那么不论A怎样拿，B都有对应的方法拿到最后1颗。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数分别是2堆石子的数量，中间用空格分隔。(1 <= N <= 10^18)

Output

共T行，如果A获胜输出A，如果B获胜输出B。

Input示例

3
3 5
3 4
1 9

Output示例

B
A
A

分析：

输入数据变大，精度要求更高了，可以通过 windows 自带的计算机求出这个黄金比例。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigDecimal;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		BigDecimal g = new BigDecimal("1.6180339887498948482045868343656");

		int T = Integer.parseInt(in.readLine());
		long[] a = new long[T];
		long[] b = new long[T];
		for (int i = 0; i < T; i++) {
			String[] tmp = in.readLine().split(" ");
			a[i] = Long.parseLong(tmp[0]);
			b[i] = Long.parseLong(tmp[1]);
		}

		for (int i = 0; i < T; i++) {
			if (a[i] > b[i]) {
				swap(a, b, i);
			}

			long k = new BigDecimal(b[i] - a[i]).multiply(g).longValue();
			out.println(a[i] == k ? "B" : "A");
		}
		out.flush();
	}

	static void swap(long[] a, long[] b, int i) {
		long t = a[i];
		a[i] = b[i];
		b[i] = t;
	}
}