Problem:
 Score : 500 points    Problem Statement Let us denote by f(x, m) the remainder of the Euclidean division of x by m .  Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M) .
Find \displaystyle{\sum_{i=1}^N A_i} .      Constraints  1 \leq N \leq 10^{10}  0 \leq X < M \leq 10^5  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  X  M       Output Print \displaystyle{\sum_{i=1}^N A_i} .        Sample Input 1 6 2 1001      Sample Output 1 1369  The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369 .       Sample Input 2 1000 2 16      Sample Output 2 6  The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6 .       Sample Input 3 10000000000 10 99959      Sample Output 3 492443256176507

Solution (Python):



def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n,x,m = mp()
u = [0]*m
kaime = [0]*m
a = [x%m]
u[x%m] += 1
kaime[x%m] = 1
t = 0
for i in range(2, n+1):
    x = x**2 % m
    if u[x] == 1:
        t = x
        break
    else:
        u[x] += 1
        a.append(x)
        kaime[x] = i
if n == len(a):
    print(sum(a))
else:
    loop_array = a[kaime[t]-1:]
    loop = (n-kaime[t]+1)//len(loop_array)
    amari = (n-kaime[t]+1)%len(loop_array)
    print(sum(a[:kaime[t]-1])+ loop*sum(loop_array)+sum(loop_array[:amari]))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

    if N == 1:
        print(X)
        return

    A = X
    steps = [0] * M
    sms = [0] * M
    steps[A] = 1
    sms[A] = A
    sm = A
    ans = A
    rest = 0
    for i in range(2, N+1):
        A = (A*A) % M
        sm += A
        ans += A
        if steps[A] != 0:
            P = i - steps[A]
            v = sm - sms[A]
            rest = N - i
            ans += v * (rest//P)
            rest %= P
            break
        steps[A] = i
        sms[A] = sm

    for i in range(rest):
        A = (A*A) % M
        ans += A

    print(ans)


solve()

Solution (Python):


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


s = {X}
l = [X]
i = 0
while True:
    a = l[-1]**2 % M
    if a in s:
        i = l.index(a)
        break
    else:
        s.add(a)
        l.append(a)

loop_length = len(l) - i
loop_cnt = (N - i) // loop_length
loop_res = (N - i) % loop_length
ans = sum(l[:i]) + loop_cnt * sum(l[i:]) + sum(l[i: i + loop_res])


print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,X,M = LI()

    d = [0] * (M+1)
    t = [0] * (M+1)

    aa = X
    i = 0
    s = 0
    while d[aa] == 0:
        i += 1
        d[aa] = i
        s += aa
        t[i] = s
        aa = (aa * aa) % M

    ans = 0
    if N <= i:
        ans = t[N]

    else:
        m = i - d[aa] + 1
        r = d[aa] - 1 + ((N - (d[aa]-1)) % m)

        ans = t[r]
        ans += (t[i] - t[d[aa]-1]) * ((N-(d[aa]-1)) // m)


    print(ans)


if __name__ == '__main__':
    main()

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

cnt = 0
s = set()
L = []
for i in range(n):
    if i == 0:
        x = x%m
    else:
        x = x**2%m
    
    if x == 0:
        break
    else:
        cnt += x
        if x not in s:
            s.add(x)
            L.append(x)
        else:
            l = L.index(x)
            restN = n - (i+1)
            restL = len(L)-l
            a = restN%restL
            
            loopcnt = 0
            restcnt = 0
            for j in range(restL):
                loopcnt += L[l+j]
                
                if j > 0 and j <= a:
                    restcnt += L[l+j]
            
            cnt += loopcnt*(restN//restL) + restcnt
            break
                

print(cnt)

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

li = [x]
a = x
q = 0
flag = False
for i in range(m):
    k = (a**2)%m
    if k == 0:
        p = i+1
        flag = True
        break
    if k in li:
        p = i+1
        q = li.index(k)
        break
    li.append(k)
    a = k
    
K = sum(li)
li2 = li[q:]
K2 = sum(li2)

if not flag:
    ans = K + ((n-p)//(p-q))*K2 + sum(li2[:((n-p)%(p-q))])
else:
    ans = sum(li[:n])
print(ans)

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

check = [0]*(M+1)
SUM1 = 0
cnt1 = 0
temp = X
check3=0
for i in range(N):

    if check[temp]==0:
        check[temp]+=1
    else:
        check3 = 1
        break
        
    SUM1 += temp
    cnt1 += 1
    temp = temp ** 2
    temp %= M


check2 = [0]*(M+1)
SUM2 = 0
cnt2 = 0
if check3==1:
    
    for i in range(N):


        if check2[temp]==0:
            check2[temp]+=1
        else:
            break
        SUM2 += temp        
        cnt2 += 1
        temp = temp ** 2
        temp %= M



SUM3 = 0

Y = (N-cnt1)%max(cnt2,1)

for i in range(Y):
    
    SUM3 += temp

    temp = temp ** 2
    temp %= M
    
if check[0]==1:
    SUM3=0
    N = cnt1+cnt2

print(SUM1+SUM2*(((N-cnt1)//max(cnt2,1)))+SUM3)

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

def main():
    n, x, m = map(int, input().split())
    if x == 0:
        print(0)
        return
    if x == 1:
        print(n)
        return

    d = {}
    d_idx = {}
    d_unit = {}
    idx = 0
    pow_x = x
    unit = 0
    while idx < n and pow_x not in d:
        d[pow_x] = idx
        d_idx[idx] = pow_x
        unit += pow_x
        d_unit[idx] = unit

        pow_x *= pow_x
        pow_x %= m
        idx += 1
    

    if idx == n:
        print(unit)
        return
    pre_idx = d[pow_x]
    pre_unit = d_unit[pre_idx] - d_idx[pre_idx]
    iter_unit = unit - pre_unit
    ans = pre_unit + iter_unit * ((n - pre_idx) // (idx - pre_idx))
    for i in range((n - pre_idx) % (idx - pre_idx)):
        ans += d_idx[i + pre_idx]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, x, m = map(int, input().split())
A = [x]
checkA = {x}
ans = x

for i in range(1,n):
    buf = A[i-1]*A[i-1] % m
    if buf in checkA:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        ans += sum(A[idx:idx+last])
        break
    else:
        A.append(buf)
        checkA.add(buf)
        ans += buf

print(ans)

Solution (Python):
N,X,M = map(int,input().split())
from collections import deque
ans = 0
flag = [0] * (M+1)
dic = dict()
q = deque()
for i in range(N):
  if not(flag[X]):
    flag[X] = 1
    dic[X] = i
    q.append(X)
    ans += X
    X = pow(X,2,M)
  else:
    q = list(q)
    loop = q[dic[X]:]
    loop_sum = sum(loop)
    loop_l = len(loop)
    length = N-i - ((N-i)//loop_l * loop_l)
    ans += loop_sum * ((N-i)//loop_l)
    ans += sum(loop[:length])
    break
print(ans)

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


A = []
B = {}
a = X
i_repeat = 0
for i in range(N):
    if a in B.keys():
        i_repeat = B[a]
        break
    A.append(a)
    B.update({ a : i })
    a = a**2 % M
    i += 1

repeat_size = i - i_repeat
repeat_interval = N - i_repeat

num_repeats = repeat_interval // repeat_size
num_red = repeat_interval % repeat_size


res = sum(A[:i_repeat])
res += sum(A[i_repeat:i]) * num_repeats
res += sum(A[i_repeat:i_repeat+num_red])

print(res)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


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



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

    L = [-1]*M
    route = []
    ans = 0
    a = 0
    l = 0
    r = N
    for i in range(N):
        if i == 0:
            a = X
        else:
            a = func(a**2, M)
        if L[a] >= 0:
            if N:
                pass
            l = L[a]
            r = i
            break
        else:
            L[a] = i
            route.append(a)
    
    ans += sum(route[:l])
    k = (N - l) // (r - l)
    m = (N - l) % (r - l)
    ans += sum(route[l:]) * k
    ans += sum(route[l:l+m])
    
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
arr=[]
from collections import Counter
c=Counter([])
inp=list(map(int,input().split()))
n=inp[0]
x=inp[1]
m=inp[2]
sumi=x
c=Counter([])
c[x]=1
a=(x**2)%m
arr=[x]
z=2
flag=0
sz=1
while 1:
    if c[a]!=0 :
        flag=1
        break
    arr.append(a)
    sz+=1
    c[a]+=1
    a=(a**2%m)
    if sz==n:
        break
if flag==0:
    print (sum(arr))
else:
    ind=arr.index(a)
    s=sum(arr[:ind])
    s1=sum(arr[ind:])
    s+=s1
    l=len(arr)-ind
    n-=len(arr)
    x=n//l
    s+=s1*x
    x=n%l
    s+=sum(arr[ind:ind+x])
    print (s)

Solution (Python):
import sys
N, X, M = map(int, input().split())
ans = X
is_visited = [-1 for i in range(10**5+1)]
X_list = []
for i in range(0, N-1):
    X = (X ** 2) % M
    if is_visited[X] >= 0:
        remN = N-i-1
        ans += (remN // (i-is_visited[X])) * sum(X_list[is_visited[X]:])
        for j in range(is_visited[X], is_visited[X]+remN % (i-is_visited[X])):
            ans += X_list[j]
        print(ans)
        sys.exit()
    is_visited[X] = i
    X_list += [X]
    ans += X
    if X == 0:
        print(ans)
        sys.exit()
print(ans)

Solution (Python):
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy


n, x, m = map(int, sys.stdin.readline().split())




li = [0]*(m+1)
a = []
p = x
a.append(x)
li[x] = 1
for i in range(m):
    p *= p
    p %= m
    if li[p] == 0:
        li[p] = 1
        a.append(p)
    else:
        d = p
        break

b = a.index(d)
bef = sum(a[:b])
afe = sum(a[b:])
loop = len(a) - b
c = n - b

f = c // loop
g = c % loop
rest = sum(a[b:b + g])

ans = bef + afe * f + rest
print(ans)

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

f = [-1]*m
ans = x
n -= 1
while n > 0:
    if f[x] == -1:
        f[x] = pow(x, 2, m)
        ans += f[x]
        x = f[x]
        n -= 1
    else:
        break
loop = [x]
ans -= x
for i in range(n):
    tmp = pow(loop[-1], 2, m)
    if tmp == loop[0]:
        break
    loop.append(tmp)
loopsum = sum(loop)
ans += (n+1) // len(loop) * loopsum + sum(loop[0:((n+1) % len(loop))])
print(ans)

Solution (Python):
def resolve():
    n,x,m = map(int,input().split())
    ans = x
    y = [x]
    for i in range(n-1):
        x = (x**2)%m
        if x not in y:
            y.append(x)
        else:
            break
    b = y.index(x)
    N = len(y[b:])
    c = sum(y[b:])
    ans = sum(y[:b]) + c*((n-b)//N)+sum(y[b:b+(n-b)%N])
    print(ans)
resolve()

Solution (Python):
def main():
    N,X,M = map(int,input().split())
    A = X
    ans = A
    LIST = [A]
    C = 0
    flag = False
    for n in range(N-1):
        A = (A**2)%M
        if A in LIST:
            ind = LIST.index(A)
            C = sum(LIST[:ind])
            LIST = LIST[ind:]
            flag = True
            break
        else:
            LIST.append(A)
        ans += A
    else:
        print(ans)
        
    if flag:
        ANS = [0]
        S = 0
        for L in LIST:
            S += L
            ANS.append(S)
            
        a = (N - ind) // len(LIST)
        b = (N - ind) % len(LIST)
        ans = sum(LIST)*a + ANS[b] + C
        
        print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):


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

A=[0]*10**5
A[0]=X
D=dict()

s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in D:
        s=A.index(a)
        break
    else:
        
        A[i]=a
        D[a]=0

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

    ans=0
    l=len(A)-s
    
    ans+=Z[s]
    
    S=Z[len(A)]-Z[s]
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    
    ans+=Z[s+K]-Z[s]


print(ans)

Solution (Python):








def solve(N, X, M):
    mods = [-1 for i in range(M)]
    number = 1
    mods[X] = number
    An = X ** 2 % M
    while mods[An] == -1:
        number += 1
        mods[An] = number
        
        An = An ** 2 % M
    
    loop_num = max(mods) - (mods[An] - 1)
    tag = (N - (mods[An] - 1)) % loop_num
    ans = 0
    for i in range(M):
        
        
        
        if mods[i] == -1:
            continue
        elif mods[i] < mods[An]:
            ans += i
        else:
            x = N - (mods[An] - 1)
            if tag != 0 and mods[i] - mods[An] < tag:
                ans += i * (x // loop_num + 1) if x >= 0 else 0
            else:
                ans += i * (x // loop_num) if x >= 0 else 0
    print(ans)



if __name__ == '__main__':
    
    
    N, X, M = map(int, input().split())
    
    
    
    solve(N, X, M)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, X, M = [int(x) for x in input().split()]

    x = {}

    ruiseki = [0] * (M + 1)

    cnt = 1
    ans = X
    c = X
    ruiseki[1] = ans
    while cnt < N:
        if c == 0:
            print(ans)
            return
        next = c ** 2 % M
        if next in x.keys():
            y = x[next]
            
            
            if N == cnt:
                print(ans + next)
                return
            loop = ruiseki[cnt] - ruiseki[y - 1]
            loopcnt = cnt - y + 1
            ans += ((N - cnt) // loopcnt) * loop
            
            amari = (N - cnt) % loopcnt
            
            if amari != 0:
                ans += ruiseki[y - 1 + amari] - ruiseki[y - 1]
                
            break

        ans += next
        cnt += 1
        ruiseki[cnt] = next
        ruiseki[cnt] += ruiseki[cnt - 1]
        c = next
        x[next] = cnt

    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0
start = X % M
An = X % M
rList = []
repeat = 1
repeatStart = None
while True:
    ans += An
    rList.append(An)
    An = An**2 % M
    repeat += 1
    if An in rList:
        repeatStart = An
        break


repStartIndex = rList.index(repeatStart)

extraPart = rList[0:repStartIndex]
repPart = rList[repStartIndex:]

extraLen = len(extraPart)
repLen = len(repPart)

ans += (((N - extraLen) // repLen) - 1)* sum(repPart)


if (N - extraLen) % repLen > 0:
    rest = (N-extraLen) % repLen
    for i in range(rest):
        ans += repPart[i]
print(ans)

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

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


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

S = 0
A = X
ls = []
for n in range(1, N + 1):
  if exist[A] == 0:
    exist[A] = n
    ls.append(A)
  else:
    term = n - exist[A]
    loop = ls[-term:]
    res = N - n + 1
    S += (res // term) * sum(loop) + sum(loop[:res % term])
    break
  S += A
  A = f(A**2, M)

print(S)

Solution (Python):
import sys

def solve():
      input = sys.stdin.readline
      N, X, M = map(int, input().split())
      D = [False] * M
      roopStart = -1
      now = X
      for i in range(M+1): 
            ne = now * now % M
            if D[ne]:
                  roopStart = ne
                  break
            else: 
                  D[ne] = True
                  now = ne
      
      roopL, roopS = 1, 0
      now = roopStart
      for i in range(M+1):
            ne = now * now % M
            roopS += now
            if ne == roopStart: break
            else: 
                  roopL += 1
                  now = ne

      
      ans = 0
      initialL = 0
      now = X
      for i in range(M+1):
            if i == N: break
            if now != roopStart:
                  ans += now
                  initialL += 1
                  now = now * now % M
            else: break
      if initialL <= N:
            N -= initialL
            roopTimes = N // roopL
            roopRem = N % roopL
            ans += (roopTimes * roopS) 
            now = roopStart
            for j in range(roopRem):
                  ans += now
                  now = now * now % M
            
      print(ans)
      return 0

if __name__ == "__main__":
      solve()

Solution (Python):
n, x, m = map(int, input().split())
mod = [-1 for i in range(m)]
sum = [-1 for i in range(m)]
c = [-1 for i in range(m)]

count = 0
a = x
a_p = -1
i = 1
for i in range(1, n+1):
  
  if(mod[a] != -1):
    loop_c = c[a_p] - c[a] + 1
    loop_sum = sum[a_p] - sum[a] + a
    
    bai = (n - c[a_p])//loop_c
    nokori = (n - c[a_p])%loop_c
    
    ans = sum[a_p] + bai*loop_sum
    for j in range(nokori+1):
      ans += a
      a = mod[a]
    print(ans)
    exit()
  
  i += 1
  count += a
  sum[a] = count
  c[a] = i
  
  
    
  a_p = a
  mod[a] = (a*a)%m
  a = mod[a]
  
  
print(count)

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

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

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

A = [X]
for i in range(N-1):
    v = f(A[-1] ** 2, M)
    A.append(v)
    if P[v] != -1:
        break
    P[v] = i

v = f(A[-1] ** 2, M)
idx = P[v]

S = sum(A[idx+1:])
q, r = divmod(N - len(A), len(A) - idx - 1)

ans = sum(A) + q * S + sum(A[idx+1:idx+1+r])
print(ans)

Solution (Python):
def main():
    N, X, M = map(int, input().split())
    ans = X
    pre = X
    cand = [X]
    cnt = 1
    for i in range(N-1):
        now = pre ** 2 % M
        if now in cand:
            cnt += 1
            index = cand.index(now)
            loop = cand[index:]
            L = len(loop)
            amari = (N - cnt + 1) % L
            syou = (N - cnt + 1) // L
            ans += syou * sum(loop)
            ans += sum(loop[:amari])
            break
        else:
            ans += now
            pre = now
            cand.append(now)
            cnt += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, X, M = map(int, input().split())
a = [0 for i in range(M+1)]
b = [X]
a[X-1] = 1

for i in range(min(N-1, M)):
  X = X**2%M
  a[X-1] += 1
  b.append(X)
  if a[X-1] > 1:
    break

if len(b) == N:
  print(sum(b))

else:
  ls = b.index(b[-1])
  bloop = b[ls:-1]
  ans = 0
  if ls > 0:
    for i in range(ls):
      ans += b[i]
  loop = (N-ls)//len(bloop)
  ans += sum(bloop) * loop
  if (N-ls)%len(bloop) != 0:
    for i in range((N-ls)%len(bloop)):
      ans += bloop[i]
  print(ans)

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

    appear = set([X])
    seq = [X]
    while True:
        seq.append(seq[-1]**2 % M)
        if seq[-1] in appear:
            break
        appear.add(seq[-1])
    loop_length = len(seq) - seq.index(seq[-1]) - 1
    seq.pop()
    first, loop = seq[:-loop_length], seq[-loop_length:]
    loop_count, reminder = divmod(N - len(first), loop_length)
    ans = sum(first) + sum(loop) * loop_count
    for i in range(reminder):
        ans += loop[i % reminder]
    return ans

print(e_sequence_sum())

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

check = set()
hazimari = -1
owari = 0
y = x

check.add(x)
for i in range(n-1):
    owari = y
    y = y**2 % m
    if y in check:
        hazimari = y
        break
    check.add(y)

if hazimari == -1:
    print(sum(check))
    exit()

ans = 0
count = 0
lp = []
y = x
for i in range(n-1):
    ans += y
    y = y**2 % m
    count = i+1
    if y == hazimari:
        lp.append(y)
        for j in range(n):
            y = y**2 % m
            lp.append(y)
            if y == owari:
                break
    else:
        continue
    break

ans += (n-count)//len(lp) * sum(lp)
ans += sum(lp[:(n-count)%len(lp)])
print(ans)

Solution (Python):
n,x,m = map(int,input().split())
ans = x
b = x
box = [x]
c= 0
for i in range(1,n):
    b= (b**2)%m
    if b == 0:
        print(ans)
        exit() 
    if b in box:
        c = box.index(b)
        break
    ans += b
    box.append(b)




print(sum(box[:c])+sum(box[c:])*((n-c)//len(box[c:])) + sum(box[c:c+(n-c)%len(box[c:])]))

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

mod = [x]
app = {}
cnt = 1
app[x] = cnt
i = x*x
i %= m
cnt += 1
while not i in app:
  mod.append(i)
  app[i] = cnt
  i *= i
  i %= m
  cnt += 1













if n <= len(mod):
  ans = sum(mod[:n])
else:
  ans = sum(mod)
  if mod[-1] != 0:
    
    n -= len(mod)
    mod = mod[app[i]-1:]
    
    num = n // len(mod)
    ans += sum(mod) * num + sum(mod[:n % len(mod)])

print(ans)

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

Visited = [0]*(M+1)
latestvisit = [0]*(M+1)
count = 0
latest = 0
proper = 0
        
for i in range (0, N):
	if Visited[X] > 0:
		latest = X
		latestvisit[X] = i
		proper = 1
		break
	latestvisit[X] = i
	Visited[X]+= 1
	X = (X**2)%M

for j in range (0, M+1):
	count+=(j*Visited[j])

if proper == 0:
	print(count)
	exit()
    
P = sum(Visited)
A = latestvisit[X]
B = latestvisit[(X**2)%M]
slouch = 0

for i in range (0, M):
	if latestvisit[i] >=B and latestvisit[i] <= A:
		slouch+=i

count+=((N-P)//(A-B+1))*slouch


for i in range (0, (N-P)%(A-B+1)):
	count+=X
	X = (X**2)%M

print(count)

Solution (Python):
N,X,M=map(int,input().split())
l=[-1]*M
a=0
t=X
l[X]=0
if t**2%M==t:
    print(N*t)
    exit()
for i in range(1,M+1):
    t=t**2%M
    if l[t]==-1:
        l[t]=i
    else:
        s,g=l[t],i
        break
if N<=s+1:
    t=X
    a=X
    for i in range(N-1):
        t=t**2%M
        a+=t
    print(a)
else:
    t=X
    a=0
    if s!=0:
        a=X
    for i in range(s-1):
        t=t**2%M
        a+=t
    t2=t
    c=0
    for i in range(g-s):
        t=t**2%M
        c+=t
    if s==0:
        for i in range(N%(g-s)):
            a+=t2
            t2=t2**2%M
    else:
        for i in range((N-s)%(g-s)):
            t2=t2**2%M
            a+=t2
    a+=c*((N-s)//(g-s))
    print(a)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,x,m = LI()
    f = [0]*m
    a = x
    ans = 0
    for i in range(1,n+1):
        ans += a
        if f[a]:
            break
        f[a] = 1
        a = pow(a,2,m)
    s = []
    f = [0]*m
    for j in range(i+1,n+1):
        if f[a]:
            break
        f[a] = 1
        a = pow(a,2,m)
        s.append(a)
    r = n-i
    if s:
        ans += sum(s)*(r//len(s))+sum(s[:r%len(s)])
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque

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

D = deque([X], M)
R = {X: 0}

x = X
for _ in range(min(N-1, M+1)):
  x = (x ** 2) % M
  if x in R:
    l = R[x]
    m = len(D) - l
    q, r = divmod(N - l, m)
    print(sum(D[i] for i in range(l)) + (q+1) * sum(D[i] for i in range(l, l+r)) + q * sum(D[i] for i in range(l+r, l+m)))
    break
  else:
    R[x] = len(D)
    D.append(x)
else:
  print(sum(D))

Solution (Python):
"""MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWO:,'..'xXWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO. .:kOo.,kNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO. .lNWWo..lXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MNOxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMMMMWKxoloxKWNc  .:xxd;  ,dxxxkXMXkxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMM
MKc''''''''''''''''.  ..'''''.   .''''.  .''MMMWx..,:. .xXo''.  .''.  ..'';kMk;'''''.  .'.''.  .''''''.  ..''.   .''MM
MWNXNNNNNNNNNNNNNNNO' ;KNNNNNKo. cKNNNd. lXNMMMK; ,0Wx. :NWXXl .dNNO' ;KNNNWMWNNNNNXc .kNNNNx. cXNNNNNO' ;KNN0; 'ONNMM
MMMMMMMMMMMMMMMMMWM0' :NMMMMWMX: .OMWWx. oWMMMMWx. ';. .dNMWWo .xMM0' :NWWMMMMMMMMWWl .OMMMWk. lWWMMWM0' ;XMMX: ,KMMMM
MMMMMMWMWkccccccccc;. :NMWNNNKd. :XMMWx. oWMMMWKo. .',. .,ldx; .dMM0' :NMMMMMMMNNWMWl .OMMMWk. lWMMMMM0' ;XMMX: ,0MMMM
MMWXKNWMWxcc,. .;cc;. :XMk,''..'lKWMMWx. oWMNx:. .lONNKxl.     .xMM0' :NMMMMMM0:,oKO' ,KMMMMk. lWWNkoc,. .;::;. ,KMMMM
MMXc.lXMMWWWNd..xWM0' :NM0;  ;kXWMMMWNl  oWMK:.;xXWWMWXx:. ,c' .dMM0' :NMMMMMMKc. ...;kWMMMMk. lWWc .:;. .clc:. ,KMMMM
MWWx. lXMWMMMK, lWM0' :NMMNx'.,ldxxoc'   oWMWNKNWWWN0o' .:kNWo .dMM0' :NMMMMMMMNO;  ,OWWWMMMk. lWM' lXx. lNMMX: ,KMMMM
MMMWk'.,xKNX0c..kWM0' :NMMMMNkl;,'',:l:  oWMMMMMWMWO' 'l0WMWWo .xMM0' :NMMMMMMMMMNd. .oXWMMMk. lWMd.....;0WMMX: ,KMMMM
MMMMWKo'...'..:kWMM0' :NMMMMMMMWWNNWWWx. oWMMMMMMMMWOxXWMWMWWo .xMM0' :NMMMMMMMMMMMKl. ,kNMMk. lWMWKkxx0NMWMMX: ,KMMMM
MMMMMMMN0kxk0XNWMMWKl;xNMMMMMMMMMMMMWM0c;kWMMMMMMMMMMMWWMMMMWk;:OMMXl,dNMMMMMMMMMMMMWO; .dNM0c;kWWMMMMMMMMMMMNd,oXMMMM
MMMMMMMMWWMWMMMMMMMMMWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWWMMWWMMWMMMMMMMMMMMMMMNkxKWMMWWMMMMMMMMMMMMMMWMMWMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM"""





import math;   		from collections import *
import sys;   		from functools import reduce
import time;   		from itertools import groupby




def get_ints()      : return map(int, input().strip().split())
def get_list()      : return list(get_ints())
def get_string()    : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args)  : return print(*args, end=" ")


DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (+1, -1)] 
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
              (+1, +1), (+1, +0), (+1, -1), (+0, +1)]

















n, x, m = get_ints()
prefix_sum = [0]
found = set()
d = dict()
ind = 0; doneInd = 1;
for i in range(n):
	if (x % m) not in found:
		found.add(x % m)
		d[x % m] = i
		prefix_sum.append(prefix_sum[-1] + (x % m))
	else:
		ind = d[x % m]
		doneInd = i
		break
	x **= 2
	x %= m




try:
	lastset = prefix_sum[-1] - prefix_sum[ind];
	offset = prefix_sum[ind]

	sz = len(prefix_sum) - ind - 1

	rem = n - ind
	ans = offset
	ans += lastset * (rem // sz)
	ans += prefix_sum[ind + (rem % sz)] - offset

except:
	ans = 1

print(ans)

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

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

A_history = [-1] * M
sum_history = [0] * (M + 1)
A = X
all_sum = A

sum_history[0] = A

for i in range(M):
    Anext = (A * A) % M
    all_sum += Anext
    sum_history[i + 1] = all_sum
    if A_history[A] == -1:
        A_history[A] = i
    else:
        break
    A = Anext

if i >= N:
    print(sum_history[N - 1])
else:
    cycle_start = A_history[A]
    cycle_end = i - 1
    cycle_length = cycle_end - cycle_start + 1
    cycle_time = N - cycle_start
    cycle_count = cycle_time // cycle_length
    cycle_mod = cycle_time % cycle_length
    ans = sum_history[cycle_start] + (sum_history[cycle_end + 1] - sum_history[cycle_start]) * cycle_count + \
          (sum_history[cycle_start + cycle_mod - 1] - sum_history[cycle_start])
    print(ans)

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, X, M = iim()

    if X == 0:
        print(0)
        return
    A = [X]

    i = 0
    vis = {X: 0}
    while i < N-1:
        a = A[i]**2 % M
        if a in vis:
            break
        elif a == 0:
            print(sum(A))
            return
        A.append(a)
        i += 1
        vis[a] = i
    else:
        a = X

    i = vis[a]
    n = len(A) - i
    a, b = divmod(N-i, n)
    ans = sum(A[i:]) * a
    for j in range(i):
        ans += A[j]
    for j in range(i, i+b):
        ans += A[j]
    print(ans)



if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq




INF = 10 ** 20

MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
flush = lambda: sys.stdout.flush()



def main():
    n, x, m = ns()

    total = x
    ai = x
    st = {x}
    prev = [x]

    for i in range(1, n):
        ai = ai ** 2 % m
        total += ai

        if ai in st:
            start = prev.index(ai)
            itrlen = len(prev) - start
            remainlen = n - i

            head = sum(prev[:start])
            itr = prev[start:]
            itrsum = sum(itr)
            remainitrsum = (remainlen // itrlen) * itrsum
            tail = sum(itr[:remainlen % itrlen])
            ans = head + itrsum + remainitrsum + tail
            print(ans)
            exit(0)

        st.add(ai)
        prev.append(ai)

    print(total)


if __name__ == '__main__':
    main()

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

mod=[0]*(m)

mod[x%m]=1
ans=x

for i in range(2,n+1):
    x=(x**2)%m
    
    if mod[x]==0:
        ans+=x
        mod[x]=i
    else:
        
        if mod[x]==-1:
            break
        
        else:
            turn=i-mod[x]
            ans+=x*(((n-i)//turn+1))
            mod[x]=-1

print(ans)

Solution (Python):
N,x,MOD = map(int, input().split())
s = x
flag = False
sflag = False
if N == 1:
  flag = True
  sflag = True
  print(s)
for i in range(1,MOD):
  x = (x*x) % MOD
  s += x
  if N == (i+1):
    flag = True
    break
if flag == True:
  if sflag == False:
    print(s)
else:
  t_s = 0
  cnt = 0
  init = x
  for i in range(MOD):
    x = (x*x) % MOD
    t_s += x
    cnt += 1
    if x == init:
      break
  bi = (N-MOD)//cnt
  res = (N-MOD)%cnt
  s += t_s * bi
  for i in range(res):
    x = (x*x) % MOD
    s += x
  print(s)

Solution (Python):
import sys, math
import io, os

from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal


mod = 998244353
INF=float('inf')

n,x,m=mdata()
d=dd(int)
d[x]=0
l=[x]
ans=x
for i in range(n-1):
    x**=2
    if x%m in d:
        x%=m
        ans+=sum(l[d[x]:])*((n-1-i)//(len(l)-d[x])) + sum(l[d[x]:d[x]+((n-1-i)%(len(l)-d[x]))])
        break
    else:
        x%=m
        ans+=x
        d[x]=i+1
        l.append(x)
out(ans)

Solution (Python):
def do():
    n, x, m = map(int, input().split())
    if x == 1: 
        print(n)
        return
    
    dat = []
    d = dict()
    dat.append(x)
    d[x] = True
    
    issyu_total = x % m
    isloop = False

    for i in range(n-1): 
        
        x = x ** 2 % m
        if x == 0: 
            print(sum(dat) % m)
            return
        if x in d:
            
            isloop = True
            loopstart = dat.index(x)
            break
        dat.append(x)
        issyu_total = (issyu_total + x)
        d[x] = True

    if isloop is False:
        print(issyu_total)
        return

    import math

    res = 0
    
    
    loopsum = sum(dat[loopstart:])
    looplength = len(dat) - loopstart

    res = sum(dat)
    n -= len(dat)

    fullloop = math.floor(n / looplength) 
    res += fullloop * loopsum

    nokori = n % fullloop
    res += sum(dat[loopstart:loopstart+nokori])

    
    print(res)
    






do()