提出 #56991713

ソースコード 拡げる

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

N, X, M = rints()
A = [X]
d = {X: 0}
cycle_start = -1
for i in range(1, N):
    X = X * X % M
    if X in d:
        cycle_start = d[X]
        break
    A.append(X)
    d[X] = i

ans = 0
if cycle_start == -1:
    ans = sum(A)
else:
    cycle_sum = sum(A[cycle_start:])
    cycle_len = len(A[cycle_start:])
    ans = sum(A[:cycle_start])
    N -= cycle_start
    A = A[cycle_start:]
    ans += N // cycle_len * cycle_sum + sum(A[: N % cycle_len])
print(ans)

提出情報

提出日時
問題 E - Sequence Sum
ユーザ gigolo
言語 Python (PyPy 3.10-v7.3.12)
得点 500
コード長 555 Byte
結果 AC
実行時間 93 ms
メモリ 92420 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 500 / 500
結果
AC × 3
AC × 24
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, max_01.txt, max_02.txt, max_03.txt, max_11.txt, max_12.txt, max_13.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
hand_01.txt AC 79 ms 76400 KiB
hand_02.txt AC 74 ms 76556 KiB
hand_03.txt AC 78 ms 76600 KiB
hand_04.txt AC 78 ms 76364 KiB
hand_05.txt AC 89 ms 87724 KiB
max_01.txt AC 93 ms 92008 KiB
max_02.txt AC 89 ms 92420 KiB
max_03.txt AC 86 ms 92128 KiB
max_11.txt AC 77 ms 76800 KiB
max_12.txt AC 75 ms 76320 KiB
max_13.txt AC 77 ms 76392 KiB
random_01.txt AC 79 ms 76352 KiB
random_02.txt AC 79 ms 76392 KiB
random_03.txt AC 76 ms 76444 KiB
random_04.txt AC 75 ms 76604 KiB
random_05.txt AC 76 ms 76336 KiB
random_06.txt AC 79 ms 76364 KiB
random_07.txt AC 79 ms 76392 KiB
random_08.txt AC 80 ms 76452 KiB
random_09.txt AC 77 ms 76628 KiB
random_10.txt AC 74 ms 76236 KiB
sample_01.txt AC 66 ms 76324 KiB
sample_02.txt AC 70 ms 76652 KiB
sample_03.txt AC 72 ms 76572 KiB