結果

問題 No.2724 Coprime Game 1
コンテスト
ユーザー yu_w(ゆ)
提出日時 2024-04-12 22:13:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 547 ms / 2,000 ms
コード長 687 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 150,016 KB
最終ジャッジ日時 2024-10-02 23:22:52
合計ジャッジ時間 4,579 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
MAX = 3*10**6+10

def Sieve_of_Eratosthenes(N):
    flag=[False]*2+[True]*(N-1)
    for i in range(2,round((N+1)**0.5)+1):
        if flag[i]:
            for j in range(i**2,N+1,i):
                flag[j]=False
    return flag

isPrime = Sieve_of_Eratosthenes(MAX)

ans = [0 for i in range(MAX)]
cantuse = 0
dq = deque()
for i in range(2,MAX):
    if dq:
        if dq[0]*2 <= i:
            cantuse -= 1
            dq.popleft()
    if isPrime[i]:
        cantuse += 1
        dq.append(i)
    else:
        ans[i] = i-2-cantuse


for _ in range(int(input())):
    N=int(input())
    
    if ans[N]%2 == 0:
        print("P")
    else:
        print("K")
0