結果

問題 No.2176 LRM Question 1
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:55:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 137 ms / 2,000 ms
コード長 985 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,648 KB
実行使用メモリ 212,860 KB
最終ジャッジ日時 2025-03-20 20:56:12
合計ジャッジ時間 2,018 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

L, R, M = map(int, input().split())

if M == 1:
    print(0)
    exit()

# Compute K and s_prev
s_prev = []
current_fact = 1  # Represents (i-1)! % M initially, but modified in loop
prod = 1
K = None

# We need to compute up to K where prod becomes zero
for i in range(1, M + 1):
    current_fact = (current_fact * i) % M
    prod = (prod * current_fact) % M
    if prod == 0:
        K = i
        break
    s_prev.append(prod)
else:
    # In case M is a very large prime and K=M. But since we loop up to M steps, theoretically, K must be <= M.
    K = M + 1  # Not possible, but to handle edge cases
    s_prev = []

# Build prefix sum array
prefix_sum = [0]
current_sum = 0
for x in s_prev:
    current_sum = (current_sum + x) % M
    prefix_sum.append(current_sum)

start = max(L, 1)
end = min(R, K - 1)

if start > end:
    total = 0
else:
    if end >= len(prefix_sum):
        end = len(prefix_sum) - 1
    total = (prefix_sum[end] - prefix_sum[start - 1]) % M

print(total % M)
0