#1032125 (PyPy3) No.8030 ミラー・ラビン素数判定法のテスト

• 問題: No.8030 ミラー・ラビン素数判定法のテスト
• ユーザー: 👑 Mizar
• 提出日時: 2024-12-18 20:04:14
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,156 ms / 9,973 ms
• コード長: 3,700 bytes
• コンパイル時間: 367 ms
• コンパイル使用メモリ: 82,016 KB
• 実行使用メモリ: 86,244 KB
• 最終ジャッジ日時: 2024-12-18 20:04:22
• 合計ジャッジ時間: 7,437 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
other	AC * 10

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
"""Python: Baillie-PSW素数判定法"""
from typing import Optional
import math
import sys
def issq(n: int) -> bool:
    """平方数判定"""
    if n < 0 or ((0x02030213 >> (n & 31)) & 1) == 0:
        return False
    return pow(math.isqrt(n), 2) == n
def kronecker_symbol(a: int, n: int) -> int:
    """クロネッカー記号 https://en.wikipedia.org/wiki/Kronecker_symbol"""
    if n == 0:
        return int(a in (1, -1))
    j = 1
    if n < 0:
        n = -n
        if a < 0:
            j = -j
    if (n & 1) == 0:
        if (a & 1) == 0:
            return 0
        if ((a + 2) & 5) == 5 and ((n & -n).bit_length() & 1) == 0:
            j = -j
        n >>= (n & -n).bit_length() - 1
    if a < 0:
        a = -a
        if (n & 3) == 3:
            j = -j
    while a != 0:
        b = (a & -a).bit_length() - 1
        if ((n + 2) & 5) == 5 and (b & 1) != 0:
            j = -j
        a >>= b
        if (a & n & 3) == 3:
            j = -j
        a, n = n % a, a
    if n == 1:
        return j
    return 0
def isprime_miller_base2(n: int) -> bool:
    """基底2のミラーラビン擬素数判定"""
    #assert n > 2, 'value must be 3 or greater integer'
    #assert (n & 1) == 1, 'value must be odd integer'
    n1 = n - 1
    s = (n1 & -n1).bit_length() - 1
    d = n1 >> s
    t = pow(2, d, n)
    if t in (1, n1):
        return True
    for _ in range(s - 1):
        t = pow(t, 2, n)
        if t == n1:
            return True
    return False
def isprime_lucas(n: int) -> bool:
    """強いリュカ擬素数判定 https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes"""
    #assert n > 2, 'value must be 3 or greater integer'
    #assert (n & 1) == 1, 'value must be odd integer'
    d = lucas_dprobe(n)
    if d is None:
        return False
    q = ((1 - d) >> 2) % n
    k = n + 1
    j = (1 << k.bit_length()) >> 1
    k &= j - 1
    j >>= 1
    u, v, qn = 1, 1, q
    while k != 0:
        u = (u * v) % n
        v = (v * v - (qn + qn)) % n
        qn = (qn * qn) % n
        if (k & j) != 0:
            uu = u + v
            v = (d * u + v) % n
            u = uu + (n & -(uu & 1)) >> 1
            if u >= n:
                u -= n
            v = v + (n & -(v & 1)) >> 1
            qn = (qn * q) % n
            k ^= j
        j >>= 1
    if u == 0 or v == 0:
        return True
    for _ in range(((n + 1) & (~n)).bit_length() - 1):
        u = u * v % n
        v = (v * v - (qn + qn)) % n
        if v == 0:
            return True
        qn = (qn * qn) % n
    return False
def lucas_dprobe(n: int) -> Optional[int]:
    """強いリュカ擬素数判定用の係数決定"""
    #assert n > 2, 'value must be 3 or greater integer'
    #assert (n & 1) == 1, 'value must be odd integer'
    i = 5
    while True:
        if i == n:
            i += 2
        d = i if (i & 3) == 1 else -i
        j = kronecker_symbol(d, n)
        if j == -1:
            return d
        if j == 0 and i < n:
            return None
        if i == 61 and issq(n):
            return None
        i += 2
def isprime(n: int) -> bool:
    """Baillie-PSW素数判定法 https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test"""
    if n < 2 or (n & 1) == 0:
        return n == 2
    return (isprime_miller_base2(n) and isprime_lucas(n))
def __main__():
    """
    yukicoder No.3030 ミラー・ラビン素数判定法のテスト https://yukicoder.me/problems/no/3030
    Mojacoder mizar/素数判定 (64bit) https://mojacoder.app/users/mizar/problems/isprime_64bit
    """
    for _ in range(int(sys.stdin.readline().rstrip())):
        a = sys.stdin.readline().rstrip()
        print(a, int(isprime(int(a))))
__main__()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX