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())
tmp = [None]*m
for i in range(m):
    tmp[i] = i*i%m
pos = [tmp]
accu = [tmp]
for i in range(40):
    tmp1 = [None]*m
    tmp2 = [None]*m
    for j in range(m):
        tmp1[j] = pos[-1][pos[-1][j]]
        tmp2[j] = accu[-1][pos[-1][j]] + accu[-1][j]
    pos.append(tmp1)
    accu.append(tmp2)
now = x
ans = x
for i in range(40):
    if (n-1)>>i&1:
        ans += accu[i][now]
        now = pos[i][now]
print(ans)

Solution (Python):
n,x,m=map(int,input().split())
id=[-1 for i in range(m+1)]
s=[]
c=0
while id[x]==-1:
    id[x]=c
    c+=1
    s.append(x)
    x=x*x%m
d=c-id[x]
ans=0
if n<=d:
    for i in range(n):
        ans+=s[i]
else:
    for i in range(id[x]):
        ans+=s[i]
    n-=id[x]
    sum=0
    for i in range(d):
        sum+=s[id[x]+i]
    ans+=(n//d)*sum
    n=n%d
    for i in range(n):
        ans+=s[id[x]+i]
print(ans)

Solution (Python):
n,x,mod = map(int,input().split())
num = []
ans = cnt = 0
ch = x
while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch
        break
    ch *= ch
    ch %= mod

index = num.index(st)

if (len(num)-index) != 0:
    rest = (n-index)%(len(num)-index)
    qu = (n-index)//(len(num)-index)
else:
    rest = n
    qu = 0
if n <= index + 1:
    ans = sum(num[:n])
else:
    ans = sum(num[:index]) + sum(num[index:index+rest]) + sum(num[index:])*qu
print(ans)

Solution (Python):

def main():
    n, x, m = map(int, input().split())
    a = [x]
    repeat_dic = {x: 0}
    cnt = 1
    repeat_start = -1
    repeat_end = -1
    for i in range(1, n):
        num = a[i-1] ** 2 % m
        a.append(num)
        if not num in repeat_dic.keys():
            repeat_dic[num] = cnt
            cnt += 1
        else:
            repeat_start = repeat_dic[num]
            repeat_end = i
            break
    if repeat_start == -1:
        ans = sum(a)
    else:
        nokori = n - repeat_start
        repeat_num = repeat_end - repeat_start
        q, mod = divmod(nokori, repeat_num)

        ans = sum(a[:repeat_start]) + q*sum(a[repeat_start:repeat_end]) + \
            sum(a[repeat_start: repeat_start + mod])
    
    
    
    
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x


while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch 
        break
    ch *= ch
    ch %= mod

stnum = num.index(st)

if 0 in num:
    ans = sum(num[:n])
else:
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum) 
        qu = (n-stnum)//(len(num)-stnum)  
    else:
        rest = n
        qu = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*qu
print(ans)

Solution (Python):
n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x


while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch 
        break
    ch *= ch
    ch %= mod


for i in range(len(num)):
    if num[i] == st:
        stnum = i 
        break
else:
    stnum = len(num) - 1


if 0 in num:
    ans = sum(num[:n])
else:
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum) 
        qu = (n-stnum)//(len(num)-stnum)  
    else:
        rest = n
        qu = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*qu
print(ans)

Solution (Python):
n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x
while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch 
        break
    ch *= ch
    ch %= mod
for i in range(len(num)):
    if num[i] == st:
        stnum = i 
        
        break
else:
    stnum = len(num) - 1
if 0 in num:
    ans = sum(num[:n])
else:
    
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum)
        sho = (n-stnum)//(len(num)-stnum)
        
    else:
        rest = n
        sho = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*sho
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
idx = [-1] * m
a = []
leng = 0
tot = 0

while idx[x] == -1:
    a.append(x)
    idx[x] = leng
    leng += 1
    tot += x
    x = (x*x)%m

c = leng - idx[x]
s = 0
for i in range(idx[x], leng):
    s += a[i]

ans = 0
if n<=leng:
    for i in range(n):
        ans += a[i]
else:
    ans += tot
    n -= leng
    ans += s*(n//c)
    n %= c
    for i in range(n):
        ans += a[idx[x]+i]

print(ans)

Solution (Python):
n, x, m = map(int, input().split())
idx = [-1] * m
a = []
leng = 0
tot = 0

while idx[x] == -1:
    a.append(x)
    idx[x] = leng
    leng += 1
    tot += x
    x = (x*x)%m

c = leng - idx[x]
s = 0
for i in range(idx[x], leng):
    s += a[i]

ans = 0
if n<=leng:
    for i in range(n):
        ans += a[i]
else:
    ans += tot
    n -= leng
    ans += s*(n//c)
    n %= c
    for i in range(n):
        ans += a[idx[x]+i]

print(ans)

Solution (Python):
n,x,m=map(int,input().split())
order=[-1 for i in range(m)] 
index=0 
a=[] 
while order[x]==-1: 
  order[x]=index 
  a.append(x)
  x=(x**2)%m
  index+=1
tmp=sum(a[order[x]:index]) 
t=index-order[x] 
if n-1<order[x]: 
  print(sum(a[:n]))
else:
  sum1=sum(a[:order[x]]) 
  x1=n-order[x] 
  n1=x1//t 
  n2=x1%t
  print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

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

nxt = X
lst = []
dic = {}

for i in range(M + 1):
    if nxt in dic:
        loop_st = dic[nxt]
        loop_ed = i - 1
        break

    lst.append(nxt)
    dic[nxt] = i

    nxt = (nxt ** 2) % M


v = N - loop_st
q, r = divmod(v, loop_ed - loop_st + 1)

pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])
print(pre_sum + loop_sum + post_sum)

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

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

SeqToNum = []
NumToSeq = {}

while not X in NumToSeq:
    NumToSeq[X] = len(SeqToNum)
    SeqToNum.append(X)
    X = X * X % M

if N <= NumToSeq[X]:
    ans = 0
    for i in range(N):
        ans += SeqToNum[i]
else:
    ans = 0
    for i in range(NumToSeq[X]):
        ans += SeqToNum[i]
    N -= NumToSeq[X]
    
    cycleScore = 0
    cycle = len(NumToSeq) - NumToSeq[X]
    for i in range(NumToSeq[X], len(NumToSeq)):
        cycleScore += SeqToNum[i]
    ans += cycleScore*(N//cycle)
    N %= cycle
    
    for i in range(NumToSeq[X], NumToSeq[X] + N):
        ans += SeqToNum[i]

print(ans)

Solution (Python):
n, x, m = map(int, input().split())
result = [x]
for i in range(m):
    y = (result[-1] * result[-1]) % m
    if y in result:
        start = result.index(y)
        end = i
        break
    result.append(y)

loop = result[start:]
a = start
b = (n - a) // len(loop)
c = (n - a) % len(loop)
ans = sum(result[:a]) + (sum(loop) * b) + sum(loop[:c])
print(ans)

Solution (Python):








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

def next(x):
    ret = pow(x,2,m)
    return ret

seen = set([])
seqs = []
for i in range(m+1):
    seen.add(x)
    seqs.append(x)
    x = next(x)
    if x in seen:
        break
start = seqs.index(x)
lp = len(seqs) - start

lpsum = sum(seqs[start:])
lptimes = (n-(start+lp)+(lp-1))//lp
ret_sum = lpsum * lptimes
n -= lp * lptimes
ret_sum += sum(seqs[:n])
ret_val = seqs[n-1]

print(ret_sum)

Solution (Python):









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

seen = set([])
seqs = []
for i in range(m+1):
    seen.add(x)
    seqs.append(x)
    x = pow(x,2,m)
    if x in seen:
        break
start = seqs.index(x)
lp = len(seqs) - start

lpsum = sum(seqs[start:])
lptimes = (n-(start+lp)+(lp-1))//lp
ret_sum = lpsum * lptimes
n -= lp * lptimes
ret_sum += sum(seqs[:n])
ret_val = seqs[n-1]

print(ret_sum)

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

order=[-1 for i in range(m)]
index=0

a=[]
while(order[x]==-1):
    order[x]=index
    a.append(x)
    x=(x**2)%m
    index+=1

tmp=sum(a[order[x]:index])
T=index-order[x]
if(n-1<order[x]):
    print(sum(a[:n]))
else:
    
    sum1=sum(a[:order[x]])
    
    x1=n-order[x]
    
    n1=x1//T
    n2=x1%T
    print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

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

order=[-1 for i in range(m)]
index=0

a=[]
while(order[x]==-1):
    order[x]=index
    a.append(x)
    x=(x**2)%m
    index+=1

tmp=sum(a[order[x]:index])
T=index-order[x]
if(n-1<order[x]):
    print(sum(a[:n]))
else:
    
    sum1=sum(a[:order[x]])
    
    x1=n-order[x]
    
    n1=x1//T
    n2=x1%T
    print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

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

ans = []
c = [0]*m
flag = False
for i in range(n):
    if c[x] == 1:
        flag = True
        break
    ans.append(x)
    c[x] = 1
    x = x**2 % m
if flag:
    p = ans.index(x)
    l = len(ans) - p
    d, e = divmod(n-p, l)
    print(sum(ans[:p]) + d*sum(ans[p:]) + sum(ans[p:p+e]))
else:
    print(sum(ans))

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

ans = []
c = [0]*m
flag = False
for i in range(n):
    if c[x] == 1:
        flag = True
        break
    ans.append(x)
    c[x] = 1
    x = x**2 % m
if flag:
    p = ans.index(x)
    l = len(ans) - p
    d, e = divmod(n-p, l)
    print(sum(ans[:p]) + d*sum(ans[p:]) + sum(ans[p:p+e]))
else:
    print(sum(ans))

Solution (Python):

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

    cycle = [False] * M
    A = []
    for i in range(N):
        if cycle[X]:
            break
        cycle[X] = True
        A.append(X)
        X = X ** 2 % M

    
    loop_start = 0
    for i in range(len(A)):
        if A[i] == X:
            loop_start = i
            break

    
    ans = sum(A[:loop_start])
    N -= loop_start

    
    A = A[loop_start:]

    loops = N // len(A)
    rest = N % len(A)
    
    ans += sum(A) * loops + sum(A[:rest])

    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))

n,x,m=MI()
stock=[]
for _ in range(1,n+1):
    if x not in stock:
        stock.append(x)
        x=(x**2)%m
        continue
    else:
        start=stock.index(x)
        repeat=stock[start:]
        l=len(repeat)
        n-=start
        sho=n//l
        amari=n%l
        s=sum(repeat)
        rest=0
        if amari!=0:
            for j in range(amari):
                rest+=repeat[j]
        print(s*sho+rest+sum(stock[:start]))
        sys.exit()
print(sum(stock))

Solution (Python):
N, X, M = map(int, input().split())
count_memo = [-1] * 10**6 
num_memo = [0] 

a = X
count = 1
count_memo[a] = count
num_memo.append(a)
for i in range(1, N):
    a = a**2 % M
    if count_memo[a] == -1:
        count += 1
        count_memo[a] = count
        num_memo.append(a)
    else:
        break

if count == N:
    answer = sum(num_memo)
else:
    
    count_before_cycle = count_memo[a] - 1
    sum_before_cycle = sum(num_memo[:count_before_cycle+1])
    
    count_cycle = count - count_before_cycle
    sum_cycle = sum(num_memo[count_before_cycle+1:])
    
    cycle_count = (N - count) // count_cycle
    sum_after_cycle = sum_cycle * cycle_count
    
    remain_count =  (N - count) % count_cycle
    sum_remain = sum(num_memo[count_before_cycle+1:count_before_cycle+1 + remain_count])

    answer = sum_before_cycle + sum_cycle + sum_after_cycle + sum_remain

print(answer)

Solution (Python):
N, X, M = map(int, input().split())
sup = 10**11
db = [[0]*M for _ in range(sup.bit_length())]
dbcum = [[0]*M for _ in range(sup.bit_length())]
db[0] = [i**2 %M for i in range(M)]
dbcum[0] = [i**2 %M for i in range(M)]
for i in range(1,sup.bit_length()):
  for j in range(M):
    db[i][j] = db[i-1][db[i-1][j]]
    dbcum[i][j] = dbcum[i-1][j]+dbcum[i-1][db[i-1][j]]
ans = X
p = 0
N -= 1
while N:
  if N%2:
    ans += dbcum[p][X]
    X = db[p][X]
  p += 1
  N >>= 1
print(ans)

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

ans = 0
C = [0]
Xd = [-1] * (M+1)

for i in range(N):
    x = X if i==0 else x**2 % M
    
    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

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

ans = 0
C = [0]
Xd = [-1] * (M+1)

for i in range(N):
    x = X if i==0 else x**2 % M
    
    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

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

ans = 0
C = [0]
Xd = [-1] * (M+1)

for i in range(N):
    if i == 0:
        x = X
    else:
        x = x**2 % M
    
    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
i = 1

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

Solution (Python):

import base64
import subprocess
import zlib


exe_bin = "c%1E9eQ*@VmGAu!T98;RSl|V0So>t3WXxI%0wiqCT7AGQtU!lE%mu@++FhY7_CwyC1wmXfiGX;rY|JI86!%$N?k?w0m4NT6E-qi?EQ~>LAF&|0

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):






def modinv(n,p):
    return pow(n,p-2,p)

def main():
    
    

    n, x, m = [int(x) for x in input().split()]
    series = []
    prev = set()
    repeat = []
    ans = 0
    y = x
    repeat_key = -1
    while True:
        if y not in prev:
            prev.add(y)
            series.append(y)
            y = (y * y) % m
        else:
            break

    repeat_key = y
    while True:
        repeat.append(y)
        y = (y * y) % m
        if y == repeat_key:
            break
    
    

    if n <= len(series):
        print(sum(series[:n]))
    else:
        n -= len(series)
        s1 = sum(series)
        s2 = sum(repeat) * (n//len(repeat))

        n %= len(repeat)
        print(s1 + s2 + sum(repeat[:n]))




py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Solution (Python):
n,x,m=map(int,input().split())
visited=set()
visited_l=[]
loop=set()
loop_l=[]
visited.add(x)
visited_l.append(x)
xc=x
for i in range(m):
    xc=(xc**2)%m
    if xc in visited and not(xc in loop):
        loop.add(xc)
        loop_l.append(xc)
    elif xc in visited and xc in loop:
        break
    else:
        visited.add(xc)
        visited_l.append(xc)
s=len(visited_l)
t=len(loop_l)



if n<=s:
    

    print(sum(visited_l[:n]))
elif n<=s+t:
    print(sum(visited_l)+sum(loop_l[:n-s-t]))

else:
    ans=sum(visited)
    n=n-s
    ans+=(sum(loop_l)*(n//t))
    ans+=sum(loop_l[:n%t])
    print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

numlist = [-1] * M

num = X
ans = num
roop_start = -1
for i in range(N-1):
    new_num = (num * num) % M
    if numlist[num] == -1:
        numlist[num] = new_num
        ans += new_num
        num = new_num
    else:
        roop_start = num
        break

num = roop_start
if roop_start == -1:
    print(ans)
else:
    roop_sum = [num]
    for i in range(N-1):
        new_num = numlist[num]
        numlist[num] = -1
        if numlist[new_num] == -1:
            break
        else:
            roop_sum.append(roop_sum[-1] + new_num)
            num = new_num
        
    if numlist[X] != -1:
        count = 0
        ans = 0
        for i in range(M):
            if numlist[i] != -1:
                ans += i
                count += 1
        N -= count
    else:
        ans = 0

    size = len(roop_sum)
    div = N // size
    rest = N % size
    ans += div * roop_sum[-1]
    if rest != 0:
        ans += roop_sum[rest-1]
    print(ans)

Solution (Python):
n,x,m=map(int,input().split())
s=x
t={x}
u=[x]
for i in range(1,n):
    if(x:=pow(x,2,m))in t:
        j=u.index(x)
        s=sum(u[:j])
        u=u[j:]
        s+=(n-j)//len(u)*sum(u)
        s+=sum(u[:(n-j)%len(u)])
        break
    s+=x
    t|={x}
    u+=x,
print(s)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(readline())


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


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd


def lcm(a, b):
    
    g = gcd(a, b)
    return a // g * b



















N, X, M = ints()
A = [X]
for i in range(M):
    A.append(pow(A[-1], 2, M))  


if N < M:
    exit(sum(A[:N]))

if M == 1:
    exit(0)


visited = set()
for i in range(M):
    if A[i] in visited:
        len_total = i
        break
    visited.add(A[i])

s = A.index(A[len_total])
cut = A[:s]
loop = A[s:len_total]



ans = sum(cut)
N -= len(cut)

ans += sum(loop) * (N // len(loop))
ans += sum(loop[:N % len(loop)])
print(ans)

Solution (Python):
N,X,M = map(int,input().split())
ans = X
N -= 1
divs,loop = [],[]
x = X**2%M
for _ in range(M):
    if x%M != 0:
        if x%M in divs:
            loop = divs[divs.index(x%M):]
            start = divs[:divs.index(x%M)]
            break
        else:
            divs.append(x%M)
            x = x**2
            x %= M
    else:
        start = divs
        break
if N >= len(start):
    ans += sum(start)
    if loop:
        cycle = (N-len(start))//len(loop)
        remain = (N-len(start))%len(loop)
        ans += sum(loop)*cycle + sum(loop[:remain])
else:
    ans += sum(start[:N])
print(ans)

Solution (Python):
N, X, M = map(int, input().split())
list = [0] * M
a = []
A = X
for i in range(N):
    if list[A] != 0:
        break
    list[A] = 1
    a.append(A)
    A = A * A % M
 
for i in range(len(a)):
    if a[i] == A:
        break
j = i
 
result = sum(a[:j])
a = a[j:]
N -= j
x = N // len(a)
y = N % len(a)
result += sum(a) * x + sum(a[:y])
print(result)

Solution (Python):


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

used = [0]*(m+1)
used_list=[]
pre=x

flag0=False
s=-1;t=-1
for i in range(m+1):
    if pre==0:
        flag0=True
        break
    now=(pre*pre)%m
    if used[pre]:
        s=used[pre]
        break
    used[pre]=i
    used_list.append(pre)
    pre=now
    
l=len(used_list[s:])
try:
    ans=sum(used_list[:s])+sum(used_list[s:])*((n-s)//l)+sum(used_list[s:s+(n-s)%l])
    if not flag0:
        print(ans)
    else:
        print(sum(used_list))
except:
    print(sum(used_list))

Solution (Python):
N,X,M=map(int,input().split())
a=X
ls=[X]
point=N
for i in range(N):
  a=a*a%M
  if a in ls:
    point=ls.index(a)
    break
  else:
  	ls.append(a)
initial=len(ls[:point])
cycle_len=len(ls[point:])
cycle_sum=sum(ls[point:])
cycles=(N-initial)//cycle_len
cycles_rem=(N-initial)%cycle_len
print(sum(ls[:point])+cycles*cycle_sum+sum(ls[point:point+cycles_rem]))

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

id = [-1] * M
a = []
l = 0
tot = 0
while id[X] == -1:
    a.append(X)
    id[X] = l
    l += 1
    tot += X
    X = X ** 2 % M

c = l - id[X]
s = 0
for i in range(id[X], l):
    s += a[i]

ans = 0
if N <= l:
    for i in range(N):
        ans += a[i]
else:
    ans += tot
    N -= l
    ans += s * (N // c)
    N %= c
    for i in range(N):
        ans += a[id[X] + i]

print(ans)

Solution (Python):

N, X, M = map(int, input().split())  
happend = set()
A = [X]
MOD = M

start = 0
for _ in range(N-1):
    if A[-1]**2 % MOD not in happend:
        happend.add(A[-1]**2 % MOD)
        A.append(A[-1]**2 % MOD)
    else:
        start = A.index(A[-1]**2 % MOD)
        break

roop_count = (N-start)//len(A[start:])

ans = sum(A[:start]) + sum(A[start:])*roop_count + sum(A[start:start+(N-start) % len(A[start:])])

print(ans)

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

num, lst = set(), []
for i in range(n):
    num.add(x), lst.append(x)
    x = x ** 2 % m
    if x in num:
        cnt, idx = i + 1, lst.index(x)
        break

ans = sum(num)
if x in num:
    div, mod = divmod(n - cnt, len(lst) - idx)
    ans += sum(lst[idx:]) * div
    ans += sum(lst[idx:idx + mod])
print(ans)

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

num, lst = set(), []
for i in range(n):
    num.add(x), lst.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i + 1, lst.index(x)
        break

ans = sum(num)
if x in lst:
    div, mod = divmod(n - cnt, len(lst) - idx)
    ans += sum(lst[idx:]) * div
    ans += sum(lst[idx:idx + mod])
print(ans)

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

num, lst = set(), []
for i in range(n):
    num.add(x), lst.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i + 1, lst.index(x)
        break

ans = sum(num)
if x in lst:
    div, mod = divmod(n - cnt, len(lst) - idx)
    ans += sum(lst[idx:]) * div
    ans += sum(lst[idx:idx + mod])
print(ans)

Solution (Python):
N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    isused[X] = True
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

Solution (Python):
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind])
        syo, r = divmod(n, l)
        s = s + sum(seq[ind:]) * (syo-1)
        if r != 0:
            for j in range(ind, ind+r):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

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

l = [X]
a = X
k = 0
for i in range(M):
    if a**2%M not in l:
        l.append(a**2%M)
        a = a**2%M
    else:
        k = l.index(a**2%M)
        break
sum = 0
for i in range(k,len(l)):
    sum += l[i]

ans = 0

ans += ((N-k)//(len(l)-k))*sum

for i in range(min(k,N)):
    ans += l[i]

for i in range(1,(N-k)%(len(l)-k)+1):
    ans += l[k+i-1]

print(ans)

Solution (Python):
import sys
import numpy as np
import math
import collections
import copy
import decimal
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations
N, X, M = map(int, input().split())

def f(X, M):
    if X**2 >= M:
        return X**2 % M
    else:
        return X**2
appear = np.full(M, -1)
seq = []
fx = X
appear[fx] = 0
seq.append(fx)
for i in range(1, N):
    fx = f(fx, M)

    if appear[fx] != -1:
        loop_st = appear[fx]
        loop_en = i
        break
    seq.append(fx)
    appear[fx] = i
seq.insert(0, 0)
seq_sum = np.cumsum(seq)

if N <= len(seq)-1 :
    print(seq_sum[N])
else:
    
    lp_b = seq_sum[loop_st-1]
    
    loop_num = (len(seq_sum)-1) - loop_st
    qu = (N-(loop_st)) // loop_num
    mo = (N-(loop_st)) % loop_num
    lp_sum = (seq_sum[-1] - seq_sum[loop_st]) * qu
    lp_en = seq_sum[loop_st+mo] - seq_sum[loop_st-1]
    print(lp_b+lp_sum+lp_en)

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

pt = [[0] * (M+100) for i in range(70)]
to = [[0] * (M+100) for i in range(70)]
for i in range(M+1):
    to[0][i] = (i*i) % M
    pt[0][i] = i

for i in range(65):
    for j in range(M+1):
        to[i+1][j] = to[i][to[i][j]]
        pt[i+1][j] = pt[i][j] + pt[i][to[i][j]]

ans = 0
for i in range(60):
    if (N>>i)&1:
        ans += pt[i][X]
        X = to[i][X]

print(ans)

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

lst, num = set(), []
for i in range(n):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i + 1, num.index(x)
        break

ans = sum(num)
if x in lst:
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:]) * div
    ans += sum(num[idx:idx + mod])
print(ans)

Solution (Python):
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
def solve(N,X,M):
    seen=set()
    order_seen=[]
    while X not in seen:
        seen.add(X)
        order_seen.append(X)
        X=f(X,M)
    pos=order_seen.index(X)  
    if pos>N:  
        return sum(order_seen[:N])
    terms_before_cycle=order_seen[:pos]
    sum_terms_before_cycle=sum(terms_before_cycle)
    ans=sum_terms_before_cycle
    terms_in_cycle=order_seen[pos:]
    sum_cycle=sum(terms_in_cycle)
    length_cycle=len(terms_in_cycle)
    number_remaining_terms=N-pos
    mult_factor=(number_remaining_terms)//length_cycle
    ans+=(sum_cycle*mult_factor)
    numb_remain=(number_remaining_terms)%length_cycle
    ans+=sum(terms_in_cycle[:numb_remain])
    return ans


def f(A,M):
    return pow(A,2,M)

N,X,M=readMap()
print(solve(N,X,M))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, x, m = map(int,input().split())
    sum_lis = [-1] * m 
    a_lis_i = [-1] * m 
    a = x
    sum_a = a
    sum_lis[a] = sum_a
    a_lis_i[a] = 0
    for i in range(1, n):
        a = pow(a, 2, m)
        sum_a += a
        if sum_lis[a] != -1: 
            loop_i = i - a_lis_i[a] 
            loop_sum = sum_a - sum_lis[a] 
            loop_cunt = (n - 1 - i)//loop_i 
            sum_a += loop_sum*loop_cunt 
            i += loop_i*loop_cunt
            for j in range(i + 1, n):
                a = pow(a, 2, m)
                sum_a += a             
            print(sum_a)
            sys.exit()
        sum_lis[a] = sum_a
        a_lis_i[a] = i
    print(sum_a)

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, x, m = map(int,input().split())
    sum_lis = [-1] * m 
    a_lis_i = [-1] * m 
    a = x
    sum_a = a
    sum_lis[a] = sum_a
    a_lis_i[a] = 0
    for i in range(1, n):
        a = pow(a, 2, m)
        sum_a += a
        if sum_lis[a] != -1: 
            loop_i = i - a_lis_i[a] 
            loop_sum = sum_a - sum_lis[a] 
            loop_cunt = (n - 1 - i)//loop_i 
            sum_a += loop_sum*loop_cunt 
            i += loop_i*loop_cunt
            for j in range(i + 1, n):
                a = pow(a, 2, m)
                sum_a += a             
            print(sum_a)
            sys.exit()
        sum_lis[a] = sum_a
        a_lis_i[a] = i
    print(sum_a)

if __name__=='__main__':
    main()

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

isUsed = [False] * M
isUsed[X] = True
S = [X]
st = X
while True:
    nx = X**2 % M
    if isUsed[nx]:
        st = nx
        break
    isUsed[nx] = True
    S.append(nx)
    X = nx

idx = S.index(st)
L, R = S[:idx], S[idx:]

ans = sum(L[:N])
N = max(0, N - len(L))

q, r = divmod(N, len(R))
ans += q * sum(R) + sum(R[:r])

print(ans)

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

def cal(x):
    return pow(x,2,M)

memo = set()
lis = []
while X not in memo:
    memo.add(X)
    lis.append(X)
    X = cal(X)
pos = lis.index(X)

if pos >= N:
    print(sum(lis[:N]))
else:
    print(sum(lis[:pos]) + ((N-pos)//(len(memo)-pos)) * sum(lis[pos:]) + sum(lis[pos:(N-pos)%(len(memo)-pos)+pos]))