Submission #21285598

Source Code Expand

import math

N,X,M = map(int,input().split())

# 二次元配列作成
nex = []
nsum = []

for _ in range(int(math.log2(N)) + 1):
    l1 = [0] * M
    l2 = [0] * M
    nex.append(l1)
    nsum.append(l2)

# dv[0][0:X]を初期化
for m in range(M):
    nex[0][m] = (m*m)%M
    nsum[0][m] = m

# ダブリングで表を構築
for k in range(1, int(math.log2(N)) + 1):
    for m in range(M):
        nex[k][m] = nex[k - 1][nex[k - 1][m]]
        nsum[k][m] = nsum[k - 1][m] + nsum[k - 1][nex[k - 1][m]]

a = []
for i in range(int(math.log2(N)) + 1):
    if N>>i & 1:
        a.append(i)

ans = 0

for i in a:
    ans += nsum[i][X]
    X = nex[i][X]
print(ans)

Submission Info

Submission Time
Task E - Sequence Sum
User H20
Language PyPy3 (7.3.0)
Score 500
Code Size 692 Byte
Status AC
Exec Time 181 ms
Memory 121564 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 24
Set Name Test Cases
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
Case Name Status Exec Time Memory
hand_01.txt AC 69 ms 62220 KiB
hand_02.txt AC 50 ms 62340 KiB
hand_03.txt AC 143 ms 121564 KiB
hand_04.txt AC 142 ms 121160 KiB
hand_05.txt AC 116 ms 92732 KiB
max_01.txt AC 176 ms 120968 KiB
max_02.txt AC 176 ms 120704 KiB
max_03.txt AC 181 ms 120464 KiB
max_11.txt AC 136 ms 121256 KiB
max_12.txt AC 138 ms 121224 KiB
max_13.txt AC 139 ms 121092 KiB
random_01.txt AC 79 ms 70772 KiB
random_02.txt AC 93 ms 83212 KiB
random_03.txt AC 123 ms 96484 KiB
random_04.txt AC 71 ms 69784 KiB
random_05.txt AC 63 ms 69760 KiB
random_06.txt AC 89 ms 84264 KiB
random_07.txt AC 133 ms 108508 KiB
random_08.txt AC 152 ms 113280 KiB
random_09.txt AC 91 ms 88492 KiB
random_10.txt AC 129 ms 100004 KiB
sample_01.txt AC 59 ms 64816 KiB
sample_02.txt AC 53 ms 62056 KiB
sample_03.txt AC 169 ms 121456 KiB