問題一覧 > 通常問題

No.3112 Decrement or Mod Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 130
作問者 : Naru820 / テスター : kenken714 ponjuice Nzt3
3 ProblemId : 12114 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-16 00:53:56

問題文

AliceとBobの二人はそれぞれ正の整数 $A,B$ を持っています。二人がこの数でゲームをします。

二人はAliceを先行として、どちらかの持つ数が0になるまで交互に以下のどちらかの操作を行います。

  • 自分の持つ数を1減らす。
  • 自分の持つ数を相手の持つ数で割ったあまりに置き換える。この操作は、相手の持つ数が自分の持つ数以下の時のみ行える。

先に自分の持つ数が0になった方が勝ちです。二人が最適な行動をするとき、どちらが勝ちますか？

なお、このゲームは必ず決着がつくことが証明できます。

制約

  • $1 \leq A,B \leq 10^{18}$

入力

入力は以下の形式で標準入力から与えられる。

$A$ $B$

出力

1行に、勝者の名前(AliceまたはBob)を出力してください。

サンプル

サンプル1
入力
5 3
出力
Alice

ゲームの進行の1例を示します。

  • Aliceは自分の持つ数を相手の持つ数で割ったあまりに置き換える操作を行う。 $A$ は $2$ となる。
  • Bobは自分の持つ数を1減らす操作を行う。$B$ は $2$ となる。
  • Aliceは自分の持つ数を相手の持つ数で割ったあまりに置き換える操作を行う。 $A$ は $0$ となる。Aliceを勝者として、ゲームを終わる。

これは両者が最適な行動をしているとは限りませんが、両者が最適に行動した場合でも、Aliceが勝者になることが証明できます。

サンプル2
入力
2 9
出力
Bob
サンプル3
入力
271828459045235602 314159265358979323
出力
Bob

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。