Day 161-Q1 — 2026-09-26 — Wythoff のゲーム（負け局面 $(\lfloor k\varphi\rfloor,\lfloor k\varphi^2\rfloor)$ を整数だけで判定し、勝ち手の数を数える）

📋 コピーimport sys
from math import isqrt


def a_of(k):
    """下 Wythoff 数 floor(k*phi)。isqrt は整数平方根なので誤差が出ない。"""
    return (k + isqrt(5 * k * k)) // 2


def partner(x):
    """x を含む負け局面 (a_k, b_k) の相方。x = 0 なら 0。"""
    if x == 0:
        return 0
    k = (isqrt(5 * x * x) - x) // 2          # x = a_k なら k ≈ x/phi
    for kk in (k - 1, k, k + 1, k + 2):
        if kk >= 1 and a_of(kk) == x:
            return x + kk                     # b_k = a_k + k
    k = (3 * x - isqrt(5 * x * x)) // 2      # x = b_k なら k ≈ x/phi^2
    for kk in (k - 1, k, k + 1, k + 2):
        if kk >= 1 and a_of(kk) + kk == x:
            return x - kk
    raise AssertionError(x)                   # Beatty の定理によりここには来ない


def winning_moves(a, b):
    if a > b:
        a, b = b, a
    d = b - a
    ad = a_of(d)
    if ad == a:
        return 0                              # 負け局面
    # 勝ち手は 3 種類で、種類ごとに行き先は 1 つ。a == b のときは山を区別して数える
    c = 0
    if partner(a) < b:
        c += 1                                # 大きい山を partner(a) に
    if partner(b) < a:
        c += 1                                # 小さい山を partner(b) に
    if ad < a:
        c += 1                                # 両方から a - ad 個ずつ
    return c


def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    out = []
    for i in range(q):
        a = int(data[1 + 2 * i])
        b = int(data[2 + 2 * i])
        out.append(str(winning_moves(a, b)))
    print("\n".join(out))


main()