Problem:


Score : 500 points

Problem Statement

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}.

Constraints

1 \leq N \leq 10^{10}

0 \leq X < M \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X M

Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Sample Input 1

6 2 1001

Sample Output 1

1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

Sample Input 2

1000 2 16

Sample Output 2

6

The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.

Sample Input 3

10000000000 10 99959

Sample Output 3

492443256176507



Sample input:
6 2 1001


Sample output:
1369

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    n, x, m = map(int, input().split())
    if x == 0:
        print(0)
        return
    if x == 1:
        print(n)
        return

    d = {}
    d_idx = {}
    d_unit = {}
    idx = 0
    pow_x = x
    unit = 0
    while idx < n and pow_x not in d:
        d[pow_x] = idx
        d_idx[idx] = pow_x
        unit += pow_x
        d_unit[idx] = unit

        pow_x *= pow_x
        pow_x %= m
        idx += 1
    # x^{2^idx} = 1

    if idx == n - 1:
        print(unit)
        return
    pre_idx = d[pow_x]
    pre_unit = d_unit[pre_idx] - d_idx[pre_idx]
    iter_unit = unit - pre_unit
    ans = pre_unit + iter_unit * ((n - pre_idx) // (idx - pre_idx))
    for i in range((n - pre_idx) % (idx - pre_idx)):
        ans += d_idx[i + pre_idx]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  if tmp==0:
    break
  if tmp in a:
    break
  a.append(tmp)
#print(a)
i = 1
while a[i]!=tmp:
  i+=1
kurikaeshi = len(a) - i
goukei = sum(a[i:])
#print(goukei)
tmp=(n-(len(a)-1))
#print(tmp//kurikaeshi)
a.append(tmp//kurikaeshi * goukei)
#print(a)
tmp = tmp%kurikaeshi
if tmp!=0:
  t = sum(a[i:i+tmp])
  a.append(t)
print(sum(a))

Submission status: Runtime Error

Solution code:
n,X,m=map(int,input().split())
x=[0]*m
y=[0]*m
y[0]=X
z=[0]*(m+1)
z[X]+=1
for i in range(1,m):
    x[i]=(i**2)%m
for i in range(1,m+1):
    y[i]=x[y[i-1]]
    z[y[i]]+=1
    if z[y[i]]==2:
        e=i
        q=y[i]
        break
for i in range(len(y)):
    if y[i]==q:
        b=i
        break
l=y[b:e]
L=len(l)
s=sum(l)
#print(x)
#print(y)
#print(z)
#print(b,e)
#print(l)
#print(sum(y[:b]))
#print(((n-b)//L)*s)
#print(sum(l[:(n-b)%L]))
ans=sum(y[:b])+((n-b)//L)*s+sum(l[:(n-b)%L])
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())

if x == 0:
    print(0)
    exit()

li = [-1] * m
v = [False] * m
v2 = [False] * m
v[x] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = i ** 2 % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li[:cnt]

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[-1])
else:
    n -= len(ans_li)
    if n % len(loop_li) == 0:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
    else:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,X,M = map(int,input().split())
ans = 0
d = defaultdict(lambda:-1)
x = X%M
for n in range(M):
    if x in d:
        T = n-d[x]
        break
    else:
        d[x] = n
    x *= x
    x %= M
p = 0
y = x
for m in range(d[x],n):
    p += y
    y *= y
    y %= M

ans = 0
n = N
z = X%M
while n:
    ans += z
    n -= 1
    z *= z
    z %= M
    if z==x:
        ans += n//T*p
        n %= T
print(ans)

Submission status: Runtime Error

Solution code:
S=list(map(int,input().split()))
a=[S[1]]
for i in range(0,S[0]-1):
        if a[i]**2>10**9+7:
           a.append(((a[i]**2)%(10**9+7))%S[2])
        else:
           a.append(((a[i]**2)%S[2])
print(sum(a))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    x = {}

    ruiseki = [0] * (M + 1)

    cnt = 1
    ans = X
    c = X
    ruiseki[1] = ans
    while cnt < N:
        next = c ** 2 % M
        if next in x.keys():
            y = x[next]
            # print(ruiseki)
            # print(cnt, y)
            if N == cnt:
                print(ans + next)
                return
            loop = ruiseki[cnt] - ruiseki[y - 1]
            loopcnt = cnt - y + 1
            ans += ((N - cnt) // loopcnt) * loop
            # print(ans)
            amari = (N - cnt) % loopcnt
            # print(amari, loop, loopcnt)
            if amari != 0:
                ans += ruiseki[y - 1 + amari] - ruiseki[y - 1]
                # print(ans)
            break

        ans += next
        cnt += 1
        ruiseki[cnt] = next
        ruiseki[cnt] += ruiseki[cnt - 1]
        c = next
        x[next] = cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,X,M = map(int, open(0).read().split())
A = []
A.append(X)
B = []
for i in range(N-1):
    if pow(A[-1],2) < M:
        A.append(pow(A[-1],2))
    else:
        B.append(pow(A[-1],2,M))
        break
b = set(B)
for i in range(N-1):
    temp = pow(B[-1],2,M)
    if temp not in b:
        B.append(temp)
        b.add(temp)
    else:
        break
As = sum(A)
Bs = sum(B)
t1 = N - len(A)
dm = divmod(t1,len(B))
print(As+Bs*dm[0]+sum(B[:dm[1]]))

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    # print(A)

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1
    straight = [0 for i in range(start)]
    loop = [0 for i in range(L)]

    np = A.index(-1)

    for i in range(start):
        if i >= np:
            break
        straight[i] = straight[i-1] + A[i]


    for i in range(L):
        if start + i >= np:
            break
        loop[i] = loop[i-1] + A[start+i]

    # print(straight)
    # print(loop)

    res = 0

    if start != 0:
        if N >= start:
            res += straight[-1]
            N -= start
        else:
            res += straight[N-1]
            N = 0

    res += (N // L) * loop[-1]

    if N % L != 0:
        res += loop[N % L - 1]

    print(res)



main()

Submission status: Runtime Error

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

A = [-1 for _ in range(M*2)]  # どうせ M 回以内でループに入るので
A[0] = X

is_seen = [0 for _ in range(M)]  # is_seen[i] : i がすでに現れたか
is_seen[X] = 1

first_sum = X

for i in range(N-1):
    A[i+1] = A[i]**2 % M
    first_sum += A[i+1]
    if A[i+1] == 0:
        break
    elif is_seen[A[i+1]]:
        # すでに出現済みということで A[A.index(A[i+1])], ..., A[i] までがループであることがわかる
        loop_length = i - A.index(A[i+1]) + 1
        ind = i
        first_sum -= A[i+1]
        A_loop = A[A.index(A[i+1]):i+1]
        loop_sum = sum(A_loop)
        break
    else:
        is_seen[A[i+1]] = 1

if loop_length:
    # 残りをループで足していく
    res = N - ind  # 足さないといけない残り
    ans = first_sum + (res//loop_length) * loop_sum
    # はみ出したぶん
    if res % loop_length != 0:
        ans += sum(A_loop[:res%loop_length-1])
else:
    ans = first_sum

print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    x = {}

    ruiseki = [0] * (M + 1)

    cnt = 1
    ans = X
    c = X
    ruiseki[1] = ans
    while cnt < N:
        next = c ** 2 % M
        if next in x.keys():
            y = x[next]
            # print(ruiseki)
            # print(cnt, y)
            loop = ruiseki[cnt] - ruiseki[y - 1]
            loopcnt = cnt - y + 1
            ans += ((N - cnt) // loopcnt) * loop
            # print(ans)
            amari = (N - cnt) % loopcnt
            # print(amari, loop, loopcnt)
            if amari != 0:
                ans += ruiseki[y - 1 + amari] - ruiseki[y - 1]
                # print(ans)
            break

        ans += next
        cnt += 1
        ruiseki[cnt] = next
        ruiseki[cnt] += ruiseki[cnt - 1]
        c = next
        x[next] = cnt

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

A_history = [-1] * M
sum_history = [0] * (M + 1)
A = X
all_sum = A

sum_history[0] = A

for i in range(M):
    Anext = (A * A) % M
    all_sum += Anext
    sum_history[i + 1] = all_sum
    if A_history[A] == -1:
        A_history[A] = i
    else:
        break
    A = Anext

if i >= N:
    print(sum_history[N - 1])
else:
    cycle_start = A_history[A]
    cycle_end = i - 1
    cycle_length = cycle_end - cycle_start + 1
    cycle_time = N - cycle_start
    cycle_count = cycle_time // cycle_length
    cycle_mod = cycle_time % cycle_length
    ans = sum_history[cycle_start] + (sum_history[cycle_end + 1] - sum_history[cycle_start]) * cycle_count + \
          (sum_history[cycle_start + cycle_mod - 1] - sum_history[cycle_start])
    print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
ans = 0
loopList = [0] * 10 ** 5
startcnt = 0
loopcnt = 0
val = x
while True:
    if startcnt >= n:
        val = 0
        break
    if val >= m: break
    ans += val
    startcnt += 1
    val **= 2
while True:
    if val < m and loopcnt == 0: break
    val %= m
    if val == loopList[0]: break
    loopcnt += 1
    loopList[loopcnt-1] = val
    val **= 2
if loopcnt == 0:
    print(ans)
else:
    z = n - startcnt
    loop = z // loopcnt
    finish = z % loopcnt
    ans += sum(loopList) * loop
    ans += sum(loopList[0:finish])
    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())
N,X,M = map(int, input().split())

first_A = [X]
mod_M = [False for i in range(M)]
mod_M[0] = True
mod_M[1] = True

is_break = False
for i in range(min(N-1,M+1)):
    A_n1 = pow(first_A[-1],2)%M
    if mod_M[A_n1]:
        is_break = True
        last_num = A_n1
        break
    else:
        first_A.append(A_n1)
        mod_M[A_n1] = True

if is_break:
    if last_num == 0:
        print(sum(first_A))
    elif last_num == 1:
        nokori = N-len(first_A)
        print(sum(first_A)+nokori)
    else: # roop
        loop_idx = first_A.index(last_num)
        first_A, second_A = first_A[:loop_idx], first_A[loop_idx:]
        roop = int((N-len(first_A))/len(second_A))
        nokori_kaisuu = (N-len(first_A)) - (roop*len(second_A))
        if nokori_kaisuu == 0:
            print(sum(first_A)+(sum(second_A)*roop))
        else:
            print(sum(first_A)+(sum(second_A)*roop)+sum(second_A[:nokori_kaisuu]))
else:
    print(sum(first_A))

Submission status: Runtime Error

Solution code:
"""MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWO:,'..'xXWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO. .:kOo.,kNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO. .lNWWo..lXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MNOxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMMMMWKxoloxKWNc  .:xxd;  ,dxxxkXMXkxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMM
MKc''''''''''''''''.  ..'''''.   .''''.  .''MMMWx..,:. .xXo''.  .''.  ..'';kMk;'''''.  .'.''.  .''''''.  ..''.   .''MM
MWNXNNNNNNNNNNNNNNNO' ;KNNNNNKo. cKNNNd. lXNMMMK; ,0Wx. :NWXXl .dNNO' ;KNNNWMWNNNNNXc .kNNNNx. cXNNNNNO' ;KNN0; 'ONNMM
MMMMMMMMMMMMMMMMMWM0' :NMMMMWMX: .OMWWx. oWMMMMWx. ';. .dNMWWo .xMM0' :NWWMMMMMMMMWWl .OMMMWk. lWWMMWM0' ;XMMX: ,KMMMM
MMMMMMWMWkccccccccc;. :NMWNNNKd. :XMMWx. oWMMMWKo. .',. .,ldx; .dMM0' :NMMMMMMMNNWMWl .OMMMWk. lWMMMMM0' ;XMMX: ,0MMMM
MMWXKNWMWxcc,. .;cc;. :XMk,''..'lKWMMWx. oWMNx:. .lONNKxl.     .xMM0' :NMMMMMM0:,oKO' ,KMMMMk. lWWNkoc,. .;::;. ,KMMMM
MMXc.lXMMWWWNd..xWM0' :NM0;  ;kXWMMMWNl  oWMK:.;xXWWMWXx:. ,c' .dMM0' :NMMMMMMKc. ...;kWMMMMk. lWWc .:;. .clc:. ,KMMMM
MWWx. lXMWMMMK, lWM0' :NMMNx'.,ldxxoc'   oWMWNKNWWWN0o' .:kNWo .dMM0' :NMMMMMMMNO;  ,OWWWMMMk. lWM' lXx. lNMMX: ,KMMMM
MMMWk'.,xKNX0c..kWM0' :NMMMMNkl;,'',:l:  oWMMMMMWMWO' 'l0WMWWo .xMM0' :NMMMMMMMMMNd. .oXWMMMk. lWMd.....;0WMMX: ,KMMMM
MMMMWKo'...'..:kWMM0' :NMMMMMMMWWNNWWWx. oWMMMMMMMMWOxXWMWMWWo .xMM0' :NMMMMMMMMMMMKl. ,kNMMk. lWMWKkxx0NMWMMX: ,KMMMM
MMMMMMMN0kxk0XNWMMWKl;xNMMMMMMMMMMMMWM0c;kWMMMMMMMMMMMWWMMMMWk;:OMMXl,dNMMMMMMMMMMMMWO; .dNM0c;kWWMMMMMMMMMMMNd,oXMMMM
MMMMMMMMWWMWMMMMMMMMMWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWWMMWWMMWMMMMMMMMMMMMMMNkxKWMMWWMMMMMMMMMMMMMMWMMWMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM"""


#				 Author: Udit "luctivud" Gupta @ https://www.linkedin.com/in/udit-gupta-1b7863135/					 #


import math;   		from collections import *
import sys;   		from functools import reduce
import time;   		from itertools import groupby

# sys.setrecursionlimit(10**6)

# def input()         : return sys.stdin.readline()
def get_ints()      : return map(int, input().strip().split())
def get_list()      : return list(get_ints())
def get_string()    : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args)  : return print(*args, end=" ")


DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (+1, -1)] 
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
              (+1, +1), (+1, +0), (+1, -1), (+0, +1)]



# MAIN >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

# se = set()
# n = 16; x = 2; m = 1001
# for i in range(n):
# 	print(x % m, i)
# 	if (x % m) in se:
# 		print(x % m, i)
# 	else:
# 		se.add(x % m)
# 	x **= 2;
# 	x %= m


n, x, m = get_ints()
prefix_sum = [0]
found = set()
d = dict()
ind = 1; doneInd = 1;
for i in range(n):
	if (x % m) not in found:
		found.add(x % m)
		d[x % m] = i
		prefix_sum.append(prefix_sum[-1] + (x % m))
	else:
		ind = d[x % m]
		doneInd = i
		break
	x **= 2
	x %= m
# print(ind, doneInd, prefix_sum[ind])
# print(prefix_sum)
# print(prefix_sum)

lastset = prefix_sum[-1] - prefix_sum[ind];
offset = prefix_sum[ind]

sz = len(prefix_sum) - ind - 1

rem = n - ind
ans = offset
ans += lastset * (rem // sz)
ans += prefix_sum[ind + rem % sz] - offset
# print(sz, lastset, rem)

print(ans)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
a = [0]*N
a[0] = X
for i in range(N-1):
    a[i+1]=a[i]**2%M
print(sum(a))

Submission status: Runtime Error

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

ans = 0
roop_init = 0
roop_sum = 0
roop_len = 0
x = X
ans += x
flug = False    # 周期を数えるフラグ
for i in range(2, N+1):
    old_x = x
    x = old_x**2 % M
    if x == 0:
        break
    if old_x**2 >= M and not flug:
        # print(old_x, x)
        flug = True
        roop_init = x
        roop_sum = x
        roop_len = 1
    elif x == roop_init:
        # print(i)
        ans += (N - (i-1)) // roop_len * roop_sum
        for j in range((N - (i-1)) % roop_len):
            if j != 0:
                old_x = x
                x = old_x**2 % M
            ans += x
        print(ans)
        break
    elif flug:
        roop_len += 1
        roop_sum += x
    ans += x
else:
    print(ans)
print(i, roop_init, roop_sum, roop_len)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
a = [0 for i in range(M+1)]
b = [X]
a[X-1] = 1

for i in range(min(N, M)):
  X = X**2%M
  a[X-1] += 1
  b.append(X)
  if a[X-1] > 1:
    break

if len(b) == N:
  print(sum(b))

else:
  ls = b.index(b[-1])
  bloop = b[ls:-1]
  ans = 0
  if ls > 0:
    for i in range(ls):
      ans += b[i]
  loop = (N-ls)//len(bloop)
  ans += sum(bloop) * loop
  if (N-ls)%len(bloop) != 0:
    for i in range((N-ls)%len(bloop)):
      ans += bloop[i]
  print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, X, M = map(int, input().split())
    A = [X % M]
    setA = set(A)

    while True:
        a = (A[-1] ** 2) % M
        if a in setA:
            break
        A.append(a)
        setA.add(a)

    pre = A.index(a)
    length = len(A)
    ans = 0
    loop = A[pre:]
    for i in range(1,N+1):
        if i-1 < pre:
            _ans = A[i-1]
        else:
            _ans = loop[(i-1 - pre) % length]
        ans += _ans
        _ans

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

A = [-1 for _ in range(M)]  # どうせ M 回以内でループに入るので
A[0] = X

is_seen = [0 for _ in range(M)]  # is_seen[i] = i がすでに現れたか
is_seen[X] = 1

summation = X
loop_length = -1

for i in range(N-1):
    A[i+1] = A[i]**2 % M
    summation += A[i+1]
    if A[i+1] == 0:
        break
    elif is_seen[A[i+1]] == 1:
        # すでに出現済みということで A[0], ..., A[i] までがループであることがわかる
        loop_length = (i+1) - A.index(A[i+1])
        ind = i
        summation -= A[i+1]
        break
    else:
        is_seen[A[i+1]] = 1

if loop_length != -1:
    # 残りをループで足していく
    A_loop = A[A.index(A[ind+1]):ind+1]
    loop_sum = sum(A_loop)
    res = N - ind  # 足さないといけない残り
    ans = summation + (res//loop_length) * loop_sum
    # はみ出したぶん
    if res % loop_length != 0:
        ans += sum(A_loop[:res%loop_length-1])
else:
    ans = summation

print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
U = [0] * (M + 10)
U[X] = 1
S = [0] * (M + 10)
S[1] = X
v = X
l = r = 0  # [l,r) で巡回
cycle_sum = 0
for i in range(2, M + 1):
    v = (v * v) % M
    if U[v]:
        l = U[v]
        r = i
        cycle_sum = S[i - 1] + v - S[l]
        break
    U[v] = i
    S[i] = S[i - 1] + v
if N < l:
    print(S[N])
    exit()

ans = S[l - 1]
N -= l - 1
d, m = divmod(N, r - l)
ans += d * cycle_sum
ans += S[l + m - 1] - S[l - 1]
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
A = [X]
ret = X
k = X
for i in range(N):
  k = (k * k) % M
  ret += k
  
  if k in A:
    A.append(k)
    break
  A.append(k)
if len(A) == N:
  print(ret)
else:
  i = A.index(A[-1])
  s_rep = sum(A[i:-1])
  a_rep = A[i:-1]
  s_init = sum(A[:i])
  k = len(a_rep)
  l_ = N - i
  ret = s_init + s_rep * (l_ // k) +sum( a_rep[:(l_ % k)])
  print(ret)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
ans=0
p=0
l=[x]
if x%m==0:
  print(x)
else:
  for i in range(1,n):
    s=(l[i-1]**2)%m
    if s==0:
      p=1
      break
    if s in l:
      break
    else:
      l.append(s)
  if p==0:
    t=sum(l[1:])
    k=(n-1)//(len(l)-1) #ループ何回回るか
    j=(n-1)%(len(l)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  else:
    print(sum(l))

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = 0
a = []
y = []
a.append(x)
ans += x
y.append(x%m)
for _ in range(N-1):
    a.append(y[-1]**2%m)
    ans += y[-1]**2%m
    y.append(a[-1]%m)
    if y[-1] in y[:-1]:
        ans -= a[-1]
        i = y[:-1].index(y[-1])
        h=len(y)-1
        one_loop = h-i
        loop_list = a[i:-1]
        break
        
ato= n-_-1
ans+=(ato//one_loop)*sum(loop_list)
ans += sum(loop_list[:(ato%one_loop)])

print(ans)

Submission status: Runtime Error

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

A = [-1 for _ in range(M)]  # どうせ M 回以内でループに入るので
A[0] = X

is_seen = [0 for _ in range(M)]  # is_seen[i] = i がすでに現れたか
is_seen[X] = 1

summation = X
loop_length = -1

for i in range(N-1):
    A[i+1] = A[i]**2 % M
    summation += A[i+1]
    if A[i+1] == 0:
        break
    elif is_seen[A[i+1]] == 1:
        # すでに出現済みということで A[0], ..., A[i] までがループであることがわかる
        loop_length = (i+1) - A.index(A[i+1])
        ind = i
        summation -= A[i+1]
        break
    else:
        is_seen[A[i+1]] = 1

if loop_length != -1:
    # 残りをループで足していく
    A_loop = A[A.index(A[ind+1]):ind+1]
    loop_sum = sum(A_loop)
    res = N - i  # 足さないといけない残り
    ans = summation + (res//loop_length) * loop_sum
    # はみ出したぶん
    if res % loop_length != 0:
        ans += sum(A_loop[:res%loop_length-1])
    # print(f"ans = {summation} + {(res//loop_length)} * {loop_sum} + {sum(A_loop[:res%loop_length-1])}")
else:
    ans = summation

print(ans)

# print(f"summation = {summation}, loop_length = {loop_length}")
# print(f"{A[:ind+1+1]}...")

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
tmp=x
L=[]
for i in range(n):
    tmp=tmp**2%m
    if tmp not in L:
        L.append(tmp)
    else:
        break
times=(n-2)//(len(L)-1)
loss=(n-2)%(len(L)-1)
ans=x+L[0]+sum(L[1:])*times
for i in range(loss):
      ans+=L[i+1]
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
U = [0] * (M)
U[X] = 1
S = [0] * (M)
S[1] = X
v = X
l = r = 0  # [l,r) で巡回
cycle_sum = 0
for i in range(2, M + 1):
    v = (v * v) % M
    if U[v]:
        l = U[v]
        r = i
        cycle_sum = S[i - 1] + v - S[l]
        break
    U[v] = i
    S[i] = S[i - 1] + v
if N < l:
    print(S[N])
    exit()

ans = S[l - 1]
N -= l - 1
d, m = divmod(N, r - l)
ans += d * cycle_sum
ans += S[l + m - 1] - S[l - 1]
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())

li = [-1] * m
v = [False] * m
v2 = [False] * m
v[x+1] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = i ** 2 % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li[:cnt]

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[n-1] + loop_li[0])
else:
    n -= len(ans_li)
    if n % len(loop_li) == 0:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
    else:
        print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])

Submission status: Runtime Error

Solution code:
r = input()
s = r.split(" ")
n = int(s[0])
x = int(s[1])
m = int(s[2])
sum = x
for i in range(0,n-1):
	x = (x*x)%m
    sum = sum + x
print(sum)

Submission status: Runtime Error

Solution code:
#
import sys
import math
import itertools


# 整数をいくつか入力
n,x,m = (int(i) for i in input().split())

if n < 100000:
    b=0
    for i in range(n):
        b += x
        #print(x)
        x = (x*x) %m
    print(b)
else:
    ll=[0]*100000
    s=0
    for i in range(100000):
        ll[i]=x
        s += x
        x = (x*x) %m
    for i in range(99998,-1,-1):
        if ll[i]==ll[99999]:
            term=99999-i
    p=(n-100000)//term
    q=(n-100000)%term
    r=0
    for i in range(term):
        r += ll[100000-term+i]
    s += r * p
    for i in range(q):
        s += ll[100000-term+i]
    print(s%)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=list()
ans=0
s=n
for i in range(n):
    ans+=x
    a.append(x)
    x=(x**2)%m
    if x in a:
        s=a.index(x)
        break

sum=0
if s!=n:
    for i in range(s, len(a)):
        sum+=a[i]

ans+=sum*(((n-s)//(len(a)-s))-1)

z=(n-s)%(len(a)-s)
for i in range(z):
    ans+=a[s+i]
print(ans)

Submission status: Runtime Error

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

A = [-1 for _ in range(M)]  # どうせ M 回以内でループに入るので
A[0] = X

is_seen = [0 for _ in range(M)]  # is_seen[i] = i がすでに現れたか
is_seen[X] = 1

summation = X
loop_length = -1

for i in range(N-1):
    A[i+1] = A[i]**2 % M
    summation += A[i+1]
    if A[i+1] == 0:
        break
    elif is_seen[A[i+1]] == 1:
        # すでに出現済みということで A[0], ..., A[i] までがループであることがわかる
        loop_length = (i+1) - A.index(A[i+1])
        ind = i
        summation -= A[i+1]
        break
    else:
        is_seen[A[i+1]] = 1

if loop_length != -1:
    # 残りをループで足していく
    A_loop = A[A.index(A[ind+1]):ind+1]
    loop_sum = sum(A_loop)
    res = N - i  # 足さないといけない残り
    ans = summation + (res//loop_length) * loop_sum + sum(A_loop[:res%loop_length-1])
    # print(f"ans = {summation} + {(res//loop_length)} * {loop_sum} + {sum(A_loop[:res%loop_length-1])}")
else:
    ans = summation

print(ans)

# print(f"summation = {summation}, loop_length = {loop_length}")
# print(f"{A[:ind+1+1]}...")

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1
    straight = [0 for i in range(start+1)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]

    for i in range(L):
        loop[i] = loop[i-1] + A[start+i]

    res = 0

    if start != 0:
        if N >= start:
            res += straight[-1]
            N -= start
        else:
            res += straight[N-1]
            N = 0

    res += (N // L) * loop[-1]

    if N % L != 0:
        res += loop[N % L - 1]

    print(res)



main()

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
a = [0 for i in range(M)]
b = [X]
a[X-1] = 1

for i in range(min(N, M)):
  X = X**2%M
  a[X-1] += 1
  b.append(X)
  if a[X-1] > 1:
    break

if len(b) == N:
  print(sum(b))

else:
  ls = b.index(b[-1])
  bloop = b[ls:-1]
  ans = 0
  if ls > 0:
    for i in range(ls):
      ans += b[i]
  loop = (N-ls)//len(bloop)
  ans += sum(bloop) * loop
  if (N-ls)%len(bloop) != 0:
    for i in range((N-ls)%len(bloop)):
      ans += bloop[i]
  print(ans)

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]



def main():
    N, X, M = read_values()
    F = [-1] * M

    A = X
    t = 0
    while F[A] < 0:
        F[A] = t
        A = pow(A, 2, M)
        t += 1
    
    if t == 1:
        print(X * N)
    else:
        d = (N - F[A]) // (t - F[A])
        r = (N - F[A]) % (t - F[A]) + F[A]

    K = 0
    for i in range(F[A], t):
        K += A
        A = pow(A, 2, M)
    
    K *= d

    A = X
    for _ in range(r):
        K += A
        A = pow(A, 2, M)

    print(K)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=[0]*(m+2)
cnt=[0]*(m+2)
a[1],f=x,x
cnt[f]=1
for i in range(2,m+1):
  f=f*f%m
  a[i]=f
  if cnt[f]==0:
    cnt[f]=1
  else:
    break
ind=a[1:].index(f)+1
ans=sum(a[:ind])+sum(a[ind:i])*((n-ind+1)//(i-ind))
p=(n-ind+1)%(i-ind)
ans+=sum(a[ind:ind+p])
print(ans)

Submission status: Runtime Error

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

appearance = [0] * (M + 1)
cum_sum = [0]
A = X
appearance[A] = 1
cum_sum.append(A)
for a in range(2, N + 1):
    A = (A**2)%M
    if appearance[A] != 0:
        n = a - 1
        break
    appearance[A] = a
    cum_sum.append(cum_sum[-1] + A)
else: n = a

k = appearance[A]
l = (N - n) // (n - k + 1)
m = (N - n) - (n - k + 1)*l + k - 1

ans = cum_sum[n] + (cum_sum[n] - cum_sum[k - 1])*l + cum_sum[m] - cum_sum[k - 1]
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=list()
ans=0
for i in range(n):
    ans+=x
    a.append(x)
    x=(x**2)%m
    if x in a:
        s=a.index(x)
        break

sum=0
for i in range(s, len(a)):
    sum+=a[i]

ans+=sum*(((n-s)//(len(a)-s))-1)

z=(n-s)%(len(a)-s)
for i in range(z):
    ans+=a[s+i]
print(ans)

Submission status: Runtime Error

Solution code:
if __name__ == '__main__':
    n, k,x = map(int, input().split())
    mod = 998244353
    ans = 0
    index=0
    a= k %x
    dict={}
    for i in range(n):
        if a not in dict.values():
            ans += a
            index += 1
            dict[i]=a
            a = a*a % x
        else:
            break

    key = [k for k, v in dict.items() if v == a][0]
    count=len(dict) -key
    n2 = n- len(dict)
    n3 = n2 // count
    n4 = n2 % count
    count2=0
    if key <= count//2:
        for i in range(key):
            count2+=dict[i]
        ans+=n3*(ans-count2)
    else:
        for i in range(count-key):
            count2+=dict[count-i]
        ans+=n3*(ans-count2)


    for i in range(n4):
        ans+=dict[key+i]

    print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=[0]*(m+2)
cnt=[0]*(m+2)
a[1],f=x,x
cnt[f]=1
for i in range(2,m):
  f=f*f%m
  a[i]=f
  if cnt[f]==0:
    cnt[f]=1
  else:
    break
ind=a[1:].index(f)+1
ans=sum(a[:ind])+sum(a[ind:i])*((n-ind+1)//(i-ind))
p=(n-ind+1)%(i-ind)
ans+=sum(a[ind:ind+p])
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
A = [X]
ret = X
k = X
for i in range(N):
  k = (k * k) % M
  ret += k
  
  if k in A:
    A.append(k)
    break
  A.append(k)
if len(A) == N:
  print(ret)
else:
  i = A.index(A[-1])
  s_rep = sum(A[i:])
  a_rep = A[i:-1]
  s_init = sum(A[:i])
  k = len(a_rep)
  l_ = N - i
  ret = s_init + s_rep * (l_ // k) +sum( a_rep[:(l_ % k)])
  print(ret)

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1
    straight = [0 for i in range(start+1)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]

    for i in range(L):
        loop[i] = loop[i-1] + A[start+i]

    res = 0

    if N >= start:
        res += straight[-1]
        N -= start
    else:
        res += straight[N-1]
        N = 0

    res += (N // L) * loop[-1]

    if N % L != 0:
        res += loop[N % L - 1]

    print(res)



main()