結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2022-08-16 15:06:36
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,385 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 82,136 KB
実行使用メモリ 66,764 KB
最終ジャッジ日時 2024-10-03 06:08:16
合計ジャッジ時間 1,511 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

class LCGs:
    def __init__(self):
        self.state = 14534622846793005

    def rand(self):
        self.state *= 6364136223846793005
        self.state += 1442695040888963407
        self.state &= 18446744073709551615
        return self.state

    def range(self, left, right):
        return left + self.rand() % (right - left + 1)


def jacobi(a, n):
    t = 0
    j = 1
    while a != 0:
        if a < 0:
            a = -a
            if (n & 3) == 3:
                j = -j
        s = (a & -a).bit_length()
        a >>= s
        if ((n & 7) == 3 or (n & 7) == 5) and (s & 1 == 1):
            j = -j
        if (a & n & 3) == 3:
            j = -j
        t = a
        a = n,
        n = t
        a %= n
        if a > (n // 2):
            a -= n
    return j if n == 1 else 0


def solovay_strassen(n):
    if n == 0 or n == 1:
        return False
    if n == 2 or n == 3:
        return True
    if n & 1 == 0:
        return False
    rnd = LCGs()
    for _ in range(13):
        a = rnd.range(2, 100000000)
        x = jacobi(a, n)
        y = n - 1
        if x == 0:
            y = 0
        elif x != -1:
            y = 1
        if y == 0 or y != pow(a, (n - 1) // 2, n):
            return False
    return True

query = int(input())
while query:
    query -= 1
    n = int(input())
    if solovay_strassen(n):
        print(1)
    else:
        print(0)
0