結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー vwxyz
提出日時 2021-08-08 12:24:42
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,472 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 96,256 KB
最終ジャッジ日時 2024-09-19 07:59:51
合計ジャッジ時間 12,712 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines

def Pollard_Rho(N):
    m=1<<N.bit_length()//8
    for c in range(1,99):
        f=lambda x:(x**2+c)%N
        y,r,q,g=2,1,1,1
        while g==1:
            x=y
            for _ in range(r):
                y=f(y)
            k=0
            while k<r and g==1:
                ys=y
                for _ in range(min(m,r-k)):
                    y=f(y)
                    q=q*abs(x-y)%N
                g=math.gcd(q,N)
                k+=m
            r<<=1
        if g==N:
            g=1
            while g==1:
                ys=f(ys)
                g=math.gcd(abs(x-ys),N)
        if g<N:
            return g
n=int(readline())
for _ in range(n):
    x=int(readline())
    if x==1:
        ans=0
    else:
        if Pollard_Rho(x)==None:
            ans=1
        else:
            ans=0
    print(x,ans)
0