No.2725 Coprime Game 2
タグ : / 解いたユーザー数 63
作問者 : MasKoaTS / テスター : 👑 p-adic 👑 ygussany
問題文
以上の整数 が与えられます。
で初期化された変数 があり、コアさんとパチェさんはこれを用いてゲームを行います。
コアさんから始めて、次の操作を交互に行います。
以上 以下の整数 のうち、次の条件をすべて満たすものを つ選び、その後 とする。
は の約数でない
と は互いに素である
両者のうち、先に操作を行えなくなった方の負けとします。
両者が最善を尽くしたとき、どちらが勝つか判定してください。
個のテストケースについて答えを求めてください。
制約
入力はすべて整数
入力
入力は次の形式で与えられます。
各テストケースは次の形式で与えられます。
出力
答えを 行ずつ合計 行に出力してください。
行目には、 個目のテストケースについてゲームを行ったときにコアさんが勝つならば K
を、パチェさんが勝つならば P
を出力してください。
サンプル
サンプル1
入力
5 3 18 2023 2 1000000000000000000
出力
K P K P K
まず、 つ目のテストケースではコアさんが必勝です。例えば、次のように操作を行います。
かつ と は互いに素かつ は の約数でないので、
コアさんは を選び、その後 とする。パチェさんが選べる整数 は存在しないので、コアさんの勝ちとなる。
続いて、 つ目のテストケースではパチェさんが必勝です。例えば、次のように操作を行います。
かつ と は互いに素かつ は の約数でないので、
コアさんは を選び、その後 とする。かつ と は互いに素かつ は の約数でないので、
パチェさんは を選び、その後 とする。コアさんが選べる整数 は存在しないので、パチェさんの勝ちとなる。
残りのテストケースについても同様に答えを求めると、上の出力例のようになります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。