提出 #62117259

---

ソースコード 拡げる

# https://judge.yosupo.jp/submission/159590
from random import randint
from math import gcd


def is_prime(n):
    if n % 2 == 0:
        return n == 2
    if n == 1:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d = d // 2
        s += 1
    a = [2, 7, 61]
    for i in a:
        if i >= n:
            break
        now = pow(i, d, n)
        if now != 1:
            comp = True
            for j in range(s):
                if now == n - 1:
                    comp = False
                    break
                now = (now * now) % n
            if comp:
                return False
    return True


def prime_fact(n):
    ret = []
    for i in range(2, 100):
        while n % i == 0:
            ret.append(i)
            n //= i
    if n == 1:
        return ret
    calc = [n]
    while len(calc) > 0:
        n = calc.pop()
        while not (is_prime(n)):
            x = randint(0, n - 1)
            plus = randint(1, n - 1)
            y = x
            i = 1
            while True:
                x = (x * x + plus) % n
                y = (y * y + plus) % n
                y = (y * y + plus) % n
                d = gcd(abs(x - y), n)
                if d == 1:
                    i += 1
                elif d == n or d == 0:
                    break
                else:
                    if is_prime(d):
                        ret.append(d)
                    else:
                        calc.append(d)
                    n = n // d
                    break
        ret.append(n)
    return ret


from sys import stdin
input = stdin.readline

for _ in range(int(input())):
    n = int(input())
    while True:
        k = randint(1, 1000)
        p = n * k + 1
        if is_prime(p):
            break
    fa = list(set(prime_fact(n)))
    while True:
        a = pow(randint(1, p - 1), k, p)
        for f in fa:
            if pow(a, n // f, p) == 1:
                break
        else:
            print(a, p)
            break

提出情報

ジャッジ結果