結果

問題 No.2724 Coprime Game 1
コンテスト
ユーザー MasKoaTS
提出日時 2024-01-02 21:03:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 986 ms / 2,000 ms
コード長 2,797 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 250,584 KB
最終ジャッジ日時 2024-10-02 22:53:56
合計ジャッジ時間 7,775 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

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