Submission #16869227


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8), cache=True)
def main(N, X, M):
    A = np.empty(M + 10, np.int64)
    A[0] = X
    first = np.full(M, -1, np.int64)
    n = 0
    while True:
        n += 1
        A[n] = A[n - 1] * A[n - 1] % M
        if first[A[n]] >= 0:
            period = n - first[A[n]]
            offset = first[A[n]] + 1
            break
        first[A[n]] = n
    if N <= offset:
        return A[:N].sum()
    x = A[:offset].sum()
    N -= offset
    q, r = divmod(N, period)
    x += q * A[offset:offset + period].sum()
    x += A[offset:offset + r].sum()
    return x

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

print(main(N, X, M))

Submission Info

Submission Time
Task E - Sequence Sum
User maspy
Language Python (3.8.2)
Score 500
Code Size 856 Byte
Status
Exec Time 487 ms
Memory 107408 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 3
× 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 487 ms 105452 KB
hand_02.txt 468 ms 106056 KB
hand_03.txt 471 ms 106584 KB
hand_04.txt 476 ms 106608 KB
hand_05.txt 475 ms 106840 KB
max_01.txt 477 ms 106868 KB
max_02.txt 478 ms 107160 KB
max_03.txt 465 ms 106768 KB
max_11.txt 475 ms 107408 KB
max_12.txt 467 ms 106640 KB
max_13.txt 469 ms 106632 KB
random_01.txt 466 ms 105568 KB
random_02.txt 475 ms 105912 KB
random_03.txt 479 ms 106588 KB
random_04.txt 468 ms 106012 KB
random_05.txt 470 ms 105996 KB
random_06.txt 478 ms 106256 KB
random_07.txt 481 ms 106984 KB
random_08.txt 475 ms 106568 KB
random_09.txt 469 ms 106284 KB
random_10.txt 473 ms 106496 KB
sample_01.txt 474 ms 106168 KB
sample_02.txt 474 ms 106672 KB
sample_03.txt 467 ms 106892 KB