結果

問題 No.3038 シャッフルの再現
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:37:54
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,097 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 67,744 KB
最終ジャッジ日時 2025-06-12 20:38:01
合計ジャッジ時間 2,226 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

MOD = 10**9 + 7

def get_prime_factors(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors[i] = factors.get(i, 0) + 1
            n = n // i
        i += 2
    if n > 1:
        factors[n] = 1
    return factors

def generate_divisors(factors):
    divisors = [1]
    for p in factors:
        exponents = []
        for e in range(factors[p] + 1):
            exponents.append(p ** e)
        current_length = len(divisors)
        for i in range(current_length):
            d = divisors[i]
            for exp in exponents:
                new_d = d * exp
                if new_d not in divisors:
                    divisors.append(new_d)
    divisors = list(set(divisors))
    divisors.sort()
    return divisors

def fib_mod(n, p):
    if n == 0:
        return 0
    def multiply(a, b):
        a00, a01, a10, a11 = a[0][0], a[0][1], a[1][0], a[1][1]
        b00, b01, b10, b11 = b[0][0], b[0][1], b[1][0], b[1][1]
        new00 = (a00 * b00 + a01 * b10) % p
        new01 = (a00 * b01 + a01 * b11) % p
        new10 = (a10 * b00 + a11 * b10) % p
        new11 = (a10 * b01 + a11 * b11) % p
        return [[new00, new01], [new10, new11]]
    def matrix_pow(mat, power):
        result = [[1, 0], [0, 1]]
        while power > 0:
            if power % 2 == 1:
                result = multiply(result, mat)
            mat = multiply(mat, mat)
            power = power // 2
        return result
    mat = [[1, 1], [1, 0]]
    mat_pow = matrix_pow(mat, n)
    return mat_pow[0][1] % p

def compute_pisano_period(p):
    if p == 5:
        return 20
    mod5 = p % 5
    if mod5 in [1, 4]:
        m = p - 1
    else:
        m = 2 * (p + 1)
    factors = get_prime_factors(m)
    divisors = generate_divisors(factors)
    for d in divisors:
        if d == 0:
            continue
        f_d = fib_mod(d, p)
        if f_d != 0:
            continue
        f_d_plus_1 = fib_mod(d + 1, p)
        if f_d_plus_1 == 1:
            return d
    return 0

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    global_factors = {}
    for _ in range(N):
        p = int(input[idx])
        k = int(input[idx + 1])
        idx += 2
        if p == 5:
            factor_dict = {2: 2, 5: k}
        else:
            pi_p = compute_pisano_period(p)
            factors_pi_p = get_prime_factors(pi_p)
            if k > 1:
                factors_pi_p[p] = factors_pi_p.get(p, 0) + (k - 1)
            factor_dict = factors_pi_p
        for prime in factor_dict:
            exp = factor_dict[prime]
            if prime in global_factors:
                if exp > global_factors[prime]:
                    global_factors[prime] = exp
            else:
                global_factors[prime] = exp
    result = 1
    for prime in global_factors:
        exponent = global_factors[prime]
        result = (result * pow(prime, exponent, MOD)) % MOD
    print(result)

if __name__ == '__main__':
    main()
0