問題一覧 > 通常問題

No.2725 Coprime Game 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : MasKoaTSMasKoaTS / テスター : 👑 p-adicp-adic 👑 ygussanyygussany
6 ProblemId : 9085 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-30 18:12:47

問題文

22 以上の整数 NN が与えられます。

y=Ny = N で初期化された変数 yy があり、コアさんパチェさんはこれを用いてゲームを行います。
コアさんから始めて、次の操作を交互に行います。

  • 22 以上 yy 以下の整数 xx のうち、次の条件をすべて満たすものを 11 つ選び、その後 y=xy = x とする。

    • xxNN の約数でない

    • xxyy は互いに素である

両者のうち、先に操作を行えなくなった方の負けとします。

両者が最善を尽くしたとき、どちらが勝つか判定してください。

TT 個のテストケースについて答えを求めてください。

制約

  • 1T1051 \leq T \leq 10^{5}

  • 2N10182 \leq N \leq 10^{18}

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

TT
case1\mathrm{case}_{1}
case2\mathrm{case}_{2}
  \vdots
caseT\mathrm{case}_{T}

各テストケースは次の形式で与えられます。

NN

出力

答えを 11 行ずつ合計 TT 行に出力してください。

ii (1iT)(1 \leq i \leq T) 行目には、ii 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K を、パチェさんが勝つならば P を出力してください。

サンプル

サンプル1
入力
5
3
18
2023
2
1000000000000000000
出力
K
P
K
P
K

まず、11 つ目のテストケースではコアさんが必勝です。例えば、次のように操作を行います。

  1. 22y=32 \leq 2 \leq y = 3 かつ 2233 は互いに素かつ 2233 の約数でないので、
    コアさんx=2x = 2 を選び、その後 y=2y = 2 とする。

  2. パチェさんが選べる整数 xx は存在しないので、コアさんの勝ちとなる。

続いて、22 つ目のテストケースではパチェさんが必勝です。例えば、次のように操作を行います。

  1. 211y=182 \leq 11 \leq y = 18 かつ 11111818 は互いに素かつ 11111818 の約数でないので、
    コアさんx=11x = 11 を選び、その後 y=11y = 11 とする。

  2. 24y=112 \leq 4 \leq y = 11 かつ 441111 は互いに素かつ 441818 の約数でないので、
    パチェさんx=4x = 4 を選び、その後 y=4y = 4 とする。

  3. コアさんが選べる整数 xx は存在しないので、パチェさんの勝ちとなる。

残りのテストケースについても同様に答えを求めると、上の出力例のようになります。

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