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

def main():
    N, X, M = map(int, input().split())
    Set = {X}
    A = [X]
    for i in range(1,M+1):
        nextA = A[i-1]**2 % M
        if nextA in Set:
            loop = A[A.index(nextA):]
            break
        else:
            Set.add(nextA)
            A.append(nextA)

    lenloop = len(loop)
    x, y = divmod(N-len(A), lenloop)
    ans = sum(A) + x*sum(loop) + sum(loop[0:y])
    print(ans)

main()

Solution (Python):

n, x, m = map(int, input().split())
import sys

result = [x]
pat = set()
pat.add(x)
flg = False
for _ in range(n - 1):
    tmp = pow(result[-1], 2, m)
    if tmp in pat:
        flg = True
        break
    elif tmp == 0:
        print(sum(result))
        sys.exit()
    else:
        result.append(tmp)
        pat.add(tmp)
        
if not flg:
    print(sum(result))

else:
    cnt = result.index(tmp)
    cycle = result[-(len(result) - cnt):]
    rest = (n - cnt)
    print(sum(result[:cnt]) + (rest // len(cycle)) * sum(cycle) + sum(cycle[:rest % len(cycle)]))

Solution (Python):
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


N,X,M = LI()







route = [X]

visited = set([X])
next = X**2 % M

while True:
    if next in visited:
        loopStart = route.index(next)
        break
    else:
        route.append(next)
        visited.add(next)
        next = next**2 % M    

beforeLoop = route[:loopStart]

loop = route[loopStart:]



if N < loopStart:
    ans = sum(beforeLoop[:N])

else:
    numOfLoops,mod = divmod((N-(loopStart)),len(loop))
    
    ans = sum(beforeLoop) + numOfLoops * sum(loop) + sum(loop[:mod])

print(ans)

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

dp=[False]*m
flag = True

res=[]
for i in range(n):
    res.append(x % m) 
    if dp[x] != False:
        flag = False
        break
    dp[x] = i 
    x = (x*x) % m
    if x ==0:
        print(sum(res))
        exit()
    if x==1:
        print(sum(res)+n-i-1)
        exit()

if flag:
    print(sum(res))
    exit()

r_sum = sum(res[dp[x]:i])
r_kaisu = (n-dp[x]) // (i-dp[x])
r_amari = (n-dp[x]) % (i-dp[x])

amari_st = sum(res[:dp[x]])
amari_en = sum(res[dp[x]:dp[x]+r_amari])

print(r_sum*r_kaisu+amari_st+amari_en)

Solution (Python):
def main():
    n,x,m=map(int,input().split())
    visited=[0]*m
    visit_sum=[0]*m
    i=1
    sm=x
    visited[x]=1
    visit_sum[x]=x
    work=x
    while i < n:
        work**=2
        work%=m
        sm+=work
        i+=1

        if not visited[work]:
            visited[work]=i
            visit_sum[work]=sm
        else :
            break
    else :
        print(sm)
        exit()
    loop_sum=sm-visit_sum[work]
    loop_num=i-visited[work]
    if visited[work]!=1: 
        initial_sum=visit_sum[visited.index(visited[work]-1)]
    else :
        initial_sum=0

    out=initial_sum

    out+=(n-visited[work]+1)//loop_num*loop_sum

    work_num=(n-visited[work]+1)%loop_num
    if work_num>0:
        out+=visit_sum[visited.index(visited[work]-1+work_num)]-initial_sum
        
    print(out)

main()

Solution (Python):
N, X, M = [int(v) for v in input().split()]

def f(a):
    return a * a % M

a = X

map = {}
ary = [a]
map[a] = 0

sub = [0, a]
last_sub = a

count = 1
for i in range(1, N):
    a = f(a)
    if a == 0:
        break
    if a in map:
        break
    else:
        map[a] = i
    count += 1
    last_sub += a
    sub.append(last_sub)

if a == 0:
    print(sub[-1])
    exit()


def naive(a):
    total = a
    ary = [a]
    for i in range(1, N):
        a = f(a)
        ary.append(a)
    return ary
    




j = map[a]




unit = sub[-1] - sub[j]


l = count
i = (N - j) % (l - j)
d = (N - j) // (l - j)





print(unit * d + sub[i + j])

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

ans = []
chk = [0]*(m+1)

tmp = x
tmp %= m
idx = 0

for i in range(n):
    ans.append(tmp)
    if tmp == 0:
        print(sum(ans))
        exit()
    if chk[tmp] == 1:
        idx = i
        break
    chk[tmp] = 1
    tmp *= tmp
    tmp %= m

if idx == 0:
    print(sum(ans))
    exit()

li = [0]*(m+1)

l_num = ans[-1]

for i in range(len(ans)):
    if l_num == ans[i]:
        f_idx = i
        break

li[0] = l_num

shuki = len(ans)-f_idx-1

for i in range(1,shuki):
    li[i] = li[i-1] + ans[f_idx+i]

t_ans = 0
t_ans += (n-idx-1) // shuki * li[shuki-1]
t_ans += li[(n-idx-1) % shuki]

print(sum(ans)-ans[-1]+t_ans)

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

a = X
s = set([a])
lst = [0]*M
lst[a] = 1
rlt = 0

j = 0
f = 1
for i in range(2,N+1):
  a = a**2 % M
  if a == 0:
    f = 2
    break
  elif a in s:
    j = lst[a]
    f = 0
    break
  else:
    lst[a] = i
    s.add(a)

if f > 0:
  print(sum(s))
else:
  t = 0
  k = i - j
  p = (N-j+1)//k
  r = (N-j+1)%k
  for u in range(1,M):
    if 0 < lst[u] < j:
      rlt += u
    elif lst[u] >= j:
      t += u
      if lst[u]-j+1 <= r:
        rlt += u
  rlt += t*p
  print(rlt)

Solution (Python):
n, x, m = map(int, input().split())
d = [0]*(m+1)
check = [x]
tmp = x
for i in range(1, n):
    tmp = (tmp**2)%m
    if d[tmp]: break
    d[tmp] = 1
    check.append(tmp)

for i in range(len(check)):
    if tmp == check[i]:
        index = i
        break
sum_c = sum(check[index:])
ans = sum(check)
nokori = n - len(check)
kuri = nokori//len(check[index:])
ans += kuri*sum_c
nokori -= kuri*len(check[index:])
ans += sum(check[index:index+nokori])
print(ans)

Solution (Python):
import math
import collections
def main():

    N, X, M = map(int, input().split())
    visited = dict()
    visited[X] = 0
    A = [X]
    v = X
    j = -1
    isperiod = False
    for i in range(1, N):
        v = (v * v) % M
        if v not in visited:
            visited[v] = i
            A.append(v)
        else:
            j = visited[v]
            isperiod = True
            break

    if isperiod:
        u = sum(A[:j])
        B = A[j:]
        p = len(B)
        u += ((N-j) // p) * sum(B) + sum(B[:(N-j) % p])
        return u
    return sum(A)



if __name__ == '__main__':
    print(main())

Solution (Python):
l=input().split()
n=int(l[0])
x=int(l[1])
m=int(l[2])
hashi=dict()
pref=0
count=0
prefix=[]
for i in range(n):
    if(i==0):
        ans=x%m
    else:
        ans=ans*ans
        ans%=m
    if(ans in hashi):
        period=i-(hashi[ans][0])
        num1=hashi[ans][0]
        k=(n-num1)//period
        rem=(n-(num1+k*period))
        count=count+prefix[num1]
        count=count+k*(pref-hashi[ans][1])
        for j in range(rem):
            if(j!=0):
                ans=ans*ans
            ans%=m
            count+=ans
        break
    hashi[ans]=(i,pref)
    prefix.append(pref)
    pref+=ans
print(max(pref,count))

Solution (Python):
def main():
    n,x,m = tuple([int(t)for t in input().split()])

    a = x
    s = a

    nextvalues = [a]
    values = set([a])

    for i in range(1,n):
        a = a*a % m
        if a in values:
            idx = nextvalues.index(a)
            size = i-idx
            sumofsubset = sum(nextvalues[idx:i])
            s += sumofsubset*((n-i)//size)+sum(nextvalues[idx:idx+(n-i)%size])
            break
        s += a
        nextvalues.append(a)
        values.add(a)
    print(s)

if __name__ == "__main__":
    main()

Solution (Python):
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, X, M = read_ints()
    seen = [0]*M
    answer = X
    cycle_length = 1
    cycle_prefix = [0, X]
    N -= 1
    count = 0
    while N > 0:
        next_X = (X**2) % M
        if seen[next_X]:
            cycle_length = count-seen[next_X]+1
            break
        seen[next_X] = seen[X]+1
        cycle_prefix.append(cycle_prefix[-1]+next_X)
        answer += next_X
        N -= 1
        X = next_X
        count += 1
    if N == 0:
        return answer
    answer += (N//cycle_length)*(cycle_prefix[-1]-cycle_prefix[-cycle_length-1])
    N %= cycle_length
    while N > 0:
        X = (X**2) % M
        answer += X
        N -= 1
    return answer


if __name__ == '__main__':
    print(solve())

Solution (Python):
import copy

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

visited = [-1]*(m+1)
when = [-1]*(m+1)
ans = 0
i = 1
while i <= n:
    ans += x
    if x == 0:
        break
    if visited[x] > -1:
        cycle = (n - i) // (i - when[x])
        ans += cycle*(ans - visited[x])
        i += cycle*(i - when[x]) + 1
        visited = [-1]*(m+1)
        when = [-1]*(m+1)
        x **= 2
        x %= m    
        continue
    visited[x] = copy.deepcopy(ans)
    when[x] = copy.deepcopy(i)
    x **= 2
    x %= m
    i += 1


print(ans)

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

lm = [x]
a = x

zero = 0
for i in range(m):
    a = a ** 2 % m
    if a == 0:
        zero = 1
        break
    lm.append(a)

if zero == 1:
    if n < len(lm):
        print(sum(lm[:n]))
    else:
        print(sum(lm))
        

else:
    last = lm[m]
    for i in range(1, m+1):
        if lm[m-i] == last:
            syuki = i
            break

    for i in range(2, m//syuki + 2):
        if m - i*syuki < 0:
            amari = (m+1) % syuki
        if lm[m - i*syuki] != last:
            amari = m - (i-1) * syuki + 1
            break

    l1 = lm[:amari]
    l2 = lm[amari:amari + syuki]


    if n <= amari:
        print(sum(l1[:n]))

    else:
        n -= amari
        print(sum(l1) + sum(l2) * (n//syuki) + sum(l2[:(n%syuki)]))

Solution (Python):
n, x, m = map(int, input().split())
pass_num = set()
route = []
num = x
count = 0
ans = 0
while num not in pass_num:
    count += 1
    pass_num.add(num)
    route.append(num)
    num = (num * num) % m

index = route.index(num)
pre = route[:index]
latter = route[index:]
if count >= n:
    
    print(sum(route[:n]))
    exit()
else:
    ans = sum(pre)
    n -= len(pre)
    roop_cnt = len(latter)
    N = n // roop_cnt
    ans += N * sum(latter)
    n -= N * roop_cnt
    ans += sum(latter[:n])
    print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n,x,m=LI()
s={x%m:(1,x%m)}
L=[x%m]
now=x%m
cycle=1
ret=x%m
diff=0
pre=0
for i in range(2,m+2):
    now=pow(now,2,m)
    ret += now
    if now in s:
        pre, pre_ret = s[now]
        cycle=i-pre
        diff=ret-pre_ret
        break
    s[now]=(i,ret)


ans=diff*((n-pre)//cycle)+pre_ret
for k in range((n-pre)%cycle):
    now = pow(now, 2, m)
    ans+=now

print(ans)

Solution (Python):
N,X,M=map(int, input().split())
A=[X]
for i in range(1,M+1):
  d=pow(A[i-1],2,M)
  if d in A:
    break
  A.append(d)
c=A.index(d)
e=len(A)
cy=e-c
ans=0
if N<=e:
  for i in range(N):
    ans+=A[i]
  print(ans)
else:
  m=sum(A[:c])
  n=sum(A[c:e])
  
  f=(N-c)//cy
  ans=m+n*f+sum(A[c:c+((N-c)%cy)])
  print(ans)

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


found = [ -1 for _ in range( m ) ]
summation = [ 0 ]
a = x
length, loop_s, s_0, start = -1, -1, -1, -1
for i in range( n ):
    if found[ a ] > -1:
        length = i - found[ a ]
        loop_s = summation[ i ] - summation[ found[ a ] ]
        start = found[ a ]
        s_0 = summation[ start ]
        
        break
    else:
        found[ a ] = i
    
    summation.append( summation[ -1 ] + a )
    a = ( a * a ) % m

if length < 0:
    print( summation[ n ] )
else:
    times = ( n - start ) // length
    rem = ( n - start ) % length
    rem_s = summation[ start + rem ] - s_0
    print( s_0 + loop_s * times + rem_s )

Solution (Python):







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

def mod(x):
    return x % M

a = X

i = 0

ans = 0
last = -1

dic = []

while a != 0 and i < N:
    ans += a
    a = mod(a * a)
    i += 1

    if a in dic:
        last = dic.index(a)
        break

    dic.append(a)


if i != N and a != 0:
    tdic = dic[last:]
    if N - i >= len(tdic):
        sdic = sum(tdic)
        ans += sdic * ((N - i) // len(tdic))

    for j in range((N - i) % len(tdic)):
        ans += tdic[j]

print(ans)

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

amari = [x]
amariset = {x}
cnt = 0
p = 0

for i in range(n-1):
	a = amari[-1]**2 % m
	if a in amariset:
		p = amari.index(a)
		cnt = i+1-p
		break
	else:
		amari.append(a)
		amariset.add(a)

if cnt == 0:
	print(sum(amari))
	
else:
	n -= len(amari)
	a = n // cnt
	b = n % cnt
	print(sum(amari)+a*sum(amari[p:])+sum(amari[p:(p+b)]))

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

A = [x]
where = {x: 0}
a = x
for i in range(1, n):
    a = A[-1]**2 % m
    if a in where:
        break
    where[a] = i
    A.append(a)

perstart = where[a]
res = sum(A)
rem = n - len(A)
per = len(A) - perstart
res += rem//per*sum(A[perstart:perstart+per])
res += sum(A[perstart:perstart + (rem%per)])

print(res)

Solution (Python):
N, X, M = map(int, input().split())
C = X
F = {X}
S = 0
cnt = 0
loop = 0
loop_S = 0
while cnt < N:
    S += C
    cnt += 1
    C *= C
    C %= M
    if C in F:
        break
    F.add(C)
st = C
L = 0
if cnt < N:
    val = (st * st) % M
    loop += 1
    loop_S = st
    while val != st:
        loop_S += val
        loop += 1
        val *= val
        val %= M
    ccnt = N - ((N-cnt)//loop)*loop - cnt
    res = 0
    val = st
    while ccnt > 0:
        res += val
        val *= val
        val %= M
        ccnt -= 1
    print(S+loop_S*((N-cnt)//loop)+res)
else:
    print(S)

Solution (Python):
N, X, M = map(int, input().split())
ans = X
ALL_cal = [False] * M
ALL = []
rou = False
for i in range(N-1):
    X = pow(X, 2, M)
    if ALL_cal[X]:
        num = ALL_cal[X]
        now = i
        rou = True
        break
    ALL.append(X)
    ALL_cal[X] = i
    ans += X
if rou :
    roupe = now - num 
    nokori = N - now - 1
    print(sum(ALL[num:])*(nokori//roupe) + ans + sum(ALL[num:num + nokori%roupe]))
else:
    print(ans)

Solution (Python):
n,x,m= list(map(int, input().strip().split()))
t=0
b=[]
b.append(x)
for i in range(m+1):
        if b[-1]**2%m in b:
            b.append(b[-1]**2%m)
            break
        else:
            b.append(b[-1]**2%m)
        
l=len(b) 
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)

Solution (Python):
import sys

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

cnt = [0] * M
accu = [X]
cnt[X] = 1
for i in range(2,min(N+1, M+3)):
    s = (accu[-1] ** 2) % M
    if cnt[s] == 0:
        cnt[s] = i
        accu.append(s)
    else:
        c = i - cnt[s] 
        su = sum(accu[cnt[s]-1:])
        ans = sum(accu[:cnt[s]-1])
        N -= (cnt[s] - 1)
        n = N // c
        ans += n * su
        N %= c
        ans += sum(accu[cnt[s]-1:cnt[s]+ N -1])
        print(ans)
        sys.exit()

print(sum(accu))

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, x, m = map(int, input().split())
s = set([x])
l = [x]
for i in range(m):
    x = x**2 % m
    if x in s:
        start_index = l.index(x)
        break
    else:
        s.add(x)
        l.append(x)
ans = sum(l[:start_index])

q = l[start_index:]
p = (n - start_index) // len(q)
ans += sum(q) * p
ans += sum(q[:(n - p*len(q) - start_index)])
print(ans)

Solution (Python):
N,X,mod = map(int,input().split())
visited = [False for i in range(mod)]
visited[X]=True
mod_loop = [X]
now = X
while visited[now**2%mod] == False:
    mod_loop.append(now**2%mod)
    visited[now**2%mod] = True
    now = now**2%mod
now=now**2%mod

que = []
for i in range(len(mod_loop)):
    if mod_loop[i] == now:
        que.append(i)

leftsum = mod_loop[:que[0]]

looper = mod_loop[que[0]:]

if N<=len(leftsum):
    print(sum(leftsum[:N]))
else:
    ans = sum(leftsum)
    u,v = divmod(N-len(leftsum),len(looper))
    ans += u*sum(looper) + sum(looper[:v])
    print(ans)

Solution (Python):
def main():
    n,x,m = map(int,input().split())
    if m == 0:
        print(0)
        return
    t = [x]
    k = -1
    for _ in range(n-1):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    if k not in t:
        print(sum(t))
        return
    else:
        s = t.index(k)
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

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

period = 0


UNDEF = -1
last_idx = [UNDEF] * (m + 1)


ans = 0


def get_start_and_loop(n, x, m):
    first = x
    cur = first
    i = 0
    vals = []
    for i in range(n):
        if last_idx[cur] != UNDEF:
            return last_idx[cur], sum(vals[: last_idx[cur]]), i - last_idx[cur], sum(vals[last_idx[cur]: ]), cur
        last_idx[cur] = i
        vals.append(cur)
        cur = (cur * cur) % m
        i += 1
    return n, sum(vals), 1, 0, 0

start, start_sum, period, period_sum, cur = get_start_and_loop(n, x, m)

ans = start_sum
n -= start
ans += n // period * period_sum
n %= period

for i in range(n):
    ans += cur
    cur = (cur * cur) % m

print(ans)

Solution (Python):
from collections import defaultdict
dic = defaultdict(int)
N, X, M = map(int, input().split())
A = [X]
ans = X
fir = -1
if N>1:
    temp = 1
    dic[X]=temp
    for i in range(2, N+1):
        a = A[-1]*A[-1]%M
        if dic[a]>0:
            fir = dic[a]
            break
        A.append(a)
        ans+=a
        temp+=1
        dic[a]=temp
    if fir!=-1:
        T = temp-fir+1
        Tsum = 0 
        TempSum = 0 
        M=N-fir+1 
        amari = M%T 
        for k in dic:
            if dic[k]>=fir and dic[k]<=temp:
                Tsum+=k
            if dic[k]>=fir and dic[k]<fir+amari:
                TempSum += k
        ans+=TempSum
        ans+=Tsum*(M//T-1)
    print(ans)
else:
    print(ans)

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

seen = {}
ans = p%m
seen[p%m]=1
T = {}
T[1] = ans
T[0] = 0
last_p = p%m

r = 0

if n==1:
  print(p%m)
  exit()
else:
  for i in range(2,m+1000):
    p = p ** 2
    p = p % m
    
    if p not in seen:
      seen[p]=i
    else:
      r = i-seen[p]
      last_p = p
      break
    
    ans += p
    T[i] = ans
    
    if i==n:
      print(ans)
      exit()
    
    
temp = T[seen[p]-1]
ans -= temp
n -= seen[p]

k = n//r
ans *= k
ans += temp

n = n % r

if n==0:
  print(ans+last_p)
  exit()

for i in range(1,m+1000):
  p = p ** 2
  p = p % m
  ans += p
  if i==n:
    print(ans+last_p)
    exit()

Solution (Python):

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

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

tmp = [0 for i in range(M+2)]
r = [0 for i in range(M)]
tmp[1] = X
r[X] = 1 
flag = False
for i in range(2, N+1):
  X = (X * X) % M
  
  tmp[i] = X
  if r[X] == 0:
    r[X] = i
  else:
    flag = True
    p = i - r[X]
    
    pt = 0
    for j in range(r[X]+1, i+1):
      pt += tmp[j]
    tmp_rX = 0
    for j in range(1, r[X]+1):
      tmp_rX += tmp[j]
    
    p_r = (N - r[X]) % p
    
    T_r = 0
    for j in range(1,p_r+1):
      T_r += tmp[ r[X] + j ]
    
    ans = tmp_rX + pt * ((N - r[X]) // p) + T_r
    break
    
if flag:
  print(ans)
else:
  print(sum(tmp))

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

    idx = [-1] * m

    i = 1
    y = x
    while not(~idx[y]):
        idx[y] = i
        y = (y * y) % m
        i += 1
    start = idx[y]
    end = i

    loop_len = end - start  

    ans = 0
    rep = 0

    rep_flg = False
    finish = False

    j = 1
    while j <= n:
        if finish:
            ans += x
        else:
            if j == start or j == end:
                if rep_flg:
                    k = (n - 1 - j) // loop_len
                    ans += (k + 1) * rep
                    j += k * loop_len
                    rep_flg = False
                    finish = True
                    if j == n:
                        break
                else:
                    rep_flg = True
            if rep_flg:
                rep += x
            else:
                ans += x
        x = (x * x) % m
        j += 1

    if not finish:
        ans += rep
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,x,m = map (int,input().split())
next=[0] * (m+1)
memo = [-1] * (m+1)
memo[x] = 0
a = 0
now = x
unti = [x]
flag = True
b = -1
for i in range(m):

    next[now] = (now **2) % m
    
    if memo[next[now]]!=-1:
        b = memo[next[now]]
        break
    elif next[now] == 0:
        flag =False
        break
    else:
        memo[next[now]] = i+1
    a += 1
    now = next[now]
    unti.append(now)
if flag:
    if b== 0:
        if (n-b)%(a-b+1) !=0:
            print(sum(unti[b:a+1]) * ((n - b) // (a - b + 1)) + sum(unti[b:b+(n - b) % (a - b + 1)]))
        else:
            print(sum(unti[b:a+1]) * ((n - b) // (a - b + 1)))
    else:
        if (n - b) % (a - b + 1) != 0:
            print(sum(unti[b:a+1]) * ((n-b)//(a-b+1)) + sum(unti[b:b+(n-b)%(a-b+1)])  + sum(unti[:b]))
        else:
            print(sum(unti[b:a + 1]) * ((n - b) // (a - b + 1)) + sum(unti[:b]))
else:
    print(sum(unti))

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X
idx = -1
idx1 = -1
for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx == -1 or idx1 == -1):
    print(sum(rec[:N]))
elif(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M
    
    if False:
        for _ in range(N):
            ans += x
            x *= x
            x %= M
            if x == 0:
                break
        return ans
    else:
        x = X
        s = [X]
        u = set()
        while True:
            x *= x
            x %= M
            s.append(x)
            if x in u:
                break
            u.add(x)

        i = s.index(s[-1])
        if i + 1 >= N:
            return sum(s[:N]) % M

        N -= i
        ans += sum(s[:i])

        s = s[i:]
        s.pop()
        ss = sum(s)
        ans += (N // len(s)) * ss
        ans += sum(s[:N%len(s)])
        return ans


def main():
    N, X, M = read_int_n()
    print(slv(N, X, M))

    
    
    
    
    
    

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

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

ans = 0

check = np.zeros(M+1, dtype = int)
suuretu = []



for i in range(N):
    if(check[X] == 1):
        detatoko = suuretu.index(X)
        loop_sum = sum(suuretu[detatoko:])
        loop_kaisu = i - detatoko


        plus_kaisu = (N - i) // loop_kaisu
        mod_plus = (N - i) % loop_kaisu


        ans += loop_sum * plus_kaisu
        ans += sum(suuretu[detatoko:detatoko+mod_plus])
        break


    else:
        check[X]  = 1

    ans += X
    suuretu.append(X)







    X = (X * X) % M


print(ans)

Solution (Python):
n,x,m = map(int,input().split())
loop = []
loop.append(x)
looplist = [0]*m
looplist[x]=1
for i in range(1,m+1):
    x = x**2%m
    
    if looplist[x]==0:
        looplist[x]=1
        loop.append(x)
    else:
        break

ss = loop.index(x)
amari = loop[:ss]
neoloop = loop[ss:]

lon = len(neoloop)

if n<=ss:
    print(sum(amari[:n]))
else:
    print(sum(amari)+(n-ss)//lon*sum(neoloop)+sum(neoloop[:(n-ss)%lon]))

Solution (Python):
from sys import stdin
input = stdin.readline

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

ls = []
s = set([])

a = X
s.add(a)
ls.append(a)
ind = -1
new_ls = []

while True:
    a = pow(a, 2, M)

    if a in s:
        ind = ls.index(a)
        break
    elif len(ls) == N:
        break
    else:
        s.add(a)
        ls.append(a)

if ind != -1:
    new_ls = ls[ind:len(ls)]

ans = sum(ls)

if len(new_ls) != 0:
    ans += sum(new_ls) * (max(0, (N - len(ls))) // len(new_ls))

    tmp = max(0, (N - len(ls))) % len(new_ls)

    if tmp != 0:
        for i in range(tmp):
            ans += new_ls[i % len(new_ls)]

print(ans)

Solution (Python):
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().rstrip()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007

inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

def ceil(a,b):
    return (a+b-1)//b
file=1

def f():
    sys.stdout.flush()





def solve():

    
   
    n,x,m = mi()  
    m1 = {}
    m1[x]=0
    a = [x]
    ans = x
    f  = 0
    for i in range(1,n):
        x = (x*x)%m
        if x in m1:
            now = i
            f = 1
            break
        m1[x] = i
        if x==0:
            print(ans)
            exit(0)
        ans += x
        a.append(x)
    if(f == 0):
        print(ans)
        exit(0)

    ans = 0
    for i in range(m1[x]):
        ans += a[i]
    b = []
    cnt = n - m1[x] 
    ans1 = 0
    x1 = cnt//(now-m1[x])
    cnt %= (now-m1[x])
    for i in range(m1[x],len(a)): 
        ans1 += a[i]
    k = m1[x]
    ans += (ans1*x1)
    for i in range(cnt):
        ans += a[k+i]
    print(ans)









        
if __name__ =="__main__":

   
    if path.exists('input.txt'):
        sys.stdin=open('input.txt', 'r')
        sys.stdout=open('output.txt','w')
    else:
        input=sys.stdin.readline
    solve()

Solution (Python):
N,X,M = map(int,input().split())
A = set()
ans = []
a = X
flg = 0
while True:
    k = len(A)
    A.add(a)
    if len(A) == k:
        break
    if a == 0:
        flg =1
        ans.append(a)
        break
    ans.append(a)
    a = a**2%M

g = ans.index(a)
ans_first = ans[:g]
ans = ans[g:]
ans_cum = [ans[0]]
for i in range(len(ans)-1):
    ans_cum.append(ans_cum[i]+ans[i+1])
check = len(ans_cum)
N -= len(ans_first)
if N < 0:
    final = ans_first[:N]
    print(sum(final))
    exit()
loop = N//check
spare = N%check
res = 0
if flg == 0:
    if spare > 0:
        res=loop*ans_cum[-1]+ ans_cum[spare-1]+sum(ans_first)
    else:
        res=loop*ans_cum[-1]+sum(ans_first)
    print(res)
else:
    print(sum(ans_first))

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

dp = [-1 for _i in range(10**5+2)]
nums = [-1 for _i in range(10**5+2)]
nums[x] = 1

dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    print(r[min(len(r)-1, n)])
elif n <= nums[bef]:
    print(r[n])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex]+1)
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )