BOJ - 4342 - 유클리드 게임

import sys

def GCD(A, B):
    if A > B: A, B = B, A
    if B % A == 0: return True
    if (B - A) < A: return not GCD(B - A, A)
    return True

def solution():
    while True:
        A, B = map(int, sys.stdin.readline().split())
        if A == B == 0: return

        print("A wins" if GCD(A, B) else "B wins")

solution()

https://www.acmicpc.net/problem/4342