51Nod-1185-威佐夫遊戲 V2

1185 威佐夫遊戲 V2

有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
           

解題方法

Wythoff Game是三個常見的博弈遊戲。Wythoff Game需要用到黃金分割解答。

詳細地威佐夫博弈算法分析看這兩個部落格——三個博弈論算法分析

與威佐夫遊戲

簡單言之，當兩堆物品數量之差乘以黃金分割率恰好等于兩堆物品中最小的那堆數量時，第二個玩家勝利，否則第一個玩家勝利。

但是，由于該題的資料過大，乘過長的小數會出現精度問題，故而需要把黃金分割比值的小數部分0.618033988749894848204586834… 拆成整數放進清單裡，然後進行乘法模拟運算，以減少精度的損失。

解題代碼

cnt = (, , )
MOD = 
T = int(input())

for i in range(T):
    n, m = list(map(int, input().split()))
    if n > m:
        n, m = m, n
    dist = m - n
    pre = dist//MOD
    last = dist % MOD

    #對于x,y,z，隻有模MOD後的數，即餘數是不需要變動的位數，其他的用于進位用。
    #這一段是模拟乘法
    x = last*cnt[]
    y = pre*cnt[] + last*cnt[] + x//MOD
    z = pre*cnt[] + last*cnt[] + y//MOD
    ans = dist+pre*cnt[0] + z//MOD
    print('A' if ans != n else 'B')