Problem: Let us denote by f(x, m) the remainder of the Euclidean division of x by m.  Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N A_i}.

Submission attempts (in order):
N, X, M = [int(x) for x in input().split()]
copy = M

k = 0
while M % 2 == 0:
    k += 1
    M = M // 2
L = M

order = 1
if L != 1:
    e = 2 % L
    while e != 1:
        order += 1
        e = (2 * e) % L

A = [0] * (k + order)
A[1] = X
for i in range(2, k + order):
    A[i] = (A[i - 1] * A[i - 1]) % copy

S = sum(A[k:])
ans = 0
if N < k:
    ans = sum(A[1:N + 1])
else:
    q, r = (N - k - 1) // order, (N - k - 1) % order
    ans = sum(A[1:k]) + S * q + sum(A[k:k + r])

print(ans)

N, X, M = [int(x) for x in input().split()]

A = [0] * (M + 1)
firstApearAt = {i:0 for i in range(M)}
A[1] =  X
firstApearAt[X] = 1
l, r = 1
for i in range(2, M + 1):
    A[i] = (A[i - 1] * A[i - 1]) % M
    if firstApearAt[A[i]] > 0:
        r = i
        l = firstApearAt[A[i]]
        break
    firstApearAt[A[i]] = i

ans = 0
if N <= l - 1:
    ans = sum(A[1:N + 1])
else:
    q, p = (N - l + 1) // (r - l), (N - l + 1) % (r - l)
    ans = sum(A[1:l]) + q * sum(A[l:r]) + sum(A[l:l + p])

print(ans)

N, X, M = [int(x) for x in input().split()]
copy = M

k = 0
while M % 2 == 0:
    k += 1
    M = M // 2
L = M

order = 1
if L != 1:
    e = 2 % L
    while e != 1:
        order += 1
        e = (2 * e) % L

A = [0] * (k + order)
A[1] = X
for i in range(2, k + order + 1):
    A[i] = (A[i - 1] * A[i - 1]) % copy

S = sum(A[k:])
ans = 0
if N < k:
    ans = sum(A[1:N + 1])
else:
    q, r = (N - k - 1) // order, (N - k - 1) % order
    ans = sum(A[1:k]) + S * q + sum(A[k:k + r])

print(ans)

N, X, M = [int(x) for x in input().split()]
copy = M

k = 0
while M % 2 == 0:
    k += 1
    M = M // 2
L = M

order = 1
if L != 1:
    e = 2 % L
    while e != 1:
        order += 1
        e = (2 * e) % L

A = [None] * (k + order)
A[1] = X
for i in range(2, k + order + 1):
    A[i] = (A[i - 1] * A[i - 1]) % copy

S = sum(A[k:])
ans = 0
if N < k:
    ans = sum(A[1:N + 1])
else:
    q, r = (N - k - 1) // order, (N - k - 1) % order
    ans = sum(A[1:k]) + S * q + sum(A[k:k + r])

print(ans)

N, X, M = [int(x) for x in input().split()]
copy = M

k = 0
while M % 2 == 0:
    k += 1
    M = M // 2
L = M

order = 1
if L != 1:
    e = 2 % L
    while e != 1:
        order += 1
        e = (2 * e) % L

A = [0] * (k + order)
A[1] = X
for i in range(2, k + order):
    A[i] = (A[i - 1] * A[i - 1]) % copy

S = sum(A[k:])
ans = 0
if N < k:
    ans = sum(A[1:N + 1])
else:
    q, r = (N - k - 1) // order, (N - k - 1) % order
    ans = sum(A[1:k]) + S * q + sum(A[k:k + r])

print(ans)

N, X, M = [int(x) for x in input().split()]

A = [0] * (M + 1)
firstApearAt = {i:0 for i in range(M)}
A[1] =  X
firstApearAt[X] = 1
l, r = 1, 2
for i in range(2, M + 1):
    A[i] = (A[i - 1] * A[i - 1]) % M
    if firstApearAt[A[i]] > 0:
        r = i
        l = firstApearAt[A[i]]
        break
    firstApearAt[A[i]] = i

ans = 0
if N <= l - 1:
    ans = sum(A[1:N + 1])
else:
    q, p = (N - l + 1) // (r - l), (N - l + 1) % (r - l)
    ans = sum(A[1:l]) + q * sum(A[l:r]) + sum(A[l:l + p])

print(ans)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted