問題一覧 > 通常問題

No.1579 New Type of Nim

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 111
作問者 : magstamagsta / テスター : startcppstartcpp
5 ProblemId : 6208 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-03 00:23:31

問題文

P 君と Q 君で石取りゲームをします。最初は山が 2 つあり、1 つ目の山には $A$ 個の石が、2 つ目の山には $B$ 個の石があります。

P 君と Q 君は、石が残っている山が存在する限り以下の操作を繰り返します。最初、操作する人は P 君です。操作した後、2 つの山にある石の数が同じでなければ、操作する人を交代します。

  • 石が残っている山を 1 つを選び、好きな数だけ (1 個以上) その山にある石を取り除く。

2 つの山どちらにも石が存在しなくなったとき、最後に石を取った人が勝ちです。両者最善を尽くしたとき、どちらの人が勝つか判定してください。

P 君が勝つなら P を、Q 君が勝つなら Q を出力してください。

入力

$A\ \ B$

  • $1 \leq A, B \leq 10^9$
  • 入力はすべて整数である

出力

PQ を出力し、最後に改行せよ。

サンプル

サンプル1
入力
1 2
出力
Q

P 君が 1 つ目の山を選んだ場合、石が 2 つある山が 1 つ残ることになり、Q 君は 2 つの石を取れば勝つことができます。

P 君が 2 つ目の山を選んで石を 2 つ取った場合、石が 1 つある山が 1 つ残ることになり、Q 君は 1 つの石を取れば勝つことができます。

P 君が 2 つ目の山を選んで石を 1 つ取った場合、石が 1 つある山が 2 つ残ることになり、操作する人は交代せず操作する人は P 君のままです。
これから P 君がいかなる操作をしても、石が 1 つある山が 1 つ残ることになり、Q 君は 1 つの石を取れば勝つことができます。

よって、P 君が最初からどのように操作しても Q 君は勝つことができます。

サンプル2
入力
4 3
出力
Q

サンプル3
入力
12398742 83717408
出力
P

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