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

idx = [-1] * M
A = []
total = 0
length = 0

while idx[X] == -1:
    A.append(X)
    idx[X] = length
    length += 1
    total += X
    X = pow(X, 2, M)

cycle = length - idx[X]
cycle_sum = sum(A[idx[X]:length])

ans = 0
if length >= N:
    print(sum(A[:N]))
else:
    ans += total
    N -= length
    l, m = divmod(N, cycle)
    ans += cycle_sum * l
    ans += sum(A[idx[X]:idx[X] + m])
    print(ans)

Solution (Python):
import sys
import re
import queue
import collections
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []


def main():
	N,X,M=i_map()

	Y = X

	went_array = []
	for i in range(0,M):
		went_array.append(-1)

	loop_flag = False
	first = -1
	second = -1
	value = -1
	for i in range(0,N):

		if(went_array[Y] != -1):
			loop_flag = True
			first = went_array[Y]
			second = i
			value = Y
			break

		went_array[Y] = i
		Y = (Y*Y) % M

	if(loop_flag == False):
		Z = X
		sum = 0

		for i in range(0,N):
			sum += Z
			Z = (Z*Z)%M

		print(sum)

	else:
		Z = X
		sum1 = 0
		for i in range(0,first):
			sum1 += Z
			Z = (Z*Z)%M

		Z = value
		cum = []
		cum.append(Z)
		Z = (Z*Z) %M
		for i in range(1,second-first):
			cum.append(cum[i-1]+Z)
			Z = (Z*Z) %M

		sum2 = ((N-first)//(second-first))*cum[second-first-1]

		if((N-first)%(second-first) == 0):
			print(sum1 + sum2)
		else:
			sum3 = cum[((N-first)%(second-first)-1)]
			print(sum1 + sum2 + sum3)


	return

if __name__ == '__main__':
	main()

Solution (Python):


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

a_list = [x]
a = x
i = 1
while (i<n and i < m+1):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    


    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    
    
    

print(ans)

Solution (Python):
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] < 0: 
    X[x] = len(P) 
    P.append(sum_p) 
    sum_p += x 
    x = x*x % m
cyc_times, nxt_len = divmod(n - X[x], len(P) - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Solution (Python):
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: 
    X[x] = len(P) 
    P.append(sum_p) 
    sum_p += x 
    x = x*x % m
cyc_times, nxt_len = divmod(n - X[x], len(P) - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Solution (Python):
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: 
    X[x] = len(P) 
    P.append(sum_p) 
    sum_p += x 
    x = x*x % m
P.append(sum_p) 
p_len = len(P) - 1
cyc_times, nxt_len = divmod(n - X[x], p_len - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Solution (Python):
N,X,M=map(int,input().split())
table=[X]
visited=[-1]*M
visited[X]=1

ans=X

for i in range(N-1):
    nx=table[i]**2
    nx%=M
    if visited[nx]>0:
        first=table.index(nx)
        oneloop=i+1-first
        rest=N-i-1
        loops=rest//oneloop
        totalofoneloop=sum(table[first:])
        ans+=totalofoneloop*loops
        remain=rest%oneloop
        ans+=sum(table[first:first+remain])
        print(ans)
        exit()
    else:
        table.append(nx)
        visited[nx]=1
        ans+=nx
 

print(ans)

Solution (Python):
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: 
    X[x] = len(P) 
    P.append(sum_p) 
    sum_p += x 
    x = x*x % m
P.append(sum_p) 

p_len = len(P) - 1
if n <= p_len:
    print(P[n]) 
    exit()

cyc_times, nxt_len = divmod(n - X[x], p_len - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_times, nxt_len = divmod(n-X[x], len(P) - X[x])
        cyc = (sum_p - P[X[x]]) * cyc_times
        remain = P[X[x] + nxt_len]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):

N,X,M = map(int,input().split())
p = [0] * (M+2)
sum = [0] * (M+2)
p[X] = 1
sum[1] = X

repeat_start = 0
repeat_end = 0

for i in range(2,N+1):
  X = (X**2) % M
  if p[X] != 0:
    repeat_start = p[X]
    repeat_end = i
    break
  else:
    sum[i] = sum[i-1] + X
    p[X] += i

if repeat_start == 0:
  print(sum[N])
else:
  repeat_cnt,mod=divmod(N-repeat_start+1,repeat_end-repeat_start)
  print(repeat_cnt*(sum[repeat_end-1]-sum[repeat_start-1]) + sum[repeat_start+mod-1])

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        n -= X[x]
        cyc = (sum_p - P[X[x]]) * (n // cyc_len)
        remain = P[X[x] + n % cyc_len]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):
class findroop:
    def __init__(self, n, nex):
        self.n = n
        self.next = nex

    
    
    
    
    def findroop(self, start):
        roopstart = -1
        roopend = -1
        visited = [False for i in range(self.n)]
        visitlist = []
        now = start
        for i in range(self.n):
            if visited[now]:
                roopend = i
                break
            else:
                visited[now] = True
                visitlist.append(now)
                now = self.next(now)
        
        for i in range(len(visitlist)):
            if visitlist[i] == now:
                roopstart = i

        return (roopstart, roopend)


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

fr = findroop(M, lambda x: x**2 % M)

roopstart, roopend = fr.findroop(X)

ans = 0
if N <= roopstart:
    for i in range(N):
        ans += X
        X = (X**2)%M
else:
    for i in range(roopstart):
        ans += X
        X = (X**2)%M

    N -= roopstart
    roopsum = 0
    for i in range(roopend-roopstart):
        roopsum += X
        X = (X**2) % M
    ans += (N // (roopend-roopstart)) * roopsum

    N = N % (roopend-roopstart)

    for i in range(N):
        ans += X
        X = (X**2) % M

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, X, M = LI()
    A = [X]
    seen = set()
    seen.add(X)
    while True:
        an = A[-1]
        an1 = ((an % M) * (an % M)) % M
        if an1 in seen:
            break
        else:
            A.append(an1)
            seen.add(an1)
    start_loop_i = 0
    for i, a in enumerate(A):
        if an1 == a:
            start_loop_i = i
            break
    loop_len = len(A) - start_loop_i
    loop_sum = sum(A[start_loop_i:])

    end = False
    ans = 0
    for i in range(start_loop_i):
        N -= 1
        ans += A[i]
        if N == 0:
            end = True
            break
    if end:
        print(ans)
        return

    ans += loop_sum * (N // loop_len)
    
    if N % loop_len > 0:
        N %= loop_len
        for i in range(N):
            ans += A[start_loop_i + i]
    print(ans)






main()

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

"""
id[X] Xを何番目に訪問したか。-1で無ければ訪問済み。
Xをメモ  A[i+1] = (A[i] * A[i]) % M
length = ループが終わるまでの長さ
"""

id = [-1] * M
A = []  
length = 0
total = 0
while id[X] == -1:
    A.append(X)
    id[X] = length
    length += 1
    total += X
    X = (X * X) % M
syuki = length - id[X]
syukisum = sum(A[id[X] : length])



ans = 0
if N <= length:
    ans = sum(A[:N])
else:
    ans += total
    N -= length
    loop, res = divmod(N, syuki)
    ans += syukisum * loop
    ans += sum(A[id[X] : id[X] + res])
print(ans)

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

chk = [0 for i in range(m)]
a = x
s = x
c = 0
ary = [x]
flg = False
while True:
  if c == n:
    break
  x = (x**2)%m
  s += x
  c += 1
  if chk[x]:
    flg = True
    break
  ary.append(x)
  chk[x] = c
if flg == False:
  print (sum(ary[:-1]))
  exit()
cyc = ary[chk[x]:]
l1 = len(cyc)
ss = ary[:chk[x]]
l2 = len(ss)
tot = sum(ss) + sum(cyc)*((n-l2)//l1) + sum(cyc[:((n-l2)%l1)])
print (tot)

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

f=1
w=[]
d=[0]*(m+2)
t=[0]
chk=n
p=x
for i in range(m+1):
    if i!=0: p=p*p%m
    if d[p]: break
    d[p]=1
    w.append(p)
    t.append(t[-1]+p)
    
    chk-=1
    if chk==0:
        print(t[-1])
        exit()
ans=0
a=w.index(p)
ans+=t[a]
n-=a
loo=len(w)-a
if n%loo==0:
    ans+=(t[-1]-t[a])*(n//loo)
else:
    ans+=(t[-1]-t[a])*(n//loo)
    ans+=t[a+n%loo]-t[a]
print(ans)

Solution (Python):
N,X,M = map(int,input().split())
L = [X]
S = set([X])
idx = N
MOD = 10**9+7
for i in range(1,N):
  X = (X**2%M)
  if len(S) != len(L):
    idx = L.index(X)
    break
  L.append(X)
  S.add(X)

if idx == N:
  print(sum(L[:idx]))
else:
  k = (N-idx)%len(L[idx:])
  print(sum(L[:idx])+((N-idx)//len(L[idx:]))*sum(L[idx:])+sum(L[idx:idx+k]))

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

A,color=[x],["white" for _ in range(m)]
color[x]="black"
while 1:
    num=A[-1]**2%m
    if color[num]=="black":
        A.append(num)
        break
    else:
        color[num]="black"
        A.append(num)

fixed,loop=[],[]
point=A[-1]
flag=0
for i in A[:-1]:
    if i==point:flag=1

    if flag:loop.append(i)
    else:fixed.append(i)

ans=0
if n<=len(fixed):print(sum(fixed[:n]))
else:
    ans +=sum(fixed)
    div,mod=divmod(n-len(fixed),len(loop))
    ans +=div*sum(loop)
    ans +=sum(loop[:mod])
    print(ans)

Solution (Python):
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, X, M = list(map(int, _in[0].split(' ')))  
    
    ans = 0
    A = X
    head_list = []
    head = set()
    repeat = set()
    for i in range(N):
        if A in head:
            ind = head_list.index(A)
            repeat = head_list[ind:]
            head = head_list[:ind]
            break
        else:
            head.add(A)
            head_list.append(A)
            A = pow(A, 2, M)

    if len(repeat) == 0:
        ans = sum(head)
    else:
        repeat_time = (N - len(head)) // len(repeat)
        tail_len = N - len(head) - repeat_time * len(repeat)
        ans = sum(head) + sum(repeat) * repeat_time + sum(repeat[:tail_len])
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N,X,M = map(int,input().split())
i = X%M
L = [i]
S = set([i])
i = i**2 % M
while not i in S:
    L.append(i)
    S.add(i)
    i = i**2 % M
index = L.index(i)
k = (N-index)//len(L[index:])
l = (N-index)%len(L[index:])


if N<index:
    ans = sum(L[:N])
else:
    ans = sum(L[:index]) + (k*sum(L[index:])) + sum(L[index:index+l])
print(ans)

Solution (Python):

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

tmp = x 
cnt = 0 
dup = 0 
a = [x] 
while True:
    tmp = (tmp*tmp)%m
    if tmp in a:
        dup = tmp 
        break
    cnt += 1
    a.append(tmp)

di = 0 
for i in range(len(a)):
    if a[i] == dup:
        di = i 


b = []
bs = 0 
for i in range(di, len(a)):
    bs += a[i]
    b.append(a[i])


bl = len(a)-di
sumbl = 0 

ans = 0 
for i in range(di):
    ans += a[i]
ans += (n-di)//bl * bs
for i in range((n-di)%bl):
    ans += b[i]

print(ans)

Solution (Python):

import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000


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

    dp = [0]
    dp.append(X)
    rp = 0
    rps = 0
    rps2 = 0
    for i in range(2, N+1):
        dp.append(dp[i-1]**2 % M)
        for j in range(1, i):
            if dp[i] == dp[j]:
                rp = 1
                rps = j
                rps2 = i
                break
        if rp != 0:
            break

    result = 0
    if rps > 0:
        for i in range(1, rps):
            result += dp[i]

        rc = (N - rps + 1) // (rps2 - rps)
        rpSum = 0
        for i in range(rps, rps2):
            rpSum += dp[i]
        result += rpSum * rc

        rca = (N - rps + 1) % (rps2 - rps)
        for i in range(rps, rps+rca):
            result += dp[i]
    else:
        for i in range(1, N+1):
            result += dp[i]

    
    print("{}".format(result))

if __name__ == '__main__':
    main()

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


table = [-1] * m
extra = []
l = 0
total = 0

while table[x] == -1:
    
    extra.append(x)
    table[x] = l
    l += 1
    total += x
    x = (x*x) % m 


c = l - table[x]


s = 0
for i in range(table[x], l):
    s += extra[i]

ans = 0


if n <= l:
    for i in range(n):
        ans += extra[i]
else:
    
    ans += total
    n -= l
    
    ans += s*(n//c)
    n %= c

    for i in range(n):
        ans += extra[table[x]+i]

print(ans)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        cyc = (sum_p - P[X[x]]) * ((n - X[x]) // cyc_len)
        remain = P[X[x] + (n - X[x]) % cyc_len] 
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(pre + cyc + nxt)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

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

p=[0]*(M+2)
sum=[0]*(M+2)
p[X]=1
sum[1]=X
f=0
for i in range(2,N+1):
    X=(X**2)%M  
    if p[X]!=0:
        j=p[X]
        f=i
        break
    else:
        sum[i]=X+sum[i-1]
        p[X]+=i

if f==0:
    print(sum[N])
else:
    d,mod=divmod(N-j+1,i-j)
    print(d*(sum[i-1]-sum[j-1])+sum[j+mod-1])

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

A = X
ans = A

visited = [0]*M
tmp = []

i = 2
while i <= N:
    A = (A*A) % M
    if visited[A] == 0:
        visited[A] = i
        tmp.append(A)
        ans += A
    else:
        ans += A
        loop_length = i-visited[A]
        loop_val = tmp[-1*loop_length:]
        loop_count = (N-i) // loop_length
        ans += sum(loop_val) * loop_count
        visited = [0]*M
        i += loop_length * loop_count

    i += 1

print(ans)

Solution (Python):
N, X, M = map(int, input().split())
record_sum = [0, ]
flag = [False for _ in range(M)]
An = X


record_sum.append(An)
flag[An] = 1

for i in range(2, M + 2):
    An = pow(An, 2, M)  
    record_sum.append(record_sum[-1] + An)

    if flag[An]:
        start_index = flag[An]
        initial_cost = record_sum[start_index - 1]
        cycle_cost = record_sum[-1] - record_sum[start_index]
        cycle_length = i - start_index
    else:
        flag[An] = i

if start_index >= N:
    print(record_sum[N])

else:
    ans = 0
    ans += ((N - start_index) // cycle_length) * cycle_cost
    ans += record_sum[(N - start_index) % cycle_length + start_index]

    print(ans)

Solution (Python):
N,X,M=map(int,input().split())
A=[X]
x=(A[0]**2)%M
i=0
while not x in A:
    A.append(x)
    i+=1
    x=(x**2)%M

loopid=A.index(x)
looplen=i-loopid+1
loopsum=sum(A[loopid:])
startsum=sum(A[:loopid])

ans=0
if N-1<loopid:
    ans=sum(A[:N])
else:
    loopnum=(N-1-loopid+1)//looplen if looplen else N-1-loopid
    rest=N-1-(loopid+looplen*loopnum)+1
    ans+=startsum
    ans+=loopnum*loopsum
    ans+=sum(A[loopid:loopid+rest])
print(ans)

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

A,color=[x],["white" for _ in range(m)]
color[x]="gray"
while 1:
    num=A[-1]**2%m
    if color[num]=="gray":
        A.append(num)
        break
    else:
        color[num]="gray"
        A.append(num)

fixed,loop=[],[]
point=A[-1]
flag=0
for i in A[:-1]:
    if i==point:flag=1

    if flag:loop.append(i)
    else:fixed.append(i)

ans=0
if n<=len(fixed):print(sum(fixed[:n]))
else:
    ans +=sum(fixed)
    div,mod=divmod(n-len(fixed),len(loop))
    ans +=div*sum(loop)
    ans +=sum(loop[:mod])
    print(ans)

Solution (Python):
class RhoSequence:
    """
    A_1 = start, A_{i+1} = f(A_i) で、かつA_i が一定の整数の範囲内に収まるような数列に対するクエリを処理するクラス

    例：A_1=3, f(x)=x*x%7 -> A_2=2, A_3=4, A_4=2, A_5=4, ...
    """

    def __init__(self, f, start, val_max, val_min=0):
        self.f = f
        self.start = start
        self.val_max = val_max
        self.val_min = 0

        width = val_max - val_min + 1
        n = [-1] * width
        n[start-val_min] = 1
        route = [start] 
        loop_start_n = -1 
        x = start
        for i in range(2, width):
            fx = f(x)
            if n[fx] != -1:
                loop_start_n = n[fx]
                break
            route.append(fx)
            n[fx] = i
            x = fx
        self.route = route
        self.route_before_loop = route[:loop_start_n-1]
        self.loop_start_n = loop_start_n
        self.cycle = self.route[loop_start_n-1:]
        self.cycle_length = len(self.cycle)
    
    def get_nth_value(self, n):
        """
        n番目の数 A_n を返す
        """
        if n < self.loop_start_n:
            
            return self.route_before_loop[n-1]
        
        n -= self.loop_start_n
        return self.cycle[n%self.cycle_length]

    def sum_until_n(self, n):
        """
        A_1 から A_n までの合計を返す
        """
        if n < self.loop_start_n:
            
            return sum(self.route_before_loop[:n])

        ret = sum(self.route_before_loop)
        n -= self.loop_start_n - 1
        n_loop = n // self.cycle_length
        ret += n_loop * sum(self.cycle)
        n -= n_loop * self.cycle_length
        ret += sum(self.cycle[:n])
        return ret

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

    rs = RhoSequence(lambda x: x*x%M, X, M-1, 0)

    
    print(rs.sum_until_n(N))

if __name__ == '__main__':
    main()

Solution (Python):
N,X,M=map(int,input().split())
a=[0]*(M)
A=X%M
a[A]=1
ans=A
Ans=[A]
flag=0
for i in range(N-1):
    A=A*A%M
    if A==0:
        break
    if a[A]==1:
        flag=1
        break
    a[A]=1
    ans+=A
    Ans.append(A)
if flag==1:
    for num in range(len(Ans)):
        if A==Ans[num]:
            break
    n=len(Ans)-num
    b=sum(Ans[:num])
    x=(N-num)//n
    y=(N-num)%n
    Sum=b+(ans-b)*(x)+sum(Ans[num:y+num])
else:
    Sum=sum(Ans)
print(Sum)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x]+nxt_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(n):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x]+nxt_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        asum00[icnt]=asum
        if chk[ai]!=-1:
            icnt0=chk[ai]
            asum0=asum00[icnt0]
            break
        chk[ai]=icnt
        asum+=ai
        ai=f(ai,m)
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        asum00[icnt]=asum
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        chk[ai]=icnt

        asum+=ai
        ai=f(ai,m)
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0

    nk=n0//icntk
    nr=n0%icntk



    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Solution (Python):
n, x, m = map(int, input().split())
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(n):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = sum(P[:X[x]])
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = sum(P[X[x]: X[x] + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = sum(P[:X[x]])
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = sum(P[X[x]: X[x] + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

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

flag = [False]*m
a = []
while not flag[x]:
    flag[x] = True
    a.append(x)
    x = pow(x, 2, m)
loop_start_idx = a.index(x)
loop_len = len(a) - loop_start_idx
loop_count = (n - loop_start_idx)//loop_len
loop_amari = (n-loop_start_idx)%loop_len
ans = sum(a[:loop_start_idx])
ans += sum(a[loop_start_idx:])*loop_count
ans += sum(a[loop_start_idx: loop_start_idx + loop_amari])
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
ans = 0
if x == 0:
    print(0)
    exit()
elif x == 1:
    print(n)
    exit()

flag = [False]*m
a = []
while not flag[x]:
    flag[x] = True
    a.append(x)
    x = pow(x, 2, m)
loop_start_idx = a.index(x)
loop_len = len(a) - loop_start_idx
loop_count = (n - loop_start_idx)//loop_len
loop_amari = (n-loop_start_idx)%loop_len
ans = sum(a[:loop_start_idx])
ans += sum(a[loop_start_idx:])*loop_count
ans += sum(a[loop_start_idx: loop_start_idx + loop_amari])
print(ans)

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)







else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Solution (Python):
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] 
sum_p = 0 
X = [-1] * m 
for i in range(mn):
    if X[x] > -1:
        pre_len = X[x]
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        pre = sum(P[:pre_len])
        cyc = (sum_p - pre) * ((n - pre_len) // cyc_len)
        nxt = sum(P[pre_len: pre_len + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Solution (Python):
N, X, M = map(int, input().split())
mod = M
A = [X]
AS = set()
AS.add(X)
cnt = 0
loop = -1
tail = -1
loop_sum = X
tail_sum = 0
while True:
    cnt += 1
    nex = pow(A[-1], 2, mod)
    if nex in AS:
        break
    A.append(nex)
    loop_sum += nex
    AS.add(nex)

for i, a in enumerate(A):
    if a == nex:
        tail = i
        loop = cnt - tail
        A = A[i:]
        break
    tail_sum += a
    loop_sum -= a

ans = tail_sum + (N - tail)//loop * loop_sum
N -= tail
N %= loop

for i in range(N):
    ans += A[i]

print(ans)

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai,icnt,asum=x,0,0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=f(ai,m)
        icnt+=1
    ai0,icnt0,asum0=x,0,0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=f(ai0,m)
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0

    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Solution (Python):

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)

        asum+=ai
    print(asum)   
else:
    aa=[]
    ai,icnt,asum=x,0,0


    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=f(ai,m)

        icnt+=1
    ai0,icnt0,asum0=x,0,0


    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=f(ai0,m)

            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0

    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    air,asumr=ai,0

    for i in range(nr):
        asumr+=air
        air=f(air,m)

    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Solution (Python):

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:
        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:

        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)