結果

問題 No.2724 Coprime Game 1
コンテスト
ユーザー Yakumo221
提出日時 2024-04-12 22:16:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,456 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 305,636 KB
最終ジャッジ日時 2024-10-02 23:24:14
合計ジャッジ時間 6,692 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1
other -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

# library from https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a

def is_prime(n):
    if n == 2:  # 2であれば素数なので終了
        return 1
    if n == 1 or n%2 == 0:  # 1もしくは2より大きい偶数であれば素数でないので終了
        return 0

    m = n - 1
    lsb = m & -m  # LSB. m-1をビット列で表した時立っているビットのうち最も小さいもの
    s = lsb.bit_length()-1  # 上述のs. LSB以上のビットの部分をdとし、2^s = LSBとすると上述のp-1 = 2^sdを満たす
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in test_numbers:
        if a == n:  # a = n -> 任意の自然数kについてa^k ≡ 0(mod n)なので無視
            continue
        x = pow(a,d,n)  # x ≡ a^d(mod n)で初期化
        r = 0
        if x == 1:  # a^d ≡ 1(mod n)なので無視
            continue
        while x != m:  # r = 0からsまで順にx ≡ a^(2^rd) ≡ -1(mod n)を検証
            x = pow(x,2,n)
            r += 1
            if x == 1 or r == s:  # x ≡ 1(mod n) -> x^2 ≡ 1(mod n)で-1になり得ないので合成数
                return 0
    return 1  # すべてのテストを通過したら素数であるとして終了

def primeenumeration(n):
    # 2<= p<=nを満たす素数nのリストを返す
    ret = []
    if n < 2:
        return ret
    ok = [False if i % 2 == 0 else True for i in range(n+1)]
    ok[1] = False
    ok[2] = True
    ret.append(2)

    for i in range(3, n+1, 2):
        if ok[i]:
            ret.append(i)
            for j in range(i, n+1,i):
                ok[j] = False

    return ret

prime = primeenumeration(1500000)

t = int(input())
while t:
    t -= 1

    n = int(input())
    if is_prime(n):
        print("P")
        continue

    lim = n // 2

    pl = [1]
    mi = []
    
    s = 0
    for p in prime:
        if p > lim:
            break
        # print(pl, mi)
        
        npl = pl[:]
        nmi = mi[:]

        for v in pl:
            k = v*p
            if k > n:
                break
            s += n // k
            nmi.append(k)
        
        for v in mi:
            k = v*p
            if k > n:
                break
            s -= n // k
            npl.append(k)
        
        pl = npl
        mi = nmi
        pl.sort()
        mi.sort()
    
    s -= 1


    if s % 2 == 0:
        print("P")
    else:
        print("K")
0