結果

問題 No.2724 Coprime Game 1
ユーザー yu_w(ゆ)yu_w(ゆ)
提出日時 2024-04-12 22:13:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 607 ms / 2,000 ms
コード長 687 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 149,876 KB
最終ジャッジ日時 2024-04-12 22:13:36
合計ジャッジ時間 5,234 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 295 ms
149,804 KB
testcase_01 AC 344 ms
149,764 KB
testcase_02 AC 304 ms
149,748 KB
testcase_03 AC 503 ms
149,832 KB
testcase_04 AC 607 ms
149,704 KB
testcase_05 AC 535 ms
149,684 KB
testcase_06 AC 430 ms
149,788 KB
testcase_07 AC 591 ms
149,876 KB
権限があれば一括ダウンロードができます

ソースコード

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