結果

問題 No.3038 シャッフルの再現
ユーザー lam6er
提出日時 2025-04-15 23:35:24
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,310 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 70,496 KB
最終ジャッジ日時 2025-04-15 23:36:29
合計ジャッジ時間 2,187 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd
from random import randint

MOD = 10**9 + 7

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

def factor(n):
    factors = {}
    while n % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        n = n // 2
    if n == 1:
        return factors

    def is_prime(num):
        if num < 2:
            return False
        for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
            if num % p == 0:
                return num == p
        d = num - 1
        s = 0
        while d % 2 == 0:
            d //= 2
            s += 1
        for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
            if a >= num:
                continue
            x = pow(a, d, num)
            if x == 1 or x == num - 1:
                continue
            for _ in range(s - 1):
                x = pow(x, 2, num)
                if x == num - 1:
                    break
            else:
                return False
        return True

    def pollards_rho(num):
        if num % 2 == 0:
            return 2
        if num % 3 == 0:
            return 3
        while True:
            c = randint(1, num - 1)
            f = lambda x: (pow(x, 2, num) + c) % num
            x, y, d = 2, 2, 1
            while d == 1:
                x = f(x)
                y = f(f(y))
                d = gcd(abs(x - y), num)
            if d != num:
                return d

    def _factor(num, fact_dict):
        if num == 1:
            return
        if is_prime(num):
            fact_dict[num] = fact_dict.get(num, 0) + 1
            return
        d = pollards_rho(num)
        _factor(d, fact_dict)
        _factor(num // d, fact_dict)

    _factor(n, factors)
    return factors

def generate_divisors(factors):
    divisors = [1]
    for q, e in sorted(factors.items()):
        current_divisors = []
        for d in divisors:
            power = 1
            for _ in range(e + 1):
                current_divisors.append(d * power)
                power *= q
        divisors = current_divisors
    divisors = sorted(divisors)
    return divisors

def fib_mod(n, mod):
    a, b = 0, 1
    bits = []
    if n == 0:
        return (0, 1)
    while n > 0:
        bits.append(n % 2)
        n = n // 2
    bits.reverse()
    for bit in bits:
        c = a * (2 * b - a) % mod
        d = (a * a + b * b) % mod
        if bit:
            a, b = d, (c + d) % mod
        else:
            a, b = c, d
    return (a, b)

def compute_pisano_period(p):
    if p == 2:
        return 3
    if p == 5:
        return 20
    rem = p % 5
    if rem in (1, 4):
        m = p - 1
    else:
        m = 2 * (p + 1)
    factors = factor(m)
    divisors = generate_divisors(factors)
    for d in divisors:
        if d == 0:
            continue
        fn, fn_plus_1 = fib_mod(d, p)
        if fn == 0 and fn_plus_1 == 1:
            return d
    return m

def main():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    lcm_val = 1
    for _ in range(N):
        p = int(data[idx])
        k = int(data[idx + 1])
        idx += 2
        period_p = compute_pisano_period(p)
        L_i = period_p * pow(p, k - 1, MOD * 1000)
        g = gcd(lcm_val, L_i)
        lcm_val = (lcm_val // g) * L_i
    print(lcm_val % MOD)

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