結果

問題 No.2724 Coprime Game 1
ユーザー MasKoaTSMasKoaTS
提出日時 2024-01-02 21:03:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 828 ms / 2,000 ms
コード長 2,797 bytes
コンパイル時間 152 ms
コンパイル使用メモリ 82,692 KB
実行使用メモリ 250,448 KB
最終ジャッジ日時 2024-04-12 20:50:44
合計ジャッジ時間 6,616 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 754 ms
248,416 KB
testcase_01 AC 117 ms
85,904 KB
testcase_02 AC 117 ms
86,368 KB
testcase_03 AC 766 ms
250,448 KB
testcase_04 AC 810 ms
250,180 KB
testcase_05 AC 807 ms
250,312 KB
testcase_06 AC 788 ms
249,444 KB
testcase_07 AC 828 ms
250,148 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools as iter
import collections as coll
import heapq as hq
import bisect as bis
from decimal import Decimal as dec
from functools import cmp_to_key
import math
import sys
#import pypyjit
#pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10 ** 6)
inp = sys.stdin.readline
input = lambda : inp()[:-1]
getN = lambda : int(inp())
getNs = lambda : map(int, inp().split())
getList = lambda : list(map(int, inp().split()))
getStrs = lambda n : [input() for _ in [0] * n]
getEdges = lambda n : [[x - 1 for x in getNs()] for _ in [0] * n]
getWEdges = lambda n : [[x - (i < 2) for i, x in enumerate(getNs())] for _ in [0] * n]
def yexit(): print("Yes"); exit(0)
def nexit(): print("No"); exit(0)
pi = 3.141592653589793
mod = 1000000007
MOD = 998244353
INF = 4611686018427387903
dxs = [1, 0, -1, 0];  dys = [0, 1, 0, -1]
#di = coll.defaultdict(int)

class Eratos:
    def __init__(self, n):
        self.n = n
        self.rad = self._seive()
        self.prime = [i == x for i, x in enumerate(self.rad)]
        self.prime[0] = self.prime[1] = False
        self.mebius = self._calc_mebius()

    def _seive(self):
        ret = [*range(self.n + 1)]
        for i in range(2, self.n + 1):
            if(ret[i] != i):
                continue
            for j in range(i * i, self.n + 1, i):
                if(ret[j] != j):
                    continue
                ret[j] = i
        return ret
    
    def _calc_mebius(self):
        ret = [-2] * (self.n + 1)
        for i in range(2, self.n + 1):
           ret[i] = self._get_mebius(i, ret)
        return ret

    def _get_mebius(self, x, mebius):
        cnt = 0
        while(x > 1):
            k = mebius[x]
            if(k != -2):
                if(k == 0):
                    return 0
                cnt += (k == -1)
                break
            p = self.rad[x]
            if(p == self.rad[x // p]):
                return 0
            x //= p
            cnt += 1
        if(cnt & 1):
            return -1
        return 1
    
    def is_prime(self, x):
        assert(2 <= x <= self.n)
        return self.prime[x]
    
    def factorize(self, x):
        assert(2 <= x <= self.n)
        ret = []
        while(x != 1):
            p = self.rad[x]
            q = 0
            while(self.rad[x] == p):
                q += 1
                x //= p
            ret.append((p, q))
        return ret

"""
Main Code
"""

query = [getN() for _ in [0] * getN()]
n_max = max(query)
era = Eratos(n_max)

prime_cnt = era.prime[:]
for i in range(1, n_max + 1):
    prime_cnt[i] += prime_cnt[i - 1]

for n in query:
    if era.is_prime(n):
        print('P')
    else:
        g = n - 2 - prime_cnt[n] + prime_cnt[n // 2]
        if(g & 1):
            print('K')
        else:
            print('P')
0