問題一覧 > 通常問題

No.2721 "Don't say N" Game

レベル : / AI推定難易度 : 625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 183
作問者 : MasKoaTS / テスター : 👑 p-adic ygussany
お気に入りにしたユーザー ProblemId : 10173 / 自分の提出
問題文最終更新日: 2024-03-30 17:19:19
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 a positive integer $N$.

Koa and Pache will now play a game. Starting with Koa, they alternately perform the following operation.

  • Choose $1$ of the positive divisors of $N$ and declare it. However, an integer that has already been declared before this operation cannot be declared.

The player who declares $N$ first loses.

Determine which player wins when both players play optimally.

Find the answer for $T$ test cases.

Constraints

  • $1 \leq T \leq 1000$

  • $1 \leq N \leq 1000$

  • 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

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

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

Sample

Sample 1
Input
4
1
6
23
961
Output
P
K
K
P

First, in test case $1$, the only integer that Koa, who moves first, can declare is $1$, so Pache has a winning strategy.

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

  1. Among the positive divisors of $6$, the ones Koa can declare are the $4$ integers $1, 2, 3, 6$. From these, Koa chooses and declares $2$.

  2. Among the positive divisors of $6$, the ones Pache can declare are the $3$ integers $1, 3, 6$. From these, Pache chooses and declares $3$.

  3. Among the positive divisors of $6$, the ones Koa can declare are the $2$ integers $1, 6$. From these, Koa chooses and declares $1$.

  4. Among the positive divisors of $6$, the only one Pache can declare is $6$. From these, Pache chooses and declares $6$.

  5. Since Pache declared $6$ first, Koa wins.

Note that the operations above are merely one example of the operations performed when both players play optimally.

Strictly speaking, note that in this test case, no matter how Pache acts, as long as Koa acts appropriately,
the game always ends with a win for Koa.

For example, Koa may also win with the following operations.

  1. Among the positive divisors of $6$, the ones Koa can declare are the $4$ integers $1, 2, 3, 6$. From these, Koa chooses and declares $3$.

  2. Among the positive divisors of $6$, the ones Pache can declare are the $3$ integers $1, 2, 6$. From these, Pache chooses and declares $1$.

  3. Among the positive divisors of $6$, the ones Koa can declare are the $2$ integers $2, 6$. From these, Koa chooses and declares $2$.

  4. Among the positive divisors of $6$, the only one Pache can declare is $6$. From these, Pache chooses and declares $6$.

  5. Since Pache declared $6$ first, Koa wins.

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

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