問題一覧 > 通常問題

No.2724 Coprime Game 1

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 82
作問者 : MasKoaTS / テスター : 👑 AngrySadEight ygussany
お気に入りにしたユーザー ProblemId : 9080 / 自分の提出
問題文最終更新日: 2024-03-30 23:52:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 427 (ゲーム問題コンテスト) (順位表) の他の問題:

Problem Statement

You are given an integer $N$ greater than or equal to $2$.

There is a set $S$ initialized as $S = \{ N \}$, and Koa and Pache play a game using it.
Starting with Koa, they alternately perform the following operation.

  • Among the integers $x$ between $2$ and $N$, inclusive, choose $1$ that satisfies all of the following conditions, and then add $x$ to $S$.

    • $x \notin S$

    • There exists some $y \in S$ such that $x$ and $y$ are not coprime.

The player who first becomes unable to perform the operation loses.

Determine who wins when both players play optimally.

$T$ test cases are given; find the answer for each of them.

Constraints

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

  • $2 \leq N \leq 3 \times 10^{6}$

  • All input values are integers.

Input

The input is given in the following format.

$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
  $\vdots$
$\mathrm{case}_{T}$

Each test case is given in the following format.

$N$

Output

Print the answers, $1$ per line, for a total of $T$ lines.

On line $i$ $(1 \leq i \leq T)$, for the game played on test case $i$, if Koa wins, print K, and if Pache wins, print P.

Sample

Sample 1
Input
5
2
6
100
2023
3000000
Output
P
K
P
P
K

First, in test case $1$, there is no integer $x$ that Koa, who moves first, can choose, so Pache has a winning strategy.

Next, in test case $2$, Koa has a winning strategy. For example, the operations are performed as follows.

  1. Since $4 \notin S = \{ 6 \}$ and $4$ and $6$ are not coprime, Koa chooses $x = 4$ and then adds $4$ to $S$.
    Now, $S = \{ 4,6 \}$.

  2. Since $3 \notin S = \{ 4,6 \}$ and $3$ and $6$ are not coprime, Pache chooses $x = 3$ and then adds $3$ to $S$.
    Now, $S = \{ 3,4,6 \}$.

  3. Since $2 \notin S = \{ 3,4,6 \}$ and $2$ and $4$ are not coprime, Koa chooses $x = 2$ and then adds $2$ to $S$.
    Now, $S = \{ 2,3,4,6 \}$.

  4. There is no integer $x$ that Pache can choose, so Koa wins.

Finding the answers for the remaining test cases in the same way gives the sample output above.

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