No.2724 Coprime Game 1
タグ : / 解いたユーザー数 73
作問者 :
MasKoaTS
/ テスター :
👑 
AngrySadEight
ygussany
問題文
$2$ 以上の整数 $N$ が与えられます。
$S = \{ N \}$ で初期化された集合 $S$ があり、コアさんとパチェさんはこれを用いてゲームを行います。
コアさんから始めて、次の操作を交互に行います。
$2$ 以上 $N$ 以下の整数 $x$ のうち、次の条件をすべて満たすものを $1$ つ選び、その後 $x$ を $S$ に追加する。
$x \notin S$
ある $y \in S$ が存在し、$x$ と $y$ は互いに素でない
両者のうち、先に操作を行えなくなった方の負けとします。
両者が最善を尽くしたとき、どちらが勝つか判定してください。
$T$ 個のテストケースについて答えを求めてください。
制約
$1 \leq T \leq 10^{5}$
$2 \leq N \leq 3 \times 10^{6}$
入力はすべて整数
入力
入力は次の形式で与えられます。
$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 2 6 100 2023 3000000
出力
P K P P K
まず、$1$ つ目のテストケースでは、先手のコアさんが選べる整数 $x$ は存在しないので、パチェさんが必勝です。
続いて、$2$ つ目のテストケースではコアさんが必勝です。例えば、次のように操作を行います。
$4 \notin S = \{ 6 \}$ かつ $4$ と $6$ は互いに素でないので、コアさんは $x = 4$ を選び、その後 $4$ を $S$ に追加する。
このとき、$S = \{ 4,6 \}$ となる。$3 \notin S = \{ 4,6 \}$ かつ $3$ と $6$ は互いに素でないので、パチェさんは $x = 3$ を選び、その後 $3$ を $S$ に追加する。
このとき、$S = \{ 3,4,6 \}$ となる。$2 \notin S = \{ 3,4,6 \}$ かつ $2$ と $4$ は互いに素でないので、コアさんは $x = 2$ を選び、その後 $2$ を $S$ に追加する。
このとき、$S = \{ 2,3,4,6 \}$ となる。パチェさんが選べる整数 $x$ は存在しないので、コアさんの勝ちとなる。
残りのテストケースについても同様に答えを求めると、上の出力例のようになります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。