問題一覧 > 通常問題

No.2725 Coprime Game 2

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 69
作問者 : MasKoaTS / テスター : 👑 p-adic ygussany
お気に入りにしたユーザー ProblemId : 9085 / 自分の提出
問題文最終更新日: 2024-03-30 18:12:47
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$ that is at least $2$.

There is a variable $y$ initialized as $y = 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 $y$, inclusive, choose $1$ that satisfies all of the following conditions, and then set $y = x$.

    • $x$ is not a divisor of $N$

    • $x$ and $y$ are coprime

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

Determine who wins when both players play optimally.

Find the answer for $T$ test cases.

Constraints

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

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

  • 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 the $i$-th test case, print Koa wins as K, and Pache wins as P; that is, print the letter corresponding to the winner.

Sample

Sample 1
Input
5
3
18
2023
2
1000000000000000000
Output
K
P
K
P
K

First, in the $1$st test case, Koa has a winning strategy. For example, the operations proceed as follows.

  1. Since $2 \leq 2 \leq y = 3$, $2$ and $3$ are coprime, and $2$ is not a divisor of $3$,
    Koa chooses $x = 2$ and then sets $y = 2$.

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

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

  1. Since $2 \leq 11 \leq y = 18$, $11$ and $18$ are coprime, and $11$ is not a divisor of $18$,
    Koa chooses $x = 11$ and then sets $y = 11$.

  2. Since $2 \leq 4 \leq y = 11$, $4$ and $11$ are coprime, and $4$ is not a divisor of $18$,
    Pache chooses $x = 4$ and then sets $y = 4$.

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

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

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