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

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

if N == 1:
    print(X)
    exit()

A = [-1] * (10**5 + 1)
A[1] = X



S = set([X])
i = 2
while True:
    A[i] = ((A[i - 1])**2) % M
    if A[i] in S:
        break
    S.add(A[i])
    i += 1



end_idx = i - 1
start_idx = 0
for start_idx in range(i):
    if A[start_idx] == A[i]:
        break

num_circles = end_idx - start_idx + 1


A[0] = 0
if start_idx > N:
    ans = sum(A[:N + 1])
    print(ans)
    exit()



v1 = sum(A[:start_idx])

remain_N = N - start_idx + 1


div, mod = divmod(remain_N, num_circles)


sum_circles = sum(A[start_idx:end_idx + 1])


v2 = sum_circles * div

if mod == 0:
    v3 = 0
else:
    
    v3 = sum(A[start_idx:start_idx + mod])

ans = v1 + v2 + v3
print(ans)

Solution (Python):


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

first_A = [X]
mod_M = [False for i in range(M+1)]
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: 
        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))

Solution (Python):
n, x, m = map(int, input().split())
init, cr = x, x
hist = [m+1, x]
for idx in range(2, n + 1):
    cr = (cr ** 2) % m
    if cr in hist:
        idx_bef = hist.index(cr)
        remains = n - idx + 1
        ans = sum(hist[1:])
        sum_period = sum(hist[idx_bef:])
        period_num = idx - idx_bef
        ans += sum_period * (remains // period_num)
        ans += sum(hist[idx_bef: idx_bef + remains % period_num])
        print(ans)
        exit()
    else:
        hist.append(cr)
print(sum(hist[1:]))

Solution (Python):
from collections import defaultdict
d = defaultdict(int)

n,x,m= map(int, input().split())
ans=0
v=[]
cnt=x
for i in range(m+10):
    if cnt==0 or i==n:
        print(ans)
        exit()

    elif d[cnt]==0:
        v.append(cnt)
        ans += cnt
        d[cnt]=i
        cnt = pow(cnt, 2, m)
    else:
        
        y=d[cnt]
        break
u=0
for i in range(y,len(v)):
    u+=v[i]
l=len(v)-y
xx=(n-len(v))//l
yy=(n-len(v))%l
ans+=xx*u+sum(v[y:y+yy])
print(ans)

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

appearance = [0] * (M + 1)
cum_sum = [0]
A = X
appearance[A] = 1
cum_sum.append(A)
a = 1
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[a - 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)

Solution (Python):
def main():
    N, X, M = map(int, input().split())
    l = [X]
    lset = set(l)
    ans = X
    bf = X
    for i in range(N):
        nx = bf**2%M
        if nx in lset:
            break
        ans += nx
        lset.add(nx)
        l.append(nx)
        bf = nx
    st = l.index(nx)
    retry = l[st:]
    remain = N - len(l)
    ans += (remain//len(retry))*sum(retry) + sum(retry[:remain%len(retry)])
    print(ans)

if __name__ == "__main__":
    main()

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

mods = [0 for i in range(M)]
vals = []
for i in range(1, M+2):
  if i == 1:
    p = X
  else:
    p = p**2 % M
  
  if mods[p] > 0:
    break
  else:
    mods[p] = i
    vals.append(p)
    if i == N:
      print(sum(vals))
      exit()

len_loop = i - mods[p]
sum_answer = sum(vals)
N_res = N - len(vals)
sum_answer += sum(vals[mods[p]-1:]) * (N_res // len_loop)
N_res = N_res % len_loop
sum_answer += sum(vals[mods[p]-1:mods[p]-1+N_res])

print(sum_answer)

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush

from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time

starttime = time.time()

mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    
    sys.stdin = open("input.txt", "r")
    
except:
    pass



n,x,m=L()
A=[x]
d={}
k=1
d[x]=1
while(A[-1]!=0 and k<n):
    y=A[-1]*A[-1]%m
    if y in d:
        break
    else:
        d[y]=1
    A.append(y)
    k+=1
if A[-1]==0:
    print(sum(A))
elif k==n:
    print(sum(A))
elif k<n:
    

    
    
    
    
    
    
    
    
    

    
    pref=0
    ans=0
    rem=-2
    cnt=-1
    
    for i in range(len(A)):
        if A[i]==y:
            ans+=pref
            pref=0
            cnt=0
            rem=(n-i)%(len(A)-i)
            
        if rem==cnt:
            ans+=pref
        if cnt>=0:
            cnt+=1
        pref+=A[i]
    ans+=pref*((n-k+cnt)//(cnt))
    print(ans)

endtime = time.time()

Solution (Python):
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
U = [0] * (M + 10)
U[X] = 1
S = [0] * (M + 10)
S[1] = X
v = X
l = r = 0  
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)

Solution (Python):
n, x, m = map(int, input().split())
a = [-1]*10**5; a[x%m] == 0; b = [x%m]
for i in range(1, n):
    x = x**2%m
    if a[x%m] == -1:
        a[x%m] = i; b.append(b[-1]+x%m)
    else:
        s = a[x%m]-1; g = i-1
        print((b[g]-b[s])*((n-s-1)//(g-s))+b[s+(n-s-1)%(g-s)])
        break
else: print(b[-1])

Solution (Python):
N, X, M = list(map(int, input().split()))
i = 1
a = X
s = 0
L = []
while i < N and a > 0:
    L.append(a)
    s += a
    a = (a**2) % M
    if a in L:
        j = L.index(a)
        break
    i += 1
else:
    s += a
    print(s)
    exit()


t = sum(L[:j])
L = L[j:]
u = s-t
N = N-j
v = t+u*(N//(i-j))
if N % (i-j) == 0:
    pass
else:
    v += sum(L[:N % (i-j)])
print(v)

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N, X, M = inpl()
hisS = [0] * M
pos = [-1] * M
c = S = hisS[0] = X
pos[X] = 0
for i in range(1, min(M+1,N)):
    c = c * c % M
    S += c
    if pos[c] >= 0:
        prev = pos[c]
        period = i - prev
        q = (N - prev) // period
        r = (N - prev) % period
        if prev == 0 and r == 0:
           ans = (S - hisS[prev]) * q
        else:
            ans = (S - hisS[prev]) * q + hisS[prev+r-1]
        print(ans)
        break
    else:
        hisS[i] = S
        pos[c] = i
else:
    print(S)
    exit()

Solution (Python):
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]   

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

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

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

LOOP = [X]
wk = X
s = set()
s.add(X)
flg = True
for i in range(N-1):
  a = wk * wk % M
  if a == 0:
    print(sum(LOOP))
    exit(0)
  if a in s:
    wk = a
    flg = False
    break
  LOOP.append(a)
  s.add(a)
  wk = a

if flg:
  print(sum(LOOP))
else:
  for i in range(len(LOOP)):
    if LOOP[i] == wk:
      beg_i = i
      break
  fin_i = len(LOOP) -1
  ans = sum(LOOP[:beg_i])
  N -= beg_i
  L = LOOP[beg_i:]
  LS = len(L)
  
  ans += sum(L) * (N//LS)
  N = N % LS
  ans += sum(L[:N])
  print(ans)

Solution (Python):
n,x,m = map(int, input().split())
visited=set()
from collections import defaultdict
ans=0
cnt=0
now=x
last=defaultdict(list)
while cnt!=n:
    cnt+=1
    if now in visited:
        break
    visited.add(now)
    last[now]=[ans,cnt]
    ans+=now

    now=(now**2) % m
    if now==0:
        print(ans)
        exit()

if cnt==n:
    print(ans)
    exit()

looplen=cnt-last[now][1]
looppoint=ans-last[now][0]
loopcnt,nokori = divmod(n-cnt,looplen)
ans+=(loopcnt*looppoint)
ans+=now

for i in range(nokori):
    now=(now**2) % m
    ans+=now

print(ans)

Solution (Python):
N, X, M = map(int, input().split())
checklist = [True] * 100000
ind = 0
l = [X]
while True:
  t = l[-1] ** 2 % M
  if checklist[t]:
    l.append(t)
    checklist[t] = False
  else:
    ind = l.index(t)
    break
S = sum(l[ind:])
L = len(l)
ans = 0
if N <= L:
  ans = sum(l[:N])
else:
  ans = sum(l)
  N -= L
  ans += S * (N // (L - ind))
  ans += sum(l[ind:ind+(N % (L - ind))])
print(ans)

Solution (Python):
def main():
    n, x, m = map(int, input().split())
    a = x
    s = a
    seen = {a}
    seq = [a]
    for i in range(n - 1):
        if a == pow(a, 2, m):
            print(s + a * (n - i - 1))
            return
        else:
            a = pow(a, 2, m)
            if a in seen:
                si = seq.index(a)
                sl = i - si + 1
                ps = s - sum(seq[:si])
                ln = (n - i - 1) // sl
                lm = (n - i - 1) % sl
                print(s + ps * ln + sum(seq[si:si + lm]))
                return
            s += a
            seen.add(a)
            seq.append(a)
    print(s)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def naive(N, X, M):
    ans = X
    ans_prev = X
    for i in range(2, N + 1):
        an1 = ans_prev % M
        an1 = pow(an1, 2, M)
        ans += an1
        ans_prev = an1
    return ans

def doubling(N, X, M):
    ans = X
    ans_prev = X
    A = [X]
    computed = set({})

    for i in range(2, N + 1):
        an1 = ans_prev % M
        an1 = pow(an1, 2, M)
        if an1 in computed:
            breakA = an1
            break
        A.append(an1)
        computed.add(an1)
        ans_prev = an1

    
    num_break = len(A)
    index = A.index(breakA)
    num_length = len(A) - index
    total = sum(A[:index])
    repeat_length = (N - index) // num_length
    remain_length = (N - index) % num_length
    total_sub = sum(A[index:]) * repeat_length
    total += total_sub
    if remain_length > 0:
        sub = naive(remain_length, breakA, M)
        total += sub    
    return total


def solve(N, X, M):
    return -1

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

    if N < 10 ** 7:
        print(naive(N, X, M))
    else:
        print(doubling(N, X, M))
        

if __name__ == '__main__':
    main()

Solution (Python):
import sys
N,X,M=map(int, sys.stdin.readline().split())

A=[]
A.append(X)
visit={}
for i in range(M+1):
    X=pow(X,2,M)
    if X not in visit:
        visit[X]=1
        A.append(X)
    else:
        break
loop_point=A.index(X)
notloop=A[:loop_point]
loop=A[loop_point:]

len_notloop=len(notloop)
len_loop=len(loop)


SUM_notloop=[0]
for x in notloop:
    SUM_notloop.append(SUM_notloop[-1]+x)


SUM_loop=[0]
for x in loop:
    SUM_loop.append(SUM_loop[-1]+x)

ans=0
if len_notloop<N:
    ans+=SUM_notloop[-1]
    N-=len_notloop
    sho,amari=N/len_loop,N%len_loop
    ans+=SUM_loop[-1]*sho
    ans+=SUM_loop[amari]
elif N<=len_notloop:
    ans=SUM_notloop[N]
print ans

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

term_set={X}
term_list=[X]
for i in range(1,N):
  term1=term_list[-1]
  term2=term1**2%M
  term_list.append(term2)
  if term2 in term_set:
    break
  else:
    term_set.add(term2)



if len(term_list)==N:
  print(sum(term_list))
else:
  c2=len(term_list)-1
  c1=term_list.index(term_list[-1])
  
  
  answer=sum(term_list[:c1])
  sum_cycle=sum(term_list[c1:c2])
  
  num_cycle=(N-c1)//(c2-c1)
  rem_cycle=(N-c1)%(c2-c1)
  answer+=sum_cycle*num_cycle
  answer+=sum(term_list[c1:c1+rem_cycle])
  print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque, defaultdict





def solve():
    N, X, M = MI()
    def f(x): return x % M
    

    ans = 0
    r = [0] * (M+1)
    p = 1
    q = 0
    pre = X
    
    
    S = [X]
    for i in range(1, N):
        tmp = f(pre ** 2) % M
        
        if r[tmp]:
            
            left = N - r[tmp]
            loop = i - r[tmp]
            
            p, q = left // loop, left % loop
            
            
            ans = S[r[tmp]-1]
            ans += p * (S[i-1] - S[r[tmp]-1])
            if q > 0:
                ans += (S[r[tmp]+q-1] - S[r[tmp]-1])
            print(ans)
            
            return 
        pre = tmp
        r[tmp] = i
        
        S.append(tmp + S[i-1])
    else:
        
        print(S[N-1])



if __name__ == '__main__':
    solve()

Solution (Python):
N,X,M = map(int,input().split())
A = [100001]*(2*(10**5)+100)
A[1] = X
S = {X}
ans = X
for i in range(2,min(2*M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  

if N == 1:
  print(X)
  exit()
elif i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  if i == j:
    print(ans)
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)

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

r = [0] * (m)

r[x] = 1
a = x

t = 0
u = 0

s = [0, x]

for i in range(2, m+2):

    a = (a ** 2) % m
    s.append(s[-1] + a)

    if r[a] == 0:
        r[a] = i
    else:
        t = i - r[a]
        u = r[a]
        break

if u >= n:
    print(s[n])

else:
    
    p = (n - (u-1)) // t
    q = (n - (u-1)) % t

    ans = s[u-1+ q] + p * (s[u+t] - s[u])

    print(ans)

Solution (Python):
n,x,m=map(int,input().split())
l=[x]
c=1
d=-1
f=0
while(x>0 and c<n):
    g=(x*x)%m
    d=g
    if(g in l):
        f=1
        break
    l.append(g)
    x=g
    c+=1
s=sum(l)
if(f==1):
    r=l.index(g)
    o=(n-c)//(c-r)
    t=(n-c)%(c-r)
    s+=o*(sum(l[r:]))+sum(l[r:r+t])
print(s)

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

A=[0,X]
D={}
D[X]=1
for i in range(2,10**7):
    A.append((A[-1]**2)%M)
    if A[-1] not in D:
        D[A[-1]]=i
    else:
        R=i
        L=D[A[-1]]
        break
    



    
Front=L-1

if N<=Front:
    print(sum(A[:N+1]))
    exit()
N-=Front
X=N//(R-L)
Y=N%(R-L)

if Y>0:
    print(sum(A[:Front+1])+X*sum(A[L:R])+sum(A[L:L+Y]))
else:
    print(sum(A[:Front+1])+X*sum(A[L:R]))

Solution (Python):
n,x,m=map(int,input().split())
ans=x
totol=n
was=[0]*m
was[x]=1
cs=x
cr=1
n-=1
seq=[x]
while n>0:
	cs=cs*cs%m
	seq.append(cs)
	cr+=1
	n-=1
	if was[cs]:
		if cs<=1:exit(print(ans+cs*(n+1)))
		res=sum(seq[:was[cs]-1])
		totol-=was[cs]-1
		loop=cr-was[cs]
		sumonloop=sum(seq[was[cs]:cr])
		res+=totol//loop*sumonloop
		for i in range(totol%loop):
			res+=cs
			cs=cs*cs%m
		exit(print(res))
	else:was[cs]=cr
	ans+=cs
print(ans)
'''
492443256176507
9 2 7

26

'''

Solution (Python):
N, X, M = map(int,input().split())
A = [X]
As = set(A)
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in As:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
        As.add(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)

Solution (Python):

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
        
        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)

Solution (Python):
def main():
    n,x,m = map(int,input().split())
    R = [x]
    g = set([x])
    for i in range(1,min(m,n)):
        x = x**2 % m
        if not x in g:
            R.append(x)
            g.add(x)
        else:
            break
    
    R_ac = [0]*(len(R)+1)
    for i in range(len(R)):
        R_ac[i+1] = R_ac[i] + R[i]

    j = R.index(x)
    ct = n
    
    ans = R_ac[j]
    ct-=j

    q = ct//(len(R)-j)
    ans+= q*(R_ac[-1]-R_ac[j]) 
    ct-=q*(len(R)-j)

    ans+= R_ac[j+ct] - R_ac[j]

    print(ans)
main()

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]









n,x,m = MI()
li = [x]
ans = 0
b = 0
for i in range(1,n):
    k =  pow(x,2,m)
    if k in li:
        b = 1
        ind = li.index(k)
        break
    li.append(k)
    x = k
    
if b == 0:
    ans = sum(li)
else:
  
  
  T = len(li) - ind
  ans += sum(li[:ind])
  
  n = n-ind
  q = n//T
  S = sum(li[ind:])
  r = n%T
  ans += q*S + sum(li[ind:ind+r])
print(ans)

Solution (Python):
N, X, M = map(int, input().split())
from collections import defaultdict
check = defaultdict(int)
L = [0,X]
L_ans = [0,X]
roop_end = 0

ans = X

old_a = X
for i in range(2,N+1):
  a = (old_a**2)%M
  ans += a
  old_a = a
  L.append(a)
  L_ans.append(ans)
  
  if check[a] != 0:
    roop_first = check[a]
    roop_end = i
    roop_iter = roop_end - roop_first
    ans = L_ans[roop_first - 1]
    roop_first_ans = L_ans[roop_first]
    roop_end_ans = L_ans[roop_end]
    roop_plus = roop_end_ans - roop_first_ans
    break
  else:
    check[a] = i
if roop_end == 0:
  print(ans)
else:
  roop_phase = N - roop_first + 1
  roop_num = roop_phase // roop_iter
  ans += roop_plus * roop_num
  roop_addition = roop_phase % roop_iter
  addition = L_ans[roop_first - 1 + roop_addition] - L_ans[roop_first - 1]
  ans += addition
  print(ans)

Solution (Python):
import sys
import math
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N,X,M = MI()


if M == 1:
    print(0)
    exit()

flag = [-1]*M
Z = [X]
flag[X] = 1
r = X
for i in range(2,M+2):
    r = r ** 2
    r %= M
    if flag[r] != -1:
        a,b = flag[r],i
        break
    else:
        flag[r] = i
        Z.append(r)

B = [0]*(len(Z))
for i in range(a-1):
    B[i] = 1
n = N-a+1
q = n//(b-a)
r = n % (b-a)

for i in range(a-1,a+r-1):
    B[i] = q+1
for i in range(a+r-1,b-1):
    B[i] = q

ans = 0
for i in range(len(Z)):
    ans += B[i]*Z[i]


print(ans)

Solution (Python):

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

    ans = 0
    loop = set([A])
    lst = [A]
    for _ in range(N):
        ans += A
        A = pow(A, 2, M)
        if A in loop:
            loop_start = lst.index(A)
            loop_sum = sum(lst[loop_start:])
            loop_length = len(lst[loop_start:])
            a = sum(lst[:loop_start])
            b = loop_sum * ((N - loop_start) // loop_length)
            c = sum(lst[loop_start:loop_start + ((N - loop_start) % loop_length)])
            ans = a + b + c
            break
        else:
            loop.add(A)
            lst.append(A)
    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0

dic = {}

roopCounter = 0
tmp = X
dic[tmp]=0
consump=0

while True:
    ans += tmp
    tmp = pow(tmp,2,M)
    roopCounter += 1
    if tmp in dic:
        consump = roopCounter
        roopCounter = roopCounter-dic[tmp]
        rooper = tmp
        break
    else:
        dic[tmp]=roopCounter

new_dic = {}
tmp = rooper
new_dic[tmp]=0
while True:
    tmp = pow(tmp,2,M)
    if tmp in new_dic:
        break
    else:
        new_dic[tmp]=0
once = 0
for i in new_dic:
    once+=i

ans += once*((N-consump)//roopCounter)

tmp = rooper
for i in range(0,(N-consump)%roopCounter):
    ans += tmp
    tmp = pow(tmp,2,M)

print(ans)

Solution (Python):
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 = 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 + 1)

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

    K = 0
    for _ 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()

Solution (Python):
n,x,m = list(map(int,input().split()))
import sys

a = [x]
while True:
  res = (a[-1]**2) % m
  if len(a) == n:
    print(sum(a))
    sys.exit()
  elif res == 0:
    print(sum(a))
    sys.exit()
  elif res in a:
    ai = a.index(res)
    aa = a[ai:]
    break
  else:
    a.append(res)

if len(a) >= n:
  print(sum(a[:n]) )
  sys.exit()

shuuki = len(aa)
shuuki_sum = sum(aa)

ans = sum(a) + shuuki_sum * ( (n-len(a)) // shuuki ) + sum( aa[:(n-len(a)) % shuuki] )
print(ans)

Solution (Python):
n,x,mod=map(int,input().split())

now=x
xs=0
for i in range(min(n,32)):
    if now%mod==0:print(xs);exit()
    else:
        xs+=now
        now=now*now%mod
        
if x%mod:
    from collections import defaultdict
    d=defaultdict(int)
    su=defaultdict(int)
    s=0
    for i in range(1,n+1):
        if  d[x]:cnt=i;pre=d[x];break
        d[x]=i
        s+=x
        su[i]=s
        x=x**2%mod
    else:print(s);exit()
    length=cnt-pre
    roop=(n-pre)//length
    amari=(n-pre)%length
    once=s-su[pre]+x

    print(su[pre]+roop*once+su[pre+amari]-su[pre-1]-x)


else:print(0)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():

    n,x,MOD = get_nums_l()

    ans = x
    now = x

    known = {x}
    history = [x]

    for i in range(1, n):
        y = now**2 % MOD
        if y in known:
            
            last_known = i-1
            loop_sum = y
            while history[last_known] != y:
                loop_sum += history[last_known]
                last_known -= 1
            loop_len = i - last_known

            ans += (n-i) // loop_len * loop_sum

            

            for j in range((n-i) % loop_len):
                if (last_known + j) < len(history):
                    ans += history[last_known + j]
            break

        known.add(y)
        history.append(y)
        ans += y
        now = y
    
    print(ans)


main()

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

L = [0] * M
S = [0] * (M + 1)
cnt = 1

L[X] = 1
S[1] = X

t = X
cnt = 1
for i in range(N):
  t = t * t % M
  if L[t] != 0:
    r = L[t]
    break
  L[t] = i + 2
  S[cnt + 1] = S[cnt] + t
  cnt += 1

if N <= cnt:
  print(S[N])
  exit()

roop = cnt - r + 1
d, m = divmod(N - r + 1, roop)

ans = (S[cnt] - S[r - 1]) * d
ans += S[r + m - 1]
print(ans)

Solution (Python):
n, x, m  = map(int, input().split())
a = [x]
found = {x}
while True:
    y = (a[-1] ** 2) % m
    a.append(y)
    if y in found:
        break
    found.add(y)
if n <= len(a):
    print(sum(a[:n]))
else:
    z = a.index(a[-1])
    a.pop()
    n -= z
    res = sum(a[:z])
    res += sum(a[z:]) * (n // (len(a) - z))
    res += sum(a[z:z + (n % (len(a) - z))])
    print(res)

Solution (Python):
n,x,m=map(int,input().split())
l=[x]
n-=1
f=-1
while(n>0):
    x=x*x
    x%=m
    if x in l:
        for i in range(len(l)):
            if x==l[i]:
                f=i
                s=l[i:].copy()
                break
    if f!=-1:
        break
    l.append(x)
    n-=1

if n==0:
    print(sum(l))
else:
    ans=sum(l)
    l=s.copy()
    ans+=sum(l)*(n//len(l))
    c=n%len(l)
    f=0
    while(c!=0):
        ans+=l[f]
        c-=1
        f+=1
    print(ans)

Solution (Python):
def calc_dynamic(n, x, m):
    
    cal_result = {}

    
    cal_result[1] = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result[i+1] = cal_result[i] ** 2 % m

    
    return sum(cal_result.values())

def calc_dynamic2(n, x, m):
    cal_result_0 = 0
    cal_result_1 = 0

    
    cal_result_0 = x
    total = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1

    return total

def calc_dynamic3(n, x, m):
    
    cal_result = {}
    cal_result_0 = 0
    cal_result_1 = 0
    loop_range = (0,0)

    
    cal_result_0 = x
    total = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1
        if cal_result_1 in cal_result:
            loop_range = (cal_result[cal_result_1], i, cal_result_0, cal_result_1)
            break
        else:
            cal_result[cal_result_1] = (i, total)

    if i == n-1:
        return total

    hoge = i
    r = i - loop_range[0][0]
    v = total - loop_range[0][1]
    hoge += r
    total += v * ((n - hoge) // r)
    hoge += r * ((n - hoge) // r)
    
    
    

    cal_result_0 = loop_range[2]
    cal_result_1 = loop_range[3]
    for i in range(hoge-r+1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1

    return total

[n, x, m] = map(lambda x: int(x), input().split(" "))
print(calc_dynamic3(n, x, m))

Solution (Python):
import sys
N, X, M = map(int, input().split())

now = X
temp_answer = now
exists = set([now])
order = [now]
rewards = [now]

for i in range(N-1):
    now = now**2 % M
    
    if now in exists:
        pre = order.index(now)
        circle = i+1 - pre
        circle_reward = rewards[-1] + now - rewards[pre]
        stopped = i + 1
        temp_answer += now
        break
    exists.add(now)
    order.append(now)
    rewards.append(rewards[-1] + now)
    temp_answer += now
else:
    print(temp_answer)
    sys.exit()

N = N - (stopped)
answer = temp_answer

answer += circle_reward * ((N-1)//circle)
rest = (N-1) % circle

for i in range(rest):
    now = now**2 % M
    answer += now

print(answer)

Solution (Python):
import sys
n,x,m=map(int,input().split())
a=[0]*(m+2)
cnt=[0]*(m+2)
a[1],f=x,x
cnt[f]=1
if x==0:
  print(0)
  sys.exit()
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)

Solution (Python):
n,x,m = map(int,input().split())
if x == 1:
  print(n)
  exit()
u = [0 for _ in range(m)]
rs = [0 for _ in range(m+1)]
s = x
u[x] = 1
rs[1] = x
i = 2
while True:
  x = (x*x)%m
  if u[x] == 0:
    u[x] = i
    s += x
    rs[i] = s
    i += 1
  else:
    ls = u[x]
    le = i-1
    break
if n <= le:
  print(rs[n])
  exit()
ans = rs[ls-1]
ll = le-ls+1
nl = n-ls+1
lsum = rs[le] - rs[ls-1]
q = nl//ll
r = nl%ll
ans += q*lsum
ans += rs[ls-1+r] - rs[ls-1]
print(ans)

Solution (Python):

N, X, M = map(int, input().split())
dp = [False]*(M+1)
dp[X] = True
S = [0]*(M+1)
S[1] = X
tmp = X
for i in range(2, min(M+1, N+1)):
    tmp = pow(tmp, 2, M)
    if dp[tmp]:
        for j in range(1, i):
            if tmp == S[j]:
                break
        ans = 0
        for k in range(j, i):
            ans += S[k]
        ans *= (N-j+1)//(i-j)
        for k in range(1, j):
            ans += S[k]
        for k in range(j, j+(N-j+1)%(i-j)):
            ans += S[k]
        print(ans)
        break
    else:
        dp[tmp] = True
        S[i] = tmp
else:
    print(sum(S))

Solution (Python):
N,X,M=map(int,input().split())
L=[]
L.append(X)
J=[0 for i in range(M+1)]
key=0
start=0
end=0
for i in range(1,M+2):
    X=(X**2)%M
    L.append(X)
    if J[X]>=1:
        key=X
        end=i
        break;
    J[X]+=1
for i in range(1,end):
    if L[end-i]==key:
        start=end-i
A=L[0:start]
B=L[start:end]
C=(N-start)//(end-start)
D=(N-start)%(end-start)
E=L[start:start+D]
if N<end:
    print(sum(L[0:N]))
else:
    print(sum(A)+sum(B)*C+sum(E))