結果
| 問題 |
No.3038 シャッフルの再現
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:09 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,396 bytes |
| コンパイル時間 | 472 ms |
| コンパイル使用メモリ | 82,188 KB |
| 実行使用メモリ | 68,300 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:50 |
| 合計ジャッジ時間 | 2,435 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | RE * 1 |
| other | RE * 21 |
ソースコード
import sys
import math
# Define the modulus for the final answer
MOD = 10**9 + 7
# Cache for factorizations to avoid recomputing
factors_cache = {}
# Function to compute the prime factorization of a number using trial division
def get_prime_factorization(num):
"""
Computes the prime factorization of num.
Returns a dictionary mapping prime factors to their exponents.
Uses a cache to store results.
"""
# Return a copy from cache if available to prevent modification issues
if num in factors_cache:
return factors_cache[num].copy()
factors = {}
n = num
# Handle factor 2 separately
count2 = 0
while n % 2 == 0:
count2 += 1
n //= 2
if count2 > 0:
factors[2] = count2
# Handle odd factors starting from 3
d = 3
# Iterate up to sqrt(n)
while d * d <= n:
# If d divides n, find its exponent
if n % d == 0:
count_d = 0
while n % d == 0:
count_d += 1
n //= d
factors[d] = count_d
# Check next odd number
d += 2
# If n is still greater than 1 after the loop,
# the remaining n must be a prime factor itself.
if n > 1:
factors[n] = factors.get(n, 0) + 1
# Store a copy in cache before returning
factors_cache[num] = factors.copy()
return factors
# Function for matrix multiplication modulo p
def mat_mul(A, B, p):
"""
Multiplies two 2x2 matrices A and B modulo p.
"""
C = [[0, 0], [0, 0]]
C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % p
C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % p
C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % p
C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % p
return C
# Function for matrix exponentiation modulo p using binary exponentiation
def mat_pow(A, n, p):
"""
Computes A^n modulo p for a 2x2 matrix A.
"""
# Initialize result as identity matrix
res = [[1, 0], [0, 1]]
base = A
while n > 0:
# If n is odd, multiply result by base
if n % 2 == 1:
res = mat_mul(res, base, p)
# Square the base
base = mat_mul(base, base, p)
# Halve n
n //= 2
return res
# Cache for Pisano periods pi(p)
pisano_cache = {}
# Function to compute the Pisano period pi(p) for a prime p
def compute_pisano_p(p):
"""
Computes the Pisano period modulo a prime p.
The Pisano period pi(p) is the smallest positive integer n such that
F_n = 0 (mod p) and F_{n+1} = 1 (mod p).
Uses properties of Pisano periods and matrix exponentiation.
Caches results.
"""
# Return cached result if available
if p in pisano_cache:
return pisano_cache[p]
# Base cases for p=2 and p=5
if p == 2: return 3
if p == 5: return 20
# Determine the upper bound C for the Pisano period based on p mod 5
rem = p % 5
# If p = 1 or 4 (mod 5), pi(p) divides p-1
if rem == 1 or rem == 4:
C = p - 1
# If p = 2 or 3 (mod 5), pi(p) divides 2*(p+1)
else:
C = 2 * (p + 1)
# Get the prime factorization of the upper bound C
factors_C = get_prime_factorization(C)
# Start with the upper bound as candidate period
n = C
# The Fibonacci matrix L = [[1, 1], [1, 0]]
L = [[1, 1], [1, 0]]
# Identity matrix I
I = [[1, 0], [0, 1]]
# Check each prime factor q of C to find the minimal period
# For each prime factor q of C, we test if we can divide n by q
# while maintaining the property L^n == I (mod p).
for q in factors_C.keys():
# Calculate the potential new period after dividing by q
target_power = n // q
# Compute L^target_power mod p
L_pow = mat_pow(L, target_power, p)
# While L^(n/q) is the identity matrix, we can reduce the period
# Keep dividing n by q as long as the condition holds and n remains divisible by q
while L_pow == I:
n //= q
# If n is no longer divisible by q, stop checking this factor
if n % q != 0:
break
# Recompute target_power and L_pow for the new smaller n
target_power = n // q
L_pow = mat_pow(L, target_power, p)
# Cache and return the computed minimal period pi(p)
pisano_cache[p] = n
return n
# Main function to solve the problem
def solve():
# Read the number of prime factors N
N = int(sys.stdin.readline())
# Dictionary to store the maximum exponents of prime factors for the overall LCM
prime_factors_lcm = {}
# Process each prime factor p_i with exponent k_i
for _ in range(N):
p, k = map(int, sys.stdin.readline().split())
# Compute pi(p), the Pisano period modulo p
pi_p = compute_pisano_p(p)
# Get the prime factorization of pi(p)
factors_pi_p = get_prime_factorization(pi_p)
# Calculate the exponent of p in the factorization of pi(p^k) = p^(k-1) * pi(p)
# v_p(pi(p^k)) = v_p(p^(k-1)) + v_p(pi(p)) = (k-1) + v_p(pi(p))
exp_p_in_pi_pk = factors_pi_p.get(p, 0) # get v_p(pi(p))
if k > 1:
exp_p_in_pi_pk += (k - 1) # add k-1
# Update the maximum exponent found so far for prime p in the overall LCM
prime_factors_lcm[p] = max(prime_factors_lcm.get(p, 0), exp_p_in_pi_pk)
# Update the maximum exponents for other prime factors q != p from factors_pi_p
# v_q(pi(p^k)) = v_q(pi(p)) for q != p
for factor, exponent in factors_pi_p.items():
if factor != p:
prime_factors_lcm[factor] = max(prime_factors_lcm.get(factor, 0), exponent)
# Compute the final LCM value modulo MOD
lcm_val = 1
# Iterate through all collected prime factors and their maximum exponents
for factor, exponent in prime_factors_lcm.items():
# Only include factors with positive exponent
if exponent > 0:
# Compute factor^exponent mod MOD using modular exponentiation
term = pow(factor, exponent, MOD)
# Multiply into the overall LCM value
lcm_val = (lcm_val * term) % MOD
# Print the final result
print(lcm_val)
# Execute the main function
solve()