結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー fiblonaria
提出日時 2025-02-07 02:38:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,290 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 139,656 KB
最終ジャッジ日時 2025-02-07 02:38:34
合計ジャッジ時間 23,001 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 1 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
SAMPLES = 10


def is_prime(n):
    if n == 1:
        return False
    s, t = 0, n - 1
    while t % 2 == 0:
        s += 1
        t //= 2
    for _ in range(SAMPLES):
        a = random.randint(1, n - 1)
        x = pow(a, t, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


def decomposite(n):
    p = 1
    check = 2
    while check <= n:
        check *= 2
        p += 1
    for i in range(p, 0, -1):
        lower, upper = 1, n + 1
        while upper - lower > 1:
            mid = (lower + upper) // 2
            if mid ** i == n:
                return mid
            elif mid ** i < n:
                lower = mid
            else:
                upper = mid
        if lower ** i == n:
            return lower



Q = int(input())
for _ in range(Q):
    n = int(input())
    if n % 2 == 0:
        print('Yes')
    else:
        a = 2
        while a < n:
            # print(n - a, decomposite(n - a), is_prime(decomposite(n - a)))
            if is_prime(decomposite(n - a)):
                print('Yes')
                break
            a *= 2
        else:
            print('No')
0