No.2721 "Don't say N" Game
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.
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$.
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$.
Among the positive divisors of $6$, the ones Koa can declare are the $2$ integers $1, 6$. From these, Koa chooses and declares $1$.
Among the positive divisors of $6$, the only one Pache can declare is $6$. From these, Pache chooses and declares $6$.
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.
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$.
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$.
Among the positive divisors of $6$, the ones Koa can declare are the $2$ integers $2, 6$. From these, Koa chooses and declares $2$.
Among the positive divisors of $6$, the only one Pache can declare is $6$. From these, Pache chooses and declares $6$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
MasKoaTS