No.2725 Coprime Game 2
タグ : / 解いたユーザー数 59
作問者 :
MasKoaTS
/ テスター :
👑 
p-adic
👑 
ygussany
問題文
$2$ 以上の整数 $N$ が与えられます。
$y = N$ で初期化された変数 $y$ があり、コアさんとパチェさんはこれを用いてゲームを行います。
コアさんから始めて、次の操作を交互に行います。
$2$ 以上 $y$ 以下の整数 $x$ のうち、次の条件をすべて満たすものを $1$ つ選び、その後 $y = x$ とする。
$x$ は $N$ の約数でない
$x$ と $y$ は互いに素である
両者のうち、先に操作を行えなくなった方の負けとします。
両者が最善を尽くしたとき、どちらが勝つか判定してください。
$T$ 個のテストケースについて答えを求めてください。
制約
$1 \leq T \leq 10^{5}$
$2 \leq N \leq 10^{18}$
入力はすべて整数
入力
入力は次の形式で与えられます。
$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$
各テストケースは次の形式で与えられます。
$N$
出力
答えを $1$ 行ずつ合計 $T$ 行に出力してください。
$i$ $(1 \leq i \leq T)$ 行目には、$i$ 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K を、パチェさんが勝つならば P を出力してください。
サンプル
サンプル1
入力
5 3 18 2023 2 1000000000000000000
出力
K P K P K
まず、$1$ つ目のテストケースではコアさんが必勝です。例えば、次のように操作を行います。
$2 \leq 2 \leq y = 3$ かつ $2$ と $3$ は互いに素かつ $2$ は $3$ の約数でないので、
コアさんは $x = 2$ を選び、その後 $y = 2$ とする。パチェさんが選べる整数 $x$ は存在しないので、コアさんの勝ちとなる。
続いて、$2$ つ目のテストケースではパチェさんが必勝です。例えば、次のように操作を行います。
$2 \leq 11 \leq y = 18$ かつ $11$ と $18$ は互いに素かつ $11$ は $18$ の約数でないので、
コアさんは $x = 11$ を選び、その後 $y = 11$ とする。$2 \leq 4 \leq y = 11$ かつ $4$ と $11$ は互いに素かつ $4$ は $18$ の約数でないので、
パチェさんは $x = 4$ を選び、その後 $y = 4$ とする。コアさんが選べる整数 $x$ は存在しないので、パチェさんの勝ちとなる。
残りのテストケースについても同様に答えを求めると、上の出力例のようになります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。