結果

問題 No.1232 2^x = x
ユーザー lam6er
提出日時 2025-04-15 21:53:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 1,583 bytes
コンパイル時間 419 ms
コンパイル使用メモリ 81,744 KB
実行使用メモリ 69,616 KB
最終ジャッジ日時 2025-04-15 21:55:19
合計ジャッジ時間 2,254 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def input():
    return sys.stdin.read()

def baby_step_giant_step(a, b, mod):
    if b == 1:
        return 0
    m = int(math.isqrt(mod)) + 1
    table = {}
    current = 1
    for j in range(m):
        if current not in table:
            table[current] = j
        current = (current * a) % mod

    am_inv = pow(a, mod - m - 1, mod)
    gamma = b
    for i in range(m):
        if gamma in table:
            return i * m + table[gamma]
        gamma = (gamma * am_inv) % mod
    return -1

def crt(a1, m1, a2, m2):
    d = math.gcd(m1, m2)
    if (a1 - a2) % d != 0:
        return -1
    lcm = m1 // d * m2
    m1_dash = m1 // d
    m2_dash = m2 // d
    inv = pow(m1_dash, -1, m2_dash)
    k = (a2 - a1) // d % m2_dash
    x = (a1 + k * m1) % lcm
    return x

def solve():
    data = input().split()
    n = int(data[0])
    primes = list(map(int, data[1:n+1]))
    for p in primes:
        if p == 2:
            print(2)
            continue
        found = False
        max_a = min(p-1, 1000)
        for a in range(max_a + 1):
            if pow(2, a, p) == a % p:
                b = baby_step_giant_step(2, a % p, p)
                if b == -1:
                    continue
                x = crt(a, p, b, p-1)
                if x == -1:
                    continue
                if x <= 0:
                    x += p * (p-1)
                if x > 1e18:
                    continue
                print(x)
                found = True
                break
        if not found:
            x = (p-1) ** 2
            print(x)
solve()
0