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())
MAXM = 101010
visited = [-1 for _ in range(MAXM)]
a = x
loop = [a]
visited[a] = 0
ans = 0
for i in range(1, n):
    a = a**2%m
    if visited[a] < 0:
        visited[a] = i
        loop.append(a)
    else:
        ii = visited[a]
        l = sum(loop[ii:i]) 
        ll = i-ii 
        ans += sum(loop[:ii]) 
        l_n = (n-ii)//ll 
        ans += l*l_n
        rem = n-ii-ll*l_n 
        ans += sum(loop[ii:rem+ii])
        break
if ans == 0:
    ans = sum(loop)
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
a = [-1 for _ in range(10 ** 5 + 2)]
memo = [-1 for _ in range(m)]
a[1] = x
for i in range(2, 10 ** 5 + 2):
    a[i] = a[i-1] ** 2 % m
    if memo[a[i]] == -1:
        memo[a[i]] = i
    else:
        one_loop = i - memo[a[i]]
        start_loop = memo[a[i]]
        break


if start_loop >= n:
    print(sum(a[1:n+1]))
else:
    ans = sum(a[1:start_loop])
    loop, res = divmod(n - start_loop + 1, one_loop)
    ans += sum(a[start_loop: start_loop + one_loop]) * loop
    ans += sum(a[start_loop: start_loop + res])   
    print(ans)

Solution (Python):
def solve(N,X,M):
    Loop = [X]
    Loop_set = set(Loop)

    for i in range(N):
        X = X**2 % M
        if X not in Loop_set:
            Loop.append(X)
            Loop_set.add(X)
        else:
            break

    loop_st = 0
    for i in range(len(Loop)):
        if Loop[i] == (Loop[-1]**2 % M):
            loop_st = i
            break

    loop_len = len(Loop) - loop_st
    ans = sum(Loop[:loop_st])
    N -= loop_st
    ans += (sum(Loop[loop_st:]) * (N // loop_len) + sum(Loop[loop_st:loop_st + (N % loop_len)]))
    return ans

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

    print(solve(N,X,M))

if __name__ == "__main__":
    main()

Solution (Python):
N, X, M = map(int, input().split())
x = X
nums = []
isSearched = [False] * (M+1)
isSearchedNums = [-1] * (M+1)
n = 0
looped = 0
while True:
    x = (x*x) % M
    if isSearched[x]:
        looped = isSearchedNums[x]
        break
    isSearched[x] = True
    isSearchedNums[x] = n
    nums.append(x)
    n+=1
if (isSearched[0]):
    ans = X
    for i in range(min((N-1), len(nums))):
        ans += nums[i]

    print(ans)
else:
    ans = X
    al = 0
    d = len(nums) - looped
    for i in range(looped, len(nums)):
        al += nums[i]
    if N - 1 > len(nums):
        N -= len(nums)
        ans += sum(nums)
        ans += al * ((N-1) // d)
        for i in range(looped, ((N-1) % d) + looped):
            ans += nums[i]
    else:
        for i in range(N - 1):
            ans += nums[i]

    print(ans)

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

lst = set()
num = []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i, num.index(x)
        div, mod = divmod(n - cnt, len(num) - idx)
        ans = sum(num[:idx + mod])
        ans += sum(num[idx:]) * (div + 1)
        break
else:
    ans = sum(num)
print(ans)

Solution (Python):
def main():
    N,X,M = map(int,input().split())
    dict = {key:0 for key in range(M)}
    
    if N==1:
        return X
    dict[X] += 1
    cnt = 1
    A = [0]*(M+1)
    A[1] = X
    ans = X
    tmp = X
    for i in range(1,N,1):
        tmp = (tmp**2)%M
        if dict[tmp] != 0:
            break
        ans += tmp
        A[i+1] = A[i]+tmp
        cnt += 1
        dict[tmp] += cnt

    num = N - cnt
    roop_num = cnt - dict[tmp] + 1
    syo = num//roop_num
    amari = num%roop_num
    ans += syo*(A[cnt]-A[dict[tmp]-1])
    ans += (A[dict[tmp]+amari-1]-A[dict[tmp]-1])
    return ans

print(main())

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

seen=[-2]*M
seen[X]
A=[X]
i=1
while(i<N):
    T=A[-1]**2%M
    if seen[T]!=-2:
        Roop=i-seen[T]
        Left,Right=seen[T],i
        break
    A.append(T)
    seen[T]=i
    i+=1

if i==N:
    print(sum(A))
    exit()

Roopsum=0
for i in range(Left,Right):
    Roopsum+=A[i]

Rest=N-len(A)

ans=sum(A)

ans+=Rest//Roop*Roopsum

for i in range(Rest%Roop):
    ans+=T
    T=T**2%M
print(ans)

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


def read():
    N, X, M = map(int, input().strip().split())
    return N, X, M


def solve(N, X, M):
    S = [-1 for i in range(M)]
    A = [0 for i in range(M+2)]
    na = X
    
    i = 1
    S[na] = i
    A[i] = X
    for i in range(2, min(N+1, M+1)):
        
        A[i] = A[i-1] * A[i-1] % M
        a = A[i-1]
        na = A[i]

        if S[na] == -1:
            S[na] = i
        else:
            
            period_start = S[na]
            period_end = S[a]
            period_length = S[a] - S[na] + 1
            
            n_loop, left = divmod(N - S[na] + 1, period_length)
            
            loop_sum = sum(A[S[na]:i])
            left_sum = sum(A[S[na]:S[na]+left])
            ans = sum(A[:S[na]]) + n_loop * loop_sum + left_sum
            return ans
        if na == 0:
            break
    return sum(A)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,x,m=nii()

ans=x
x_list=[x]
zan=0
for i in range(n-1):
  a=(x**2)%m
  ans+=a
  x=a
  if x in x_list:
    inx=x_list.index(x)
    zan=(n-1)-i-1

    inx=x_list.index(x)+1
    nx_list=x_list[inx:]+[x_list[inx-1]]

    if zan<=len(nx_list):
      ans+=sum(nx_list[:zan])
    else:
      num=zan//len(nx_list)
      q=zan%len(nx_list)
      ans+=sum(nx_list)*num
      ans+=sum(nx_list[:q])
    break
  else:
    x_list.append(x)

print(ans)

Solution (Python):
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

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

used=[0]*m
used[x]=1
cnt=1
y=x
while True:
    y=y**2
    y%=m
    cnt+=1

    if used[y]>0:
        loopst=used[y]
        loopend=cnt-1
        break
    
    used[y]=cnt

ans=0
loopsum=0
beforesum=0
for i in range(m):
    if loopst<=used[i]<=loopend:
        loopsum+=i
    if 0<used[i]<loopst:
        beforesum+=i

if n>loopend:
    n-=loopst-1
    ans+=beforesum
    ans+=n//(loopend-loopst+1)*loopsum
    n%=(loopend-loopst+1)
    
    for i in range(m):
        if used[i]==loopst:
            x=i
            break

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

print(ans)

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

l = []
ans = 0
for i in range(n):
    if x in l:
      
        d = l.index(x)
        ans += sum(l[:d])
        le = len(l)-d
        
        count = sum(l[d:])
        
        n -= d
        
        ans += count*(n//le)
        n %= le
        
        for k in range(d,d+n):
            ans += l[k]

        print(ans)
        exit()
        break
    l.append(x)
    x = (x**2)%m

print(sum(l))

Solution (Python):

import sys
sys.setrecursionlimit(10**6)

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

data = [-1]*(m+1)

ans = x

num = x
data[x] = (1, 0)
count = 2

flag = 0
while(count <= n):
    
    num_new = (num**2) % m
    if data[num_new] == -1 or flag == 1:
        data[num_new] = (count, ans)
        ans += num_new
        num = num_new
    else:
        diff = ans-data[num_new][1]
        frec = count - data[num_new][0]

        kaisuu = (n-(count-1))//frec

        if kaisuu > 0:
            count = count-1 + frec*kaisuu
            ans += kaisuu*diff
        else:
            ans += num
            num = num_new
        flag = 1
    count += 1



print(ans)

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

s = set()
idx = {i: -1 for i in range(m)}
cumsum = [0]
val = x
idx[val] = 0
for i in range(n):
    cumsum.append(cumsum[-1] + val)
    val = pow(val, 2, m)
    if idx[val] != -1:
        break
    idx[val] = i + 1

if len(cumsum) > n:
    print(cumsum[n])
else:
    loop_len = i + 1 - idx[val]
    print((cumsum[i+1]-cumsum[idx[val]]) * ((n-idx[val])//loop_len) + cumsum[idx[val]+(n-idx[val])%loop_len])

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

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

li = [-1] * (m+1)
v = [False] * (m+1)
v2 = [False] * (m+1)
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

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[n-1])
else:
    n -= len(ans_li)
    if len(loop_li) == 0:
        print(ans_li[-1])
    else:
        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])

Solution (Python):
n,x,m = map(int,input().split())
ans = 0
al = set([x])
for i in range(n):
  ans += x
  x = (x**2)%m
  if x==0:
    break
  if x in al:
    ind = list(al).index(x)
    loop = i-ind+1
    l = list(al)
    ans += sum(l[ind:i+1])*((n-i-1)//loop)
    for j in range((n-i-1)%loop):
      ans += l[ind+j]
    break
  al.add(x)
print(ans)

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

ans, tmp = X, X
s = set()
s.add(X)
for i in range(1, N):
  tmp = (tmp**2) % M
  if tmp == 0:
    break
  if tmp == 1:
    ans += N-i
    break
  if tmp not in s:
    s.add(tmp)
    ans += tmp
  else:
    s = list(s)
    idx = s.index(tmp)
    ans += sum(s[idx:]) * ((N-i)//(len(s)-idx))
    ans += sum(s[idx:idx+(N-i)%(len(s)-idx)])
    break
print(ans)

Solution (Python):
N, X, M = [int(x) for x in input().split()]
s = [0] * (M+10)
s[1] = X
d = {X: 0}
tmp = X
for i in range(M):
    tmp = tmp * tmp % M
    if tmp == 0:
        print(s[i+1])
        exit()
    elif tmp in d:
        l, r = d[tmp], i+1
        sl = s[r] - s[l]
        loop = r-l
        ans = sl*((N-l)//loop) + s[l+(N-l)%loop]
        print(ans)
        exit()
    else:
        d[tmp] = i+1
        s[i+2] = s[i+1] + tmp
print(d)

Solution (Python):
def f(x, m):
    return (x ** 2) % m


def main():
    n, x, m = map(int, input().split())
    lst = [[False, 0] for _ in range((m + 1))]
    lst[x] = [True, 1]
    res = [x]
    loop = 0

    for i in range(2, m + 1):
        x = f(x, m)
        if lst[x][0] == False:
            lst[x][0] = True
            lst[x][1] = i
            res.append(x)
        else:
            loop = i - lst[x][1]
            non_loop = lst[x][1] - 1
            break
    if loop == 0:
        print(sum(res[:n]))
        exit()
    ans = sum(res[:non_loop])
    ans += (n - non_loop) // loop * sum(res[non_loop:])
    ans += sum(res[non_loop:non_loop + (n - non_loop) % loop])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,x,m = map(int,input().split())
set_ = set()
l = []
cnt =0
dic = {}
while x not in set_ and cnt<n:
    set_.add(x)
    l.append(x)
    dic[x]= cnt
    cnt += 1
    x = (x**2)%m
    if x==0:
        l.append(0)
        break
if l[-1]==0:
    print(sum(l));exit()
if cnt==n:
    print(sum(l));exit()

ans = sum(l[:dic[x]])
l = l[dic[x]:]

L = l+ l
cnt  = len(l)
n-=dic[x]
s = sum(l)
ans += (n//cnt)*s + sum(l[:n%cnt])

print(ans)

Solution (Python):
N, X, M = map(int, input().split())
Flag = [True]*(M)

A = []
temp = X

while Flag[temp]:
  A.append(temp)
  Flag[temp] = False
  temp = (temp**2)%M
  last = temp

I = A.index(last)
looplen = len(A) - I
loop, cnt = divmod(max(N-I, 0), looplen)

ans = 0
if N <= I+1:
  ans += sum(A[:N])
else:
  ans += sum(A[:I])
  ans += loop*sum(A[I:])
  ans += sum(A[I:I+cnt])

print(ans)

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

A = X
i = 1
sigma = X
A_list = [None, X]
A_sigma = [None, X]
A_index = {X: 1}
cycled = False
while i < N:
    A = A*A % M
    i += 1
    sigma += A

    if cycled: continue

    A_list.append(A)
    A_sigma.append(sigma)
    if A not in A_index:
        A_index[A] = i
    else:
        cycle_len = i - A_index[A]
        cycles = (N-i) // cycle_len
        sigma += (sigma - A_sigma[A_index[A]]) * cycles
        i += cycles * cycle_len
        cycled = True

print(sigma)

Solution (Python):
n,X,m=map(int,input().split())
if m==1:
    print(0)
else:
    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):
        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)
    
    
    
    
    
    
    
    
    if n>=b:
        ans=sum(y[:b])+((n-b)//L)*s+sum(l[:(n-b)%L])
    else:
        ans=sum(y[:n])
    print(ans)

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

p = x
seen = {}
total = 0
done = False

for i in range(min(n, m)):
    total += p

    if p in seen:
        
        cycleTotal = total - seen[p][1]
        cycleLength = i - seen[p][0]
        

        iterationsLeft = (n-(i+1))
        total += (iterationsLeft//cycleLength) * cycleTotal

        iterationsLeft %= cycleLength

        for j in range(iterationsLeft):
            p = (p**2)%m
            total += p

        print(total)
        done = True
        break
    else:
        seen[p] = (i, total)

    p = (p**2)%m

if not done:
    print(total)

Solution (Python):
n,x,m=map(int,input().split())
ans=x
rp=[x]
if n<=m:
    for i in range(n-1):
        x=pow(x,2,m)
        ans+=x
    print(ans)
    exit()
for i in range(m+1):
    x=pow(x,2,m)
    if x in rp:
        tt=rp.index(x)
        t=len(rp)-tt
        break
    else:
        rp.append(x)
tmp=sum(rp[tt:])
wari=(n-tt)//t
amari=(n-tt)%t
ans=sum(rp[:tt])+tmp*wari+sum(rp[tt:tt+amari])
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

n, x, m = map(int, input().split())
seen = [-1] * m
is_done = True
ans = 0
for i in range(n):
    if i == 0:
        val = x
    else:
        val = val * val % m
    if seen[val] != -1:
        loop_len = i - seen[val]
        loop_val = val
        is_done = False
        cnt = i
        break
    else:
        seen[val] = i
        ans += val
if is_done:
    print(ans)
    exit()
n -= (cnt + 1)

val = loop_val
loop_sum = 0
for i in range(loop_len):
    val = val * val % m
    loop_sum += val
ans += (n // loop_len) * loop_sum

val = loop_val
for i in range(n % loop_len):
    val = val * val % m
    ans += val

print(ans + loop_val)

Solution (Python):
n, x, m = map(int,input().split())
k = (x ** 2) % m
l = [0] * (m+1)
l[(x ** 2) % m] == 0
a = [x]
flag = True
for i in range(n-1):
    x = (x ** 2) % m
    a.append(x)
    if l[x] != 0:
        flag = False
        break
    else:
        l[x] += 1
    
    

if not flag:
    p = i+1
    ku = n - p 
    f = False
    loops = []
    for i in range(len(a)-1):
        if f:
            loops.append(a[i])
        else:
            if (a[i]) == a[-1]:
                loops.append(a[i])
                p = len(a) - (i+1)
                f = True
    k = max(1, len(loops))
    w = (ku) // k
    x = (ku) % k


if flag:
    ans = sum(a)
else:
    sss = 0
    for i in range(x):
        sss += loops[i]
    ans = sum(a) - a[-1] + sum(loops) * w + sss
print(ans)

Solution (Python):
n,x,m=map(int,input().split())
ans=x
a=x
res=[x]
res2=0
r=0
for i in range(1,m+1):
    a=(a*a)%m
    if a==0:
        break
    if a in res:
        r=res.index(a)
        res2=i-r
        break
    else:
        ans+=a
        res.append(a)
b=[0]*m
for i in range(res2):
    b[i+1]=b[i]+res[r+i]
if res2==0:
    print(ans)
else:
    k=(n-r)//res2;l=(n-r)%res2
    ans+=b[res2]*(k-1)+b[l]
    print(ans)

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

lis=[0]*m

ans=x
ai=x
lis[ai]=[1,ans]
flg=0

for i in range(2,n+1):
    ai=(ai**2)%m
    if lis[ai]!=0:
        start=lis[ai][0]
        goal=i-1
        span=goal-start+1
        sumspan=ans-lis[ai][1]+ai
        flg=1
        break
    ans+=ai
    lis[ai]=[i,ans]

if flg:
    times=(n-goal)//span
    last=(n-goal)%span
    ans+=sumspan*times
    
    
    if last==1:
        ans+=ai
    for i in range(0,last-1):
        ans+=ai
        
        ai=(ai**2)%m
        if i == last-2:
            ans+=ai
    print(ans)
else:
    print(ans)

Solution (Python):
def binary_search(data, value):
    left = 0            
    right = len(data) - 1            
    while left <= right:
        mid = (left + right) // 2            
        if data[mid] == value:
            
            return mid
        elif data[mid] < value:
            
            left = mid + 1
        else:
            
            right = mid - 1
    return -1            

import heapq

n,x,mod = map(int,input().split())
c = [x]
heapq.heapify(c)
cc = [x]
num = x
count = 1
while True:
    num = pow(num, 2, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    heapq.heappush(c, num)
    cc.append(num)




ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)

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

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

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

d = [-1] * (M + 1)
out = [0]
a = X
ans = 0
for i in range(1, N + 1):
    ans += a
    d[a] = i
    out.append(a)
    a = a ** 2 % M
    if a == 0:
        print(ans)
        exit()

    if d[a] != -1:
        loop_num = i + 1 - d[a]
        remain = N - i
        ans += sum(out[d[a]:d[a] + loop_num]) * (remain // loop_num)
        ans += sum(out[d[a]:d[a] + (remain % loop_num)])
        break
print(ans)

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

count = [0 for _ in range(M)]
cumsum = [0]
now = X%M
nowcount = 1
while count[now] == 0:
  count[now] = nowcount
  cumsum.append(now + cumsum[-1])
  now = pow(now, 2, M)
  
  nowcount += 1




loop = cumsum[nowcount-1]-cumsum[count[now]-1]

if N < nowcount:
  print(cumsum[N])
else:
  ans = cumsum[nowcount-1]
 
  N -= (nowcount-1)
  f = nowcount - count[now]
  r = N%f
  q = N//f
 
  ans += q*loop + cumsum[count[now]-1+r] - cumsum[count[now]-1]
  print(ans)

Solution (Python):




import sys
from io import StringIO
import unittest
import collections





def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    cnt=collections.Counter()
    n,x,m=map(int, readline().rstrip().split())
    a=x
    if n==1:
        print(a)
        return
    t=-1
    i=2
    stock=0
    nnn=0
    ans=a
    gogo=False
    b=a
    f=-1
    while i <= n:
        a=(a*a)%m
        ans+=a
        cnt[a]+=1
        if gogo==False:
            if cnt[a] == 2:
                stock+=a
                if f<0:
                    f=i
            if cnt[a] == 3:
                ans-=a
                hani=i-f
                nokori=n-i+1
                ddd=nokori//hani
                ans+=stock*ddd
                i+=ddd*hani
                i-=1
                gogo=True
                a=b
        i+=1
        b=a
    print(ans)
    
    
    
    

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

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

mods = [0 for _ in range(M)]

x = X
f = False
res = 0
for i in range(N):
    if mods[x]:
        k = i
        l = i + 1 - mods[x]
        f = True
        break
    res += x
    mods[x] = i + 1
    x **= 2
    x %= M

if not f:
    res = 0
    for i in range(M):
        if mods[i]:
            res += i
    print(res)

else:
    x2 = x
    lsm = 0
    for i in range(k):
        if k - l <= i <= k - 1:
            lsm += x
        x **= 2
        x %= M
    loop, r = divmod(N - k, l)
    res += loop * lsm
    for i in range(r):
        res += x2
        x2 **= 2
        x2 %= M

    print(res)

Solution (Python):
import sys
import numpy as np

readline = sys.stdin.readline

n, x, m = map(int, input().split())
l = np.full(m+1,-1)
l[0] = x
s = set()
s.add(x)
lsum = [-1 for i in range(m+1)]
lsum[0] = x
for i in range(1,m+1):
    a = pow(int(l[i-1]),2,m)
    if a in s:
        if n <= i:
            print(lsum[n-1])
            sys.exit()
        j = np.where(l==a)[0][0]
        if j == 0:
            ans = lsum[i-1]
            n -= i
            ans += (lsum[i-1]) * (n//(i-j))
            if n % (i-j) == 0:
                print(ans)
                sys.exit()
            else:
                d = n % (i-j)
                ans += lsum[d-1]
                print(ans)
                sys.exit()
        else:
            ans = lsum[i-1]
            n -= i
            ans += (lsum[i-1] - lsum[j-1]) * (n//(i-j))
            if n % (i-j) == 0:
                print(ans)
                sys.exit()
            else:
                d = n % (i-j)
                ans += lsum[j+d-1] - lsum[j-1]
                print(ans)
                sys.exit()
    else:
        s.add(a)
        l[i] = a
        lsum[i] = lsum[i-1] + a

Solution (Python):
n,x,m=map(int,input().split())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n+1:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    
else:
    print(ans)

Solution (Python):
def resolve():
    
    
    
    
    n,x,m=map(int,input().split())
    l=[]
    ans=0
    cnt=0
    while (x not in l)and(cnt<=n):
      l.append(x)
      ans+=x
      cnt+=1
      x=(x**2)%m
    for i in range(len(l)):
      if x==l[i]:
        break
    lc=l[i:].copy()
    lc_cnt=(n-cnt)//len(lc)
    ans+=lc_cnt*sum(lc)+sum(lc[:(n-cnt)-lc_cnt*len(lc)])
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,x,m=nii()

ans=x
x_list=[x]
zan=0
for i in range(n-1):
  a=(x**2)%m
  ans+=a
  x=a
  if x in x_list:
    inx=x_list.index(x)
    zan=(n-1)-i-1

    inx=x_list.index(x)+1
    nx_list=x_list[inx:]+[x_list[inx-1]]

    if zan<=len(nx_list):
      ans+=sum(nx_list[:zan])
    else:
      num=zan//len(nx_list)
      q=zan%len(nx_list)
      ans+=sum(nx_list)*num
      ans+=sum(nx_list[:q])
    break
  else:
    x_list.append(x)

print(ans)

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

S = {X : 1}

path = [X]

cnt = 1
ans = X
a = X
for i in range(2, N + 1):
    a = a * a % M
    if a in S:
        cnt = i - S[a]
        break
    S[a] = i

    ans += a
    path.append(a)

pre_len = S[a] - 1

Q, R = divmod(N - pre_len - 1, len(path) - pre_len)

pre = sum(path[:pre_len])
cycle = sum(path) - pre

ans = a
for _ in range(R):
    a = a * a % M
    ans += a

print(pre + Q * cycle + ans)

Solution (Python):

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

F=[0 for i in range(10**5+1)]
for i in range(10**5+1):
    F[i]=pow(i,2,M)
    
Flag=[False for i in range(10**5+1)]
A_i=X
while True:
    A_i=F[A_i]
    if Flag[A_i]:
        st=A_i
        break
    Flag[A_i]=True

A_i=X
Sum_1=0
cnt=0
while True:
    if A_i==st:
        break
    cnt+=1
    Sum_1+=A_i
    A_i=F[A_i]

roop=1
A_i=st
Sum_2=0
while True:
    Sum_2+=A_i
    A_i=F[A_i]
    if A_i==st:
        break
    roop+=1

    
A_i=st
Sum_3=0
for i in range((N-cnt)%roop):
    Sum_3+=A_i
    A_i=F[A_i]
    
    
if N-cnt>roop:
    ans=Sum_1+Sum_2*((N-cnt)//roop)+Sum_3
elif N<=cnt:
    ans=0
    A_i=X
    for i in range(N):
        ans+=A_i
        A_i=F[A_i]

else:
    ans=Sum_1
    A_i=st
    for i in range(N-cnt):
        ans+=A_i
        A_i=F[A_i]

print(ans)

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, X, M = nn()

dic = dict()

ans = 0
cyc = 0
A = X
for i in range(N):
    if i != 0 and A in dic:
        cyc = i - dic[A][0]
        cyci = dic[A][0]
        r = ans - dic[A][1]
        t = dic[A][1]
        break

    dic[A] = (i, ans)
    ans += A
    A = A**2 % M

if cyc == 0:
    print(ans)
    exit(0)


ans = t + r * ((N-cyci)//cyc)

for i in range((N-cyci) % cyc):
    ans += A
    A = A**2 % M

print(ans)

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

d = {X:0}
l = [X]
s = X

for i in range(1,N):
  l+=[(l[i-1]**2)%M]
  s += l[i]
  if l[i] in d:
    dl = l[d[l[i]]+1:]
    s += sum(dl)*((N-i-1)//len(dl))
    if (N-i-1)%len(dl) != 0:
      s += sum(dl[0:(N-i-1)%len(dl)])
    break
  d[l[i]] = i
print(s)

Solution (Python):
def main():
  n, x ,m = map(int, input().split())
  a = [0, x]
  place = [-1]*m
  place[x] = 1
  num = 2
  while True:
    x = (x**2%m)
    if place[x] >= 0:
      break
    a.append(x)
    place[x] = num
    num += 1
  loop = num-place[x]
  loop_sum = sum(a[place[x]:])
  loop_st = sum(a[:place[x]])
  
  if n <= place[x]:
    print(sum(a[:n+1]))
  else:
    n -= place[x]-1
    print(loop_st + loop_sum*(n//loop) + sum(a[place[x]:n%loop+place[x]]))
  
if __name__ == "__main__":
  main()

Solution (Python):
import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1





A = [0] * (mod + 1)

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    temp = A[1]
    i = 1
    migi = 1
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    
    
    cycle_val = sum(A[hidari:migi])
    
    
    
    cycle = migi - hidari
    if cycle >= 2:

        kaisu = n // cycle
        amari = n % cycle - (hidari - 1)
        amari %= cycle
        kaisu = (n - (amari + hidari - 1)) // cycle
        amari_val = sum(A[hidari : hidari + amari])
        
        
        
        ans = saisho + cycle_val * kaisu + amari_val
    else:
        ans = 0
        if cycle == 0:
            for j in range(1, i + 1):
                ans += A[j]
        else:
            for j in range(1, i + 1):
                ans += A[j]
            ans += (n - i) * A[j]
print(ans)

Solution (Python):
import sys
from sys import exit
from math import gcd, factorial, ceil, floor, sqrt
from bisect import bisect_left, bisect_right
from copy import deepcopy
from heapq import heapify, heappop, heappush
from itertools import permutations, combinations, product, accumulate
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(10**7)

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

N, X, M = mi()

if X == 0:
    print(0)
    sys.exit()
if M == 1 or N == 1:
    print(X)
    sys.exit()

ans = 0
ls = []

s = set()
num = X
cur = 0
f = 0
while not num in s:
    s.add(num)
    cur += 1
    ls.append(num)
    if cur == N:
        f = 1
        break

    num = num**2%M
    if num == 0:
        f = 1
        break
    if num == 1:
        f = 2
        break
if f == 1:
    print(sum(ls[:min(cur, N)]))
    sys.exit()
m = [0] + list(accumulate(ls))
if f == 2:
    print(m[-1] + (N-len(ls)))
    sys.exit()

i = ls.index(num)
b = ls[i:]

a = (N-i)//len(b)

ind = (N-i) - a*len(b)

print(sum(ls[:i]) + sum(b)*a + sum(b[:ind]))

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

ans = 0
A = [X]
tmp = X

first=0
firstCnt=0
loop=0
loopLen=0
loopCnt=0
remain=0
remainCnt=0

induces=[ -1 for _ in range(M+1)]

for n in range(1,M+1):
	cur = ( tmp ** 2 ) % M
	if induces[ cur ] != -1:
		index = induces[ cur ]
		first = sum(A[:index])
		firstCnt = len(A[:index])
		loop = sum(A[index:])
		loopLen = len(A[index:])
		loopCnt = (N-firstCnt)//loopLen
		remainCnt = (N-firstCnt)%loopLen
		remain = sum(A[index:index+remainCnt])

		
		
		break
	induces[ cur ] = n
	A.append( cur )
	tmp = cur

ans = first + loop * loopCnt + remain
print( ans )

Solution (Python):
N,X,M=map(int,input().split())
A=[X]
A1=X
ans=0
for i in range(1,N):
    if 2*A1>M:
        A2=((M-A1)**2)%M
    else:
        A2=(A1**2)%M
    if A2 in A:
        num=A.index(A2)
        loop=i-num
        loop_A=A[num::]
        loop_val=sum(loop_A)
        rest=N-i
        x=rest%loop
        for _ in range(x):
            ans+=A[num]
            num+=1
        ans=ans+(rest//loop)*loop_val
        break
    else:
       A1=A2 
       A.append(A2)

print(sum(A)+ans)

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


A = [-1]*(M+100)
A[0] = X
i = 0
tmpans = 0
flag = False
check = [-1]*(M+1)
slice = -1
while i< N-1:
    newa = A[i]**2%M
    i+= 1
    if check[newa] != -1:
        flag = True
        slice = check[newa]
        break
    A[i] = newa
    check[newa] = i

if not flag:
    print(sum(A[:i+1]))

else:
    print(sum(A[:slice])+ sum(A[slice:i])*((N-slice)//(i-slice))+sum(A[slice:slice + (N-slice)%(i-slice)]))