結果
| 問題 |
No.2193 メガの下１桁
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:08:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 2,000 ms |
| コード長 | 10,120 bytes |
| コンパイル時間 | 163 ms |
| コンパイル使用メモリ | 82,444 KB |
| 実行使用メモリ | 54,612 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:10 |
| 合計ジャッジ時間 | 2,628 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 40 |
ソースコード
import sys
# Function to compute Euler's totient function phi(n)
# It computes the count of positive integers up to n that are relatively prime to n.
def get_phi_standard(n):
"""Computes Euler's totient function phi(n)."""
if n == 1:
# By convention phi(1)=1. It also serves as the base case for the modulus tower.
return 1
result = n
p = 2
_n = n # Use a temporary copy to modify
# Iterate through potential prime factors up to sqrt(n)
while p * p <= _n:
if _n % p == 0:
# p is a prime factor of n
while _n % p == 0:
# Remove all factors of p from _n
_n //= p
# Apply the formula part for factor p: result = result * (1 - 1/p)
result -= result // p
p += 1
# If _n > 1 after the loop, it means there's a remaining prime factor greater than sqrt(n)
if _n > 1:
result -= result // _n
return result
# Function to generate the tower of moduli: B, phi(B), phi(phi(B)), ..., 1
def get_modulus_tower(B):
"""Generates the tower of moduli B, phi(B), phi(phi(B)), ..., until 1."""
tower = []
curr = B
visited = set() # Used to detect potential cycles in phi function sequence (unlikely for small B)
while curr not in visited:
visited.add(curr)
tower.append(curr)
if curr == 1:
# Tower ends when 1 is reached
break
curr = get_phi_standard(curr)
# For B > 1, the sequence phi(phi(...phi(B)...)) eventually reaches 1.
# Ensure 1 is in the tower if B > 1. This should always happen naturally.
# Example: B=10 -> [10, 4, 2, 1]. B=7 -> [7, 6, 2, 1].
return tower
# Custom modular exponentiation function for large exponents M_k >= 4
# It uses the property derived from Euler's totient theorem extension:
# a^e === a^(e mod phi(mod) + phi(mod)) (mod mod) for e >= threshold
# The threshold is related to the prime factorization of mod. For mod <= 11, threshold is at most 3.
# Since we call this only when M_k >= 4, the condition is satisfied.
def custom_pow_large_exp(base, exp_mod_phi, phi, mod):
"""Computes base^exponent mod mod using Euler's theorem extension.
Assumes exponent >= 4."""
base %= mod
if base == 0:
# The exponent M_k is >= 4, hence positive. 0^positive = 0.
# This holds even for mod = 1, as 0 % 1 = 0.
return 0
# Calculate the effective exponent according to the theorem extension
effective_exponent = exp_mod_phi + phi
# Since phi >= 1 and exp_mod_phi >= 0, effective_exponent >= 1.
# Perform modular exponentiation using binary exponentiation (also known as exponentiation by squaring)
res = 1
current_base = base
current_exp = effective_exponent
while current_exp > 0:
if current_exp % 2 == 1:
# If the current bit of the exponent is 1, multiply the result by current_base
res = (res * current_base) % mod
# Square the current_base for the next bit
current_base = (current_base * current_base) % mod
# Move to the next bit (integer division by 2)
current_exp //= 2
return res
# Main part of the program
M = int(sys.stdin.readline()) # Initial value
D = int(sys.stdin.readline()) # Shift value
N = int(sys.stdin.readline()) # Number of iterations
B = int(sys.stdin.readline()) # Base for the final output digit
# Handle the trivial case N=0: The result is M itself. We need M mod B.
if N == 0:
final_val_mod_B = M % B
if final_val_mod_B < 10:
print(final_val_mod_B)
elif final_val_mod_B == 10: # Only possible if B=11
print('A')
# No else needed since B <= 11 restricts results to 0..10.
exit() # Terminate the program after printing
# Generate the modulus tower and precompute phi values
mods = get_modulus_tower(B)
phis = {}
for mod_val in mods:
phis[mod_val] = get_phi_standard(mod_val)
# Calculate the initial state S_0
vals_curr = []
for mod_val in mods:
# M can be very large, but Python handles large integers. Modulo operation keeps values small.
if mod_val == 0: # Safety check, should not happen for B >= 2
vals_curr.append(0)
else:
vals_curr.append(M % mod_val)
# Track the exact value of M_k if it's small (0, 1, 2, 3), otherwise mark it as large (>= 4).
# We use a 'capped value': min(M_k, 4). A value of 4 indicates M_k >= 4.
capped_val_curr = min(M, 4)
# The state is a tuple: (tuple of modular values, capped value)
# Tuples are hashable, suitable for dictionary keys (for cycle detection).
state_curr = (tuple(vals_curr), capped_val_curr)
# History stores states encountered and the step number they occurred at.
# Used for cycle detection. {state: step_number}
history = {state_curr: 0}
# states_list stores states in the order they appear. Used to retrieve state by index.
states_list = [state_curr]
k = 0 # Current step number completed
while k < N:
# Get values from the previous state (state at step k)
vals_prev = list(state_curr[0]) # M_k mod B_i values
capped_val_prev = state_curr[1] # min(M_k, 4)
# Compute the capped value for the next state M_{k+1}
capped_val_next = -1
if capped_val_prev == 0: # M_k = 0
# Transformation: (0+D)^0. If D=0, 0^0=1. If D>0, D^0=1. So M_{k+1} = 1.
capped_val_next = 1
elif capped_val_prev == 1: # M_k = 1
# Transformation: (1+D)^1 = 1+D. So M_{k+1} = 1+D.
# Compare 1+D with 4. D can be large.
if D >= 3: # Check if 1+D >= 4
capped_val_next = 4
else: # D is 0, 1, or 2. Then 1+D is 1, 2, or 3.
capped_val_next = int(1 + D) # Safe to convert to int
else: # M_k >= 2 (capped_val_prev is 2, 3, or 4)
# Transformation: M_{k+1} = (M_k+D)^{M_k}
# If M_k=2, M_{k+1}=(2+D)^2 >= 2^2 = 4 (since D>=0).
# If M_k=3, M_{k+1}=(3+D)^3 >= 3^3 = 27.
# If M_k>=4, M_{k+1}=(M_k+D)^{M_k} >= (4+D)^4 >= 4^4 = 256.
# In all cases where M_k >= 2, the next value M_{k+1} is >= 4.
capped_val_next = 4
# Compute the modular values for the next state M_{k+1}
vals_next = []
for i in range(len(mods)):
mod_val = mods[i]
m_k_plus_1_mod_i = -1 # Placeholder for M_{k+1} mod B_i
if mod_val == 0: # Defensive check
vals_next.append(0)
continue
# Calculate M_{k+1} mod mod_val based on M_k's capped value
if capped_val_prev == 0: # M_k = 0 => M_{k+1} = 1
# Result is 1 mod mod_val
if mod_val == 1: m_k_plus_1_mod_i = 0
else: m_k_plus_1_mod_i = 1
elif capped_val_prev == 1: # M_k = 1 => M_{k+1} = 1 + D
# Compute (1 + D) mod mod_val. D can be large.
m_k_plus_1_mod_i = (1 + D) % mod_val
elif capped_val_prev == 2: # M_k = 2 => M_{k+1} = (2+D)^2
# Compute base = (2+D) mod mod_val
base = (2 + D) % mod_val
# Compute base^2 mod mod_val. Standard pow is efficient for small fixed exponents.
m_k_plus_1_mod_i = pow(base, 2, mod_val)
elif capped_val_prev == 3: # M_k = 3 => M_{k+1} = (3+D)^3
base = (3 + D) % mod_val
# Compute base^3 mod mod_val.
m_k_plus_1_mod_i = pow(base, 3, mod_val)
else: # capped_val_prev == 4, meaning M_k >= 4
# M_{k+1} = (M_k+D)^{M_k}
# Base for exponentiation: (M_k + D) mod mod_val
base = (vals_prev[i] + D % mod_val) % mod_val
# Need exponent M_k modulo phi(mod_val)
phi_of_mod = phis[mod_val] # Look up precomputed phi(B_i)
exp_mod_phi = -1
# phi(mod_val) = phi(B_i) = B_{i+1}. We need M_k mod B_{i+1}.
# This value is available in vals_prev at index i+1.
if i + 1 < len(mods):
exp_mod_phi = vals_prev[i+1]
else:
# This case occurs if mod_val = 1 (last element of tower).
# phi(1)=1. M_k mod 1 = 0.
exp_mod_phi = 0
# Call the custom power function for large exponents M_k >= 4
m_k_plus_1_mod_i = custom_pow_large_exp(base, exp_mod_phi, phi_of_mod, mod_val)
vals_next.append(m_k_plus_1_mod_i)
# Construct the state for step k+1
state_next = (tuple(vals_next), capped_val_next)
k += 1 # Increment step counter after computing state for step k
# Check if the computed state has been seen before (cycle detection)
if state_next in history:
# Cycle detected!
start_step = history[state_next] # Step number where cycle begins
cycle_len = k - start_step # Length of the cycle
remaining_steps = N - k # Number of steps remaining after current step k
# Calculate the index in the cycle corresponding to the final Nth step
final_step_in_cycle = remaining_steps % cycle_len
# The index in states_list corresponding to the final state S_N
final_state_idx = start_step + final_step_in_cycle
# Retrieve the final state S_N from the list
state_curr = states_list[final_state_idx]
# Break the loop since we found the state for step N
break
else:
# State is new. Record it in history and list.
history[state_next] = k
states_list.append(state_next)
# Update current state for the next iteration
state_curr = state_next
# After the loop (either completed N steps or broke due to cycle detection),
# state_curr holds the final state S_N.
# The required result is M_N mod B. This is the first element of the vals tuple in the final state.
final_val_mod_B = state_curr[0][0]
# Output the result in base B. For B=11, 10 is represented as 'A'.
if final_val_mod_B < 10:
print(final_val_mod_B)
elif final_val_mod_B == 10: # Must be B=11 case
print('A')
# No other cases needed as B <= 11 implies result mod B <= 10.