結果

問題 No.3030 Kruskal-Katona
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:09:29
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,515 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 65,536 KB
最終ジャッジ日時 2025-05-14 13:10:34
合計ジャッジ時間 3,461 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def power(base, exp, mod):
    """
    Calculates (base^exp) % mod efficiently.
    Uses the built-in pow function which is highly optimized.
    """
    return pow(base, exp, mod)

def is_prime_miller_rabin(n):
    """
    Checks if a number n is prime using the Miller-Rabin primality test.
    This implementation is deterministic for n < 2^64.
    """
    # Handle base cases for small numbers
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    # Handle even numbers greater than 2
    if n % 2 == 0:
        return False

    # Write n - 1 as 2^s * d, where d is odd
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    # Bases proven to be sufficient for deterministic Miller-Rabin for n < 2^64
    # Source: FIPS 186-4 Appendix F / Wikipedia / various number theory resources
    # A commonly cited set is [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    # Another valid set for n < 3,317,044,064,679,887,385,961,981 is
    # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] (covers 2^64)
    # Let's use the smaller proven set for efficiency.
    # The problem constraint is n < 2^63, so this set is sufficient.
    bases_to_test = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]

    for a in bases_to_test:
        # If the base is >= n, we can skip it or take mod n.
        # Since n can be small (e.g., n=5), some bases might be larger.
        # However, the properties hold if we effectively test a % n.
        # Let's just skip if a >= n, as the test is defined for 1 < a < n-1.
        # More correctly, if n itself is one of the small bases, it should be prime.
        # The initial checks handle n=2, n=3. If n is a larger prime base,
        # the test should correctly identify it.
        if a >= n:
            continue # Test base must be < n

        # Calculate x = a^d mod n
        x = power(a, d, n)

        # If x is 1 or n-1, n might be prime (passes this test base)
        if x == 1 or x == n - 1:
            continue

        # Repeat squaring s-1 times (check a^(d*2^r) for r = 1 to s-1)
        # We already have a^d (r=0).
        composite = True
        for r in range(1, s):
            # Calculate x = x^2 mod n = (a^(d*2^(r-1)))^2 mod n = a^(d*2^r) mod n
            x = power(x, 2, n)

            # If x is 1, then we found a non-trivial square root of 1
            # (because the previous value was not n-1), so n is composite.
            if x == 1:
                return False

            # If x is n-1, n might be prime. Stop squaring for this base 'a'
            # and proceed to the next base.
            if x == n - 1:
                composite = False
                break

        # If the loop finished without finding x == n-1, then 'a' is a witness
        # to the compositeness of n.
        if composite:
            return False

    # If n passed the test for all chosen bases, it is (deterministically) prime
    # for the tested range.
    return True

def solve():
    """
    Reads input, performs primality tests, and prints output.
    """
    n_queries = int(sys.stdin.readline())
    results = []
    for _ in range(n_queries):
        x = int(sys.stdin.readline())
        is_p = is_prime_miller_rabin(x)
        # Append result string "x 0" or "x 1"
        results.append(f"{x} {1 if is_p else 0}")

    # Print all results at once, separated by newlines
    print("\n".join(results))

# Run the main solve function
if __name__ == "__main__":
    solve()
0