結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー keigo kuwata
提出日時 2025-04-20 17:34:50
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 994 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2025-04-20 17:34:55
合計ジャッジ時間 4,478 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other AC * 31 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

def gcd(a, b):
    """ユークリッドの互除法による最大公約数の計算"""
    while b:
        a, b = b, a % b
    return a

def solve_game_efficient(a, b):
    """最も効率的なゲーム勝者決定関数"""
    g = gcd(a, b)
    
    # 最大公約数が1より大きい場合
    if g > 1:
        return "Alice" if a > b else "Bob"
    
    # 互いに素の場合
    a, b = min(a, b), max(a, b)  # a < bとなるように並べ替え
    
    # 偶数ステップで終わるかどうかを判定
    count = 0
    while a > 0:
        b %= a
        count += 1
        if b == 0:
            return "Bob" if count % 2 == 1 else "Alice"
        a, b = b, a
    
    # ここには到達しないはず
    return "Unknown"

def main():
    # 入力を受け取る
    a, b = map(int, input().split())
    
    # 勝者を決定（最効率版）
    winner = solve_game_efficient(a, b)
    
    # 結果を出力
    print(winner)

if __name__ == "__main__":
    main()
0