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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X, M = MAP()
ans = 0
flag = False
L = []
dic = dict()
for i in range(1, N+1):
    if X % M not in L:
        L.append(X % M)
    else:
        flag = True
        tmp = X % M
        l = len(L)
        break
    X = (X % M) ** 2
if flag == True:
    index = L.index(tmp)
    nR = L[:index]
    R = L[index:]
    amari = (N - len(nR)) % len(R)
    ans = sum(nR) + (N - len(nR)) // len(R) * sum(R) + sum(R[:amari])
    print(ans)    
else:
    ans = sum(L)
    print(ans)

Solution (Python):


def main():
    n,x,m = map(int,input().split())
    a = [0] * m
    b = [x]
    ans = x
    i = 1
    while i < n:
        x = (x*x) % m
        if x == 0:
            print(ans)
            exit()

        if a[x] == 0:
            a[x] = i
            b.append(x)
            ans += x
            i += 1
        else :
            q = len(b) - a[x]
            qq = (n-len(b)) // q
            qqq = (n-len(b)) % q
            ans += sum(b[a[x]:]) * qq
            ans += sum(b[a[x]:a[x]+qqq])
            
            print(ans)
            exit()

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

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

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    if (N - 1) <= counter:
        ans = X + sum(mod_list[:N - 1])
    else:
        ans += X + mod_sum
        N -= (counter + 1)
        ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])
print(ans)

Solution (Python):
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
d,m=divmod(n-l[x],T)
print(S*d+s[l.index(l[x]+m)])

Solution (Python):
n, x, m = map(int, input().split())
a = x
s = 0
h = []
h.append(a)
i = 0
fl = 0
while i < n:
    s += a
    a = (a*a) % m
    if a == 0:
      break
    i += 1
    if fl == 0 and a in h:
      fl = 1
      po = h.index(a)
      ss = 0
      for j in range(po):
        ss += h[j]
      s2 = s - ss
      f = (n - po) // (i - po)
      s2 *= f
      s = s2 + ss
      i2 = i - po
      i2 *= f
      i = i2 + po
    else:
      h.append(a)
print(s)

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

def main():
    N, X, M = map(int, input().split())
    pre = set()
    pre.add(X)
    cnt = 1
    while cnt < N:
        X = f(X, M)
        if X in pre: break
        cnt += 1
        pre.add(X)
    if cnt == N:
        return sum(pre)
    ans = sum(pre)
    N -= cnt
    loop = set()
    loop.add(X)
    while cnt < N:
        X = f(X, M)
        if X in loop: break
        loop.add(X)
    
    left = N % len(loop)
    ans += sum(loop) * (N // len(loop))
    for i in range(left):
        ans += X
        X = f(X, M)
    return ans

print(main())

Solution (Python):
N, X, M = map(int, input().split())
A = X
P = set([A])
cnt, cnt2 = -1, -1
S = A
S2 = 0
off = -1
for i in range(N-1):
    A = A**2%M
    if A in P and cnt == -1:
        cnt = i
        off = A
    elif A ==off:
        cnt2 = i
        break
    S += A
    if cnt != -1:
        S2 += A
    P.add(A)
l = max(cnt2-cnt,1)
if cnt2==-1:
    res = S
else:
    res = 0
    for i in range((N-cnt-1)%l):
        res += off
        off = off**2%M
    res += S + ((N-cnt2-1)//l)*S2
print(res)
"""
9 4 7
"""

Solution (Python):
def resolve():
    N, X, M = map(int,input().split())
    A_list = [X]
    preA = X
    A_set = set(A_list)
    for i in range(N-1):
        A = preA**2%M

        if A == 0:
            answer = sum(A_list)
            break
        elif A in A_set:
            finished_count = len(A_list)
            
            same_A_index = A_list.index(A)
            one_loop = A_list[same_A_index:]
            loop_count, part_loop = divmod(N-finished_count, len(one_loop))
            answer = sum(A_list) + sum(one_loop)*loop_count + sum(one_loop[:part_loop])
            break

        A_list.append(A)
        A_set.add(A)
        preA = A
    else:
        answer = sum(A_list)
    print(answer)
resolve()

Solution (Python):

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


import sys


readline = sys.stdin.readline

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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


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

if __name__ == '__main__':
    main()

Solution (Python):

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


import sys


readline = sys.stdin.readline

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M

    x = X
    s = [X]
    u = set()
    while True:
        x *= x
        x %= M
        s.append(x)
        if x in u:
            break
        u.add(x)

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

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

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


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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
N, X, M = map(int, input().split())
A = [X]
visited = set()
visited.add(X)

idx = defaultdict()
idx[X] = 0

iii = -1

for i in range(1, M):
    tmp = (A[-1]**2) % M
    if tmp not in visited:
        A.append(tmp)
        visited.add(tmp)
        idx[tmp] = i
    else:
        iii = idx[tmp]





ans = 0

ans += sum(A[:iii])
N -= iii

l = len(A) - iii

ans += (N // l) * sum(A[iii:])
N -= N // l * l

ans += sum(A[iii:iii + N])

print(ans)
exit()

Solution (Python):
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
print(S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)])

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

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

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

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

Rest=N-len(A)

ans+=Rest//Roop*RoopSum

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

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

def f(x, m):
    return x % m

a = x
a_set = {a}
a_array = [a]
a_index = 0
while(True):
    a = f(a ** 2, m)
    if a in a_set:
        a_index = a_array.index(a)
        break
    a_set.add(a)
    a_array.append(a)


a_iter_array = a_array[a_index:]
div, mod = divmod(n - a_index, len(a_iter_array))
ans = sum(a_array[:a_index]) + sum(a_iter_array) * div + sum(a_iter_array[:mod])
print(ans)

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

ans = []
flag = False
for i in range(n):
    if x in ans:
        v = x
        flag = True
        break
    ans.append(x)
    x = x**2 % m
if flag:
    p = ans.index(v)
    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())
A = X%M
Ans = A
Modset = set()
Modset.add(A)
i = 1
for _ in range(10**6):
    A = pow(A,2,M)
    if A not in Modset:
        Modset.add(A)
        Ans += A
        i += 1
    else:
        break
if 0 in Modset:
    print(Ans)
else:
    S = A
    B = A
    j = 1
    for _ in range(10**6):
        B = pow(B,2,M)
        if A != B:
            S += B
            j += 1
        else:
            break
    rep = (N-i)//j
    Ans += S*rep
    i += j*rep
    if i < N:
        i += 1
        Ans += A
        for _ in range(10**10):
            if i == N:
                break
            else:
                i += 1
                A = pow(A,2,M)
                Ans += A
    print(Ans)

Solution (Python):
n,x,m=map(int,input().split())
l=[-1]*m
s=[0]*m
t=p=0
while l[x]<0:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
if n<l[x]:
  print(s[l.index(n)])
else:
  print(S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)])

Solution (Python):
n,x,m=map(int,input().split())
ans=0
if n<=10**6:
    for i in range(n):
        ans+=x%m
        x*=x
        x%=m
    print(ans)
else:
    lis=[x]
    s={x}
    while 1:
        x*=x
        x%=m
        if x in s:
            num=x
            break
        lis.append(x)
        s.add(x)
    for i in range(len(lis)):
        if lis[i]==num:
            idx=i
    cnt=(n-idx)//(len(lis)-idx)
    idx2=(n-idx)%(len(lis)-idx)
    
    suma=0
    sumb=0
    for i in range(len(lis)):
        if i<idx:
            suma+=lis[i]
        else:
            sumb+=lis[i]
    ans+=suma+sumb*cnt
    for i in range(idx2):
        ans+=lis[idx+i]
    print(ans)

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


cnt=1
now=x
ans=x
jisyo=defaultdict(list)
jisyo[now]=[ans,cnt]
while cnt<n:
    nex=now**2%m
    cnt+=1
    ans+=nex
    now=nex
    if nex in jisyo:
        tmp=jisyo[nex]
        
        ans+=(ans-tmp[0])*((n-cnt)//(cnt-tmp[1]))
        cnt=n-(n-cnt)%(cnt-tmp[1])
        break
    else:
        jisyo[now]=[ans,cnt]
    
for i in range(n-cnt):
    now=now**2%m
    ans+=now
print(ans)

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

s=set()

while True:
    if X==0:
        print(sum(s))
        exit()
    if X in s:
        break
    else:
        s.add(X)
        X=X**2%M
    
loop=set()
while True:
    if X in loop:
        break
    else:
        loop.add(X)
        X=X**2%M

bef_loop=[]
X=_X
while True:
    if  X in loop:
        break
    else:
        bef_loop.append(X)
        X=X**2%M

if N<=len(bef_loop):
    print(sum(bef_loop[:N]))
else:
    ans=sum(bef_loop)
    R=N-len(bef_loop)

    ans+=R//len(loop)*sum(loop)
    r=R%len(loop)

    X=_X
    for _ in range(len(bef_loop)):
        X=X**2%M
    for _ in range(r):
        ans+=X
        X=X**2%M
    print(ans)

Solution (Python):
N,X,M=map(int,input().split())
t=[]
t.append(X)
temp=X
ans=X
for i in range(10**5+100):
    temp=temp**2%M
    if temp in t:
        firstindex=t.index(temp)
        currentindex=len(t)
        firstsum=0
        for i in range(firstindex):
            firstsum+=t[i]
        repeatsum=0
        for i in range(firstindex,currentindex):
            repeatsum+=t[i]
        repetition=(N-firstindex)//(currentindex-firstindex)
        lastrep=        (N-firstindex)%(currentindex-firstindex)
        lastsum=0
        for i in range(firstindex,firstindex+lastrep):
            lastsum+=t[i]
        print(firstsum+repetition*repeatsum+lastsum)
        exit()

    else:
        t.append(temp)

Solution (Python):
n, x, m = map(int, input().split())
g = x * 1
ans = x
arr = []
res = set([])
roop = (0, 0)
k = 0
for i in range(m + 1):
	tmp = x ** 2 % m
	if tmp in res:
		roop = (i, tmp)
		break
	res.add(tmp)
	arr.append(tmp)
	ans += tmp
	x = tmp

for i, y in enumerate(arr):
	if y == roop[1]:
		k = i
		break

ini = sum(arr[:k])
mul = ans - ini - g
t, v = divmod(n - k - 1, roop[0] - k)
print(g + ini + mul * t + sum(arr[k:k + v]))

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

a_i = x
log = [x]
app=[-1]*m
app[x]=0
last = x
for i in range(1,n):
  a_i = (a_i**2)%m
  if app[a_i] > -1:
    last = a_i
    break
  app[a_i] = i
  log.append(a_i)


ans = sum(log[:min(n, app[last])])
if n > app[last]:
  
  ans += sum(log[app[last]:]) * ((n-app[last]) // (len(log) - app[last]))
  
  ans += sum(log[app[last]:app[last] + (n-app[last]) % (len(log) - app[last])])
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
ans = x
if n <= m:
    for i in range(1, n):
        x = (x * x) % m
        ans += x
    print(ans)
    exit()
cnt = [0] * m
loop = []
start = -1
for i in range(4 * m):
    x = (x * x) % m
    if cnt[x] == 1:
        loop.append(x)
        if start == -1:
            start = i
    cnt[x] += 1
for i in range(m):
    if cnt[i] > 0:
        ans +=  i
l = len(loop)
if l > 0 and start != -1:
    ans += sum(loop) * ((n-1-start) // l)
    ans += sum(loop[:(n-1-start)%l])
print(ans)

Solution (Python):
n,x,m=map(int,raw_input().split())
i=0
v=[x]
t={x:0}
p=0 
start=0
while True: 
    i+=1
    y=(x*x)%m 
    if y in t: 
        p+=(i-t[y]) 
        start+=t[y]
        break 
    t[y]=i
    v.append(y) 
    x=y 
ans=0 

if n<(len(v)): 
    for i in range(n): 
        ans+=v[i] 
    print ans 
else: 
    for i in range(start): 
        ans+=v[i] 
    n-=(start) 
    g=n%p+start
    l=n/p 
    for i in range(start,len(v)): 
        ans+=(l*v[i]) 
        if i<g: 
            ans+=v[i] 
    print ans

Solution (Python):



def solve(*args: str) -> str:
    n, x, m = map(int, args[0].split())

    a = x
    ret = 0
    D = [-1]*(m+1)
    for i in range(n):
        if 0 <= D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
def main():
    n,x,m = map(int,input().split())
    amari = [0 for i in range(m)]
    x = x%m
    amari[x] = 1
    loop = [x]
    while True:
        x = x**2 % m
        if amari[x]==0:
            loop.append(x)
            amari[x] = 1
        elif x==0:
            loop.append(0)
            if len(loop)>n:
                print(sum(loop))
            else:
                print(sum(loop[0:n]))
            return
        else:
            st = loop[0:loop.index(x)]
            loop = loop[loop.index(x):]
            break
    ans = 0
    if len(st)>=n:
        ans = sum(st[0:n])
        print(ans)
        return
    ans = sum(st)
    l = (n-len(st))//len(loop)
    ans += l*sum(loop)
    for i in range(n-len(st)-l*len(loop)):
        ans += loop[i]
    print(ans)

if __name__ == "__main__":
    main()

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

if x == 0:
    ans = 0
else:
    ans = x % m
dicNum = dict()
dicSum = dict()
dicNum[x] = 1
dicSum[1] = x
dicSum[0] = 0

for i in range(2,n+1):
    b = x
    x = x**2 % m
    if x in dicNum.keys():
        t = i - dicNum[x]
        zan = n - i + 1
        k = zan // t
        ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
        if zan% t != 0:
            zan = zan % t
            ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
        break
    else:
        ans += x
        dicSum[i] = ans
        dicNum[x] = i

print(ans)

Solution (Python):
N, X, M = map(int, input().split())
d = dict()
L = []
for i in range(M+1):
    if X not in d:
        d[X] = i
        L.append(X)
    else:
        j = d[X]
        k = i
        break
    X = X*X%M
s=k-j
kk, zz = divmod((N-j), s)
print(sum(L[:j])+sum(L[j:])*kk+sum(L[j:j+zz]))

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

existence = [0] * M
a = []
A = X
for i in range(N):
    if existence[A] != 0:
        break
    existence[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):
from collections import defaultdict
N,X,M=map(int,input().split())
cnt=0
index=[X]
d=defaultdict(int)
i=1
while True:
	X=pow(X,2,M)
	if d[X]!=0:
		z=d[X]
		break
	d[X]=i
	i+=1
	index.append(X)
target=len(index)-z
total=0
for i in range(z,len(index)):
	total+=index[i]
for i in range(z):
	cnt+=index[i]
total2=0
for i in range(z,z+(N-z)%target):
	total2+=index[i]
cnt+=total*((N-z)//target)+total2
print(cnt)

Solution (Python):
import sys

def main():
    N, X, M = map(int, sys.stdin.readline().rstrip().split())

    S = [0] * M  
    C = [0] * M  

    _sum = 0
    cycle_sum = 0
    cycle_count = 0
    for i in range(1, N+1):
        _sum += X
        if S[X] == 0:
            C[X] = _sum
            S[X] = i
        else:
            cycle_sum = _sum - C[X]
            cycle_length = i - S[X]
            break
        X = X**2 % M
    else:
        print(_sum)
        return        

    
    first_sum = C[X]
    cycle_n = (N - S[X]) // cycle_length
    _sum = first_sum + cycle_n * cycle_sum
    rest = N - (S[X] + cycle_n * cycle_length)
    
    

    for i in range(rest):
        X = X**2 % M
        _sum += X
    
    print(_sum)


main()

Solution (Python):
n, x, m = map(int, input().split())
check = [False] * (10**5 + 10)
check_list = [x]
a = x

for i in range(n):
    a = (a * a) % m
    if check[a]:
        break
    check[a] = True
    check_list.append(a)


index = check_list.index(a)

roop_bef = check_list[0:index]

roop = check_list[index:]



roop_num = (n - len(roop_bef)) // len(roop)
roop_after_num = (n - len(roop_bef)) % len(roop)


ans = sum(roop_bef) + sum(roop) * roop_num + sum(roop[:roop_after_num])

print(ans)

Solution (Python):

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

    _l = tuple([i**2 % M for i in range(M)])

    _a = X
    ans_l = [0] * M
    ans_l[0] = _a
    seq = [_a]
    s = g = 0
    for i in range(1, M):
        _a = _l[_a]
        ans_l[i] = _a + ans_l[i-1]
        if _a in seq:
            s = seq.index(_a)
            g = len(seq)-1
            break
        seq.append(_a)
    _tmp = N - s
    loop = _tmp // (g - s + 1)
    zan = _tmp % (g - s + 1)
    ans = ans_l[s-1] + (ans_l[g] - ans_l[s-1]) * loop + \
        (ans_l[s+zan-1] - ans_l[s-1])
    print(ans)


solve()

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

h = [0 for i in range(M + 1)]
r = [0 for i in range(M + 1)]

A = X
result = A
h[A] = 1
i = 2
f = True
while i < N + 1:
    r[A] = result

    A = (A * A) % M
    if A == 0:
        break
    result = result + A
    if f and h[A] > 0:
        f = False
        d = i - h[A]
        result = (result - r[A]) * int((N - i) / d) + result
        i = N - (N - i) % d
    h[A] = i
    i = i + 1
print(result)

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


amari = [0] * (m + 1)
for i in range(m + 1):
    y = pow(i, 2, m)
    amari[y] += 1 

visited = [0] * (m + 1)
now = x
loop = 1
while True:
    y = pow(now, 2, m)
    if visited[y] == 1:
        last = y
        break
    visited[y] += 1
    now = pow(now, 2, m)
    loop += 1





res = x


cnt_init = 1
now = x
while True:
    y = pow(now, 2, m)
    
    if y == last:
        break
    res += pow(now, 2, m)
    now = pow(now, 2, m)
    cnt_init += 1


loop = loop - cnt_init




cnt = (n - cnt_init) // loop
tmp = last 
now = last
while True:
    y = pow(now, 2, m)
    if y == last:
        break
    tmp += pow(now, 2, m)
    
    now = pow(now, 2, m)

res += tmp * cnt


nokori = (n - cnt_init) % loop

if nokori == 0:
    print(res)
    exit()

now = last
res += last
for _ in range(nokori-1):
    res += pow(now, 2, m)
    now = pow(now, 2, m)

print(res)

Solution (Python):
def main(N, X, M):
    kurikaesi = []
    shoki = [X]
    st_shoki = {X}

    now = X
    for n in range(1, N):
        next = (now ** 2) % M
        if next in st_shoki:
            i = shoki.index(next)
            kurikaesi = shoki[i:]
            shoki = shoki[:i]
            break
        else:
            shoki.append(next)
            st_shoki.add(next)
            now = next
    else:
        print(sum(shoki))
        exit()

    shou = (N - len(shoki)) // len(kurikaesi)
    amari = (N - len(shoki)) % len(kurikaesi)

    print(sum(shoki) + sum(kurikaesi) * shou + sum(kurikaesi[:amari]))
    
if __name__ == '__main__':
    N, X, M = list(map(int, input().split()))
    main(N, X, M)

Solution (Python):
from collections import defaultdict
n, x, m = map(int, input().split())
now = x
ans = x
d = defaultdict(int)
repeat = []

for i in range(n):
    now = (now**2)%m
    d[now] += 1
    repeat.append(now)
    if d[now] > 1:
        break

for g in range(len(repeat)):
    if repeat[g] == now:
        break
    else:
        ans += repeat[g]
        n -= 1

repeat = repeat[g:-1] 
n -= 1
if len(repeat) != 0:
    ans += sum(repeat)*(n//len(repeat)) + sum(repeat[:n%len(repeat)])
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
check = [False] * (10**5 + 10)
check_list = [x]
a = x
check[a] = True

for i in range(n):
    
    a = (a * a) % m
    if check[a]:
        break
    check[a] = True
    check_list.append(a)



index = check_list.index(a)

roop_bef = check_list[0:index]
roop = check_list[index:]



roop_bef_num = len(roop_bef)
roop_num = (n - len(roop_bef)) // len(roop)
roop_after_num = (n - len(roop_bef)) % len(roop)

ans = sum(roop_bef) + sum(roop) * roop_num + sum(roop[:roop_after_num])



print(ans)

Solution (Python):
def main():
    n,x,m=map(int,input().split())
    A=[]
    s=set()
    while True:
        A.append(x)
        s.add(x)
        x**=2
        x%=m
        if x==0:
            A.append(0)
            break
        if x in s:
            break
    
    if n<=len(A):
        return sum(A[:n])
    if A[-1]==0:
        return sum(A)
    for idx,a in enumerate(A):
        if a==x:
            break
    l=len(A)-idx
    cycles=(n-idx)//l
    remain=(n-idx)%l
    
    s=sum(A[idx:])
    ans=sum(A[:idx])
    ans+=s*cycles
    ans+=sum(A[idx:idx+remain])
    return ans
    
if __name__=='__main__':
    print(main())

Solution (Python):
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, x, m = MI()
    a = x
    flag = [False]*(m+1)
    t = 0
    s = []
    idx = 0
    for _ in range(m+1):
        if flag[a]:
            idx = s.index(a)
            break
        flag[a] = True
        s.append(a)
        t += a
        a = (a*a) % m
        if a == 0:
            print(t)
            sys.exit()
    ans = sum(s[0:idx])
    ans += sum(s[idx:])*((n-idx)//(len(s)-idx))
    ans += sum(s[idx:idx+(n-idx)%(len(s)-idx)])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, sX, mod = mapint()

X = sX
s = set()
s.add(X)
s_loop = set()
ans = X
loop = 0
loops = []
i = -1
for i in range(min(10**5*2+10, N-1)):
    X = pow(X, 2, mod)
    if X in s:
        if X in s_loop:
            loops.append(X)
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
if rest:
    ans += (rest//len(s_loop))*loop
    amari = rest%len(s_loop)+1
    for i in range(amari):
        ans += loops[i]
    print(ans)
else:
    print(ans)

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

ans = []
flag = False
for i in range(n):
    if x in ans:
        v = x
        flag = True
        break
    ans.append(x)
    x = x**2 % m
if flag:
    p = ans.index(v)
    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())
def am(a, b):
    return (a * a) % b
l = [x]
u = []
now = x
for i in range(n):
    s = am(now, m)
    if(s in l):
        break
    l.append(s)
    now = s
c = l.index(s)
k = 0
if(0 in l):
    print(sum(l))
else:
    for i in range(c):
        u.append(l.pop(0))
    a = (n-len(u)) // len(l)
    b = (n-len(u)) % len(l)
    print(sum(u) + a * sum(l) + sum(l[:b]))

Solution (Python):
n, x, m = map(int, input().split())
a = [x]
if n == 1:
    print(x)
    exit()
for i in range(n-1):
    ad = (a[-1]**2) % m
    if ad in a:
        roop_s = a.index(ad)
        roop_e = len(a)
        break
    else:
        a.append(ad)
    if i == n-2:
        print(sum(a))
        exit()
roop_t = (n-roop_s) // (roop_e - roop_s)
left = n - roop_t*(roop_e - roop_s) - roop_s
ans = sum(a[:roop_s]) + roop_t*sum(a[roop_s : roop_e]) + sum(a[roop_s:roop_s+left])
print(ans)

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

List = [X]

for i in range(N-1):
    X = X**2 % M
    if X in List:
        
        num = i + 1
        
        key = List.index(X)
        break
    List.append(X)

ans = sum(List)
if len(List) == N:
    print(ans)

else:
    loop = (N - len(List)) // (num - key)
    add = (N - len(List)) % (num - key)

    ans += (N - len(List)) // (num - key) * sum(List[key:num])
    ans += sum(List[key:key+((N - len(List)) % (num - key))])

    print(ans)

Solution (Python):
def resolve():
    n, x, m = map(int, input().split())
    a = [None] * m
    s = [x]
    a[x] = 0
    ans = x
    for i in range(1, n):
        x = pow(x, 2, m)
        if a[x] is None:
            ans += x
            a[x] = i
            s.append(ans)
        else:
            past = a[x]
            d = i - past
            ans += x
            s.append(ans)
            diff = s[i] - s[past]
            ans += ((n - i - 1) // d) * diff
            ans += s[past + ((n - i - 1) % d)] - s[past]
            break
    print(ans)


if __name__ == '__main__':
    resolve()

Solution (Python):
n,x,m=map(int,input().split())
p=[0]*(m+1)
a=x
t=0
s=0
for i in range(2*m):
    if p[a]==1:
        p[a]=2
        break
    else:
        p[a]=1
        a=a**2%m
a=x
S=0
for i in range(2*m):
    if p[a]==1:
        s+=1
        S+=a
        a=a**2%m
    else:
        s+=1
        S+=a
        break
T=0
A=0
for i in range(2*m):
    a=a**2%m
    t+=1
    T+=a
    if p[a]==2:
        A=a
        break
a = x
if n <= s:
    ans=0
    for i in range(n):
        ans+=a
        a=a**2%m
    print(ans)
else:
    ans=S
    a=A
    n-=s
    ans+=(n//t)*T
    n=n%t
    for i in range(n):
        a=a**2%m
        ans+=a
    print(ans)

Solution (Python):
n, x, mod = map(int, input().split())
lst = [0, x]
num_set = set([x])
num_lst = [0, x]
flag = False

for i in range(mod - 1):
  x = (x * x) % mod
  s = x + lst[-1]
  if x == 0:
    lst.append(s)
    break
  if x in num_set:
    flag = True
    break
  lst.append(s)
  num_set.add(x)
  num_lst.append(x)
  if i + 2 == n:
    break


if flag:
  for i, ele in enumerate(num_lst):
    if x == ele:
      loop_s = i
      break

l = len(lst)
if lst[l - 1] == lst[l - 2]:
  print(lst[l - 1])
else:
  if not flag:
    print(lst[-1])
  else:
    loop = len(lst) - loop_s
    n -= loop_s - 1
    c = n // loop
    r = n % loop
    ans = lst[l - 1] + (c - 1) * (lst[l - 1] - lst[loop_s - 1]) + lst[loop_s + r - 1] - lst[loop_s - 1]
    print(ans)

Solution (Python):
N, X, M = map(int,input().split())
if N==1:
  print(X)
  exit()
a = [X]
sa = set([X])
for i in range(1,N):
  X = (X**2)%M
  if X in sa:
    break
  else:
    a.append(X)
    sa.add(X)

if i==N-1:
  print(sum(a))
  exit()
start = a.index(X)
ans = sum(a[:start])
base = sum(a[start:])
rep = i-start
sets = (N-start)//rep
more = (N-start)%rep
ans += base*sets + sum(a[start:start+more])
print(ans)