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



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


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

    
    
    A = []
    used = set([x])
    A.append(x)
    while True:
        a_next = ((A[-1])**2) % m
        if a_next in used:
            n_loop = a_next
            break
        A.append(a_next)
        used.add(a_next)
    
    start_ptr = A.index(n_loop)
    end_ptr = len(A) - 1
    loop_len = end_ptr - start_ptr + 1
    loop_sum = sum(A[start_ptr:])
    ans = 0
    rem = n - 1
    
    if start_ptr < rem:
        ans += sum(A[:start_ptr])
        rem -= start_ptr
        if rem >= loop_len > 0:
            ans += loop_sum * (rem // loop_len)
        rem = rem % loop_len
        ans += sum(A[start_ptr:start_ptr + rem + 1])
        print(ans)
    else:
        ans = sum(A[:n])
        print(ans)
        return

    return


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def debug():
    A = [x]
    for _ in range(n - 1):
        next_A = pow(A[-1], 2) % m
        A.append(next_A)
    print(sum(A))


def resolve():
    A = [x]
    target = 0
    for _ in range(n - 1):
        next_A = pow(A[-1], 2) % m
        if next_A == 0:
            print(sum(A))
            exit()
        if next_A in A:
            target = next_A
            break
        A.append(next_A)
    else:
        print(sum(A))
        exit()

    idx = A.index(target)
    loop_length = len(A) - idx
    q, r = divmod(n - len(A), loop_length)
    base = sum(A)
    plus = sum(A[idx:]) * q + (sum(A[idx:idx + r]) if r != 0 else 0)
    print(base + plus)


if __name__ == '__main__':
    n, x, m = map(int, input().split())
    resolve()

Solution (Python):
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

def doubling(MAX, A):
    """ ダブリング """

    N = len(A)
    nxt = list2d(MAX, N, -1)
    sm = list2d(MAX, N, 0)
    for i, a in enumerate(A):
        nxt[0][i] = a
        sm[0][i] = a
    for k in range(1, MAX):
        for i in range(N):
            nxt[k][i] = nxt[k-1][nxt[k-1][i]]
            sm[k][i] = sm[k-1][i] + sm[k-1][nxt[k-1][i]]
    return (nxt, sm)

N, X, M = MAP()

MAX = 40
A = [0] * M
for i in range(M):
    A[i] = pow(i, 2, M)
nxt, sm = doubling(MAX, A)

cur = X
ans = X
N -= 1
for k in range(MAX-1, -1, -1):
    if N >> k & 1:
        ans += sm[k][cur]
        cur = nxt[k][cur]
print(ans)

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

arr = [x]
s = set()
s.add(x)
h = -1
r = 0
for i in range(n - 1):
	val = arr[-1]**2 % m
	if val not in s:
		arr += [arr[-1]**2 % m]
		s.add(arr[-1])
	else:
		h = i
		r = val
		break


res = sum(arr)
if h != -1:
	new_arr = arr[arr.index(r):]
	rest = n - (h + 1)
	c = len(new_arr)
	q = rest // c
	ssum = sum(new_arr) * q
	r = rest % c
	for i in range(r):
		ssum += new_arr[i]
	res += ssum	
	
print(res)

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,x,m=LI()
  ans=[x]
  d={x:x}
  y=-inf
  for i in range(n-1):
    x=x*x%m
    if x in d:
      y=x
      break
    d[x]=x
    ans.append(x)

  if y==-inf:
    return sum(ans)

  

  for i,x in enumerate(ans):
    if x==y:
      break

  sm=sum(ans)
  n-=len(ans)
  ans2=ans[i:]
  sm+=n//len(ans2)*sum(ans2)

  n%=len(ans2)
  for i in range(i,i+n):
    sm+=ans[i]

  return sm


print(main())

Solution (Python):
n, x, m = map(int, input().split())
mod_value = [-1 for i in range(2*m)] 
mod_check = [False for i in range(m)] 
value = x
i = 0
head = 0
while i < n:
    if not mod_check[value]:
        mod_value[i] = value
        mod_check[value] = True
        i += 1
        value = (value**2)%m
    else:
        head = mod_value.index(value)
        break
if i == n:
    print(sum(mod_value[:n]))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print(sum(mod_value[:head]) + sum(mod_value[head:i])*block_num + sum(mod_value[head:head+(n-head)%block_size]))

Solution (Python):
n, x, m = map(int, input().split())
s = set([x])
t = [x]
p = 1
for i in range(n):
    x = x * x % m
    if x in s:
        break
    else:
        s.add(x)
        t.append(x)
    p += 1
if p == n:
    print(sum(s))
    exit()

q = t.index(x)
l = p - q
b = sum(t[q:p])
ans = sum(t[:q])
n -= q
ans += n // l * b + sum(t[q:q + n % l])
print(ans)

Solution (Python):
n,x,m=map(int,input().split())
a=set()
b=[x]
for i in range(m):
  x=pow(x,2,m)
  if x in a:break
  a.add(x)
  b+=[x]
j=b.index(x)
n-=j
c=b[j:]
ans=sum(b[:j])+sum(c)*(n//len(c))+sum(c[:n%len(c)])
print(ans)

Solution (Python):

import sys
from sys import stdin

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

db = [ [0] * 40 for i in range(mod) ]
s = [ [0] * 40 for i in range(mod) ]

for i in range(mod):

    db[i][0] = i*i%mod
    s[i][0] = i


for j in range(1,40):
    for i in range(mod):

        db[i][j] = db[db[i][j-1]][j-1]
        s[i][j] = s[i][j-1] + s[db[i][j-1]][j-1]

now = X
ans = 0



for i in range(39,-1,-1):

    
    if N & (2**i) > 0:
        ans += s[now][i]
        now = db[now][i]

print (ans)

Solution (Python):
N,X,M = list(map(int,input().split()))
L = []
D = {}
L.append(X)
D[X] = D.get(X,0)+1
A = X
flag = 1
for i in range(N-1):
    A = A**2%M
    D[A] = D.get(A,0)+1
    if D[A]==2:
        flag=-1
        break
    else:
        L.append(A)
        if A==0:
            flag=0
            break
if flag==0:
    print(sum(L))
elif flag==1:
    print(sum(L))
else:
    LN = len(L)
    for i in range(LN):
        if L[i]==A:
            break
    Lu = L[i:]
    LuN = len(Lu)
    LuS = sum(Lu)
    out = 0
    if i!=0:
        out += sum(L[:i])
        N = N-i
    if N%LuN==0:
        out += LuS*(N//LuN)
        print(out)
    else:
        out += LuS*(N//LuN)
        amari = N%LuN
        out += sum(Lu[0:amari])
        print(out)

Solution (Python):
N,X,M = map(int,input().split())
array = [0,X]
array2 = [X]
a = X
sum = X
valid = True
while(True):
    a = pow(a,2,M)
    if a in array2:
        y = array2.index(a)
        break
    sum += a
    array.append(sum)
    array2.append(a)
l = len(array2)
h = l - y
if N <= y:
    print(array[N])
else:
    ans = array[y] + (array[-1]-array[y])*((N-y)//h) + array[y+(N-y)%h] - array[y]
    print(ans)

Solution (Python):

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

ans_list = [X]
if N == 1:
    print(X)
else:
    for i in range(1,N):
        ans = ans_list[-1]**2%M
        if ans in ans_list:
            break
        else:
            ans_list.append(ans)

    st_index = ans_list.index(ans)

    if st_index == N-1:
        print(sum(ans_list))
    else:
        total = sum(ans_list[:st_index])
        N -= st_index
        syo = N//(i-st_index)
        mod = N%(i-st_index)

        total += sum(ans_list[st_index:])*syo
        total += sum(ans_list[st_index:st_index+mod])
        print(total)

Solution (Python):
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n, x, m = getList()

    visited = [-1] * (m+1)
    acc = [-1] * (m+1)
    tmp = x
    tmpsum = 0
    index = 0
    while True:
        
        if visited[tmp] >= 0:
            cycle = index - visited[tmp]
            issyu = tmpsum - acc[tmp]
            outofcycle = index - 1
            ans = tmpsum
            cyclestart = tmp
            break

        visited[tmp] = index
        acc[tmp] = tmpsum
        tmpsum += tmp
        tmp = (tmp ** 2) % m
        index += 1
        if index == n:
            print(tmpsum)
            return

    
    ans += ((n - outofcycle - 1) // cycle) * issyu


    tmp = cyclestart
    for i in range((n - outofcycle - 1) % cycle):
        ans += tmp
        tmp = (tmp ** 2) % m

    print(ans)
    




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n, x, m = sp()
arr = [x]
s = set()
while True:
    x = (x * x) % m
    if x in s or x == 0 or x == 1:
        break
    s.add(x)
    arr.append(x)
answer = 0
m = n
if x == 0:
    for i in range(min(m, len(arr))):
        answer += arr[i]
    out(answer)
    exit()
if x == 1:
    for i in range(min(m, len(arr))):
        answer += arr[i]
    out(answer + max(0, m - len(arr)))
    exit()
find = arr.index(x)
if m <= len(arr):
    out(sum(arr[:m]))
    exit()
answer = sum(arr)
m -= len(arr)
arr = arr[find:]
for i in range(m % len(arr)):
    answer += arr[i]
s = sum(arr)
answer += s * (m // len(arr))
out(answer)

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

XX = X

ans = 0
a = 1
while a <= N:
    if O[X] == 0:
        O[X] = a
    else:
        b = O[X]
        c = a - b
        d = N - (N - b) % c 
        e = N - d
        h = ((N - b) // c)
        
        
        ans = 0
        X = XX
        for i in range(b):
            ans += X
            X = (X * X) % M
        for i in range(c):
            if i < e:
                ans += (h + 1) * X
            else:
                ans += h * X
            X = (X * X) % M
        print(ans)
        exit()
    ans += X
    X = (X * X) % M
    a += 1

print(ans)

Solution (Python):
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json

import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


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

    h = {X: 0}

    totals = [X]

    t = X

    c = X
    counter = 0
    while True:
        c = (c * c) % M
        if c in h:
            counter += 1
            t += c
            last_index = h[c]
            diff = t - totals[last_index]
            width = counter - last_index
            amari = last_index
            break
        counter += 1
        h[c] = counter
        t += c
        totals.append(t)

    if N <= amari:
        print(totals[N - 1])
        return

    N -= amari + 1
    rep = N // width
    mod = N % width

    k = totals[amari + mod]

    T = rep * diff + k
    print(T)


if __name__ == "__main__":
    main()

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

candicate = [pow(i, 2, M) for i in range(M)]
ans = 0
now = X
A = [0]
X2 = pow(X, 2, M)

d = dict()

flag = True
for i in range(1, N+1):
    if i == 1:
        A.append(X)
    
    else:
        nxt = candicate[A[i-1]]

        if d.get(nxt) == None:
            if nxt == 0:
                A.append(nxt)
                break
            else:
                A.append(nxt)
                d[nxt] = i

        else:
            flag = False
            break


if flag:
    print(sum(A))
else:
    l = d[nxt]
    r = i - 1
    circle_total = 0
    for j in range(l, r+1):
        circle_total += A[j]
    
    for j in range(1, l):
        ans += A[j]

    width = r - l + 1
    N -= (l - 1)
    ans += circle_total * (N // width)

    for j in range(l, l + N % width):
        ans += A[j]

    print(ans)

Solution (Python):
import sys

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

if m==1:
    print(0)
    sys.exit()

check=[-1 for i in range(m)]

A=[x%m]
check[x%m]=0

roopstart=10**15
for i in range(1,m):
    Ai=(A[i-1]*A[i-1])%m
    if check[Ai]!=-1:
        roopstart=check[Ai]
        break
    else:
        check[Ai]=i
        A.append(Ai)

if roopstart>=n:
    print(sum(A[:n]))
    sys.exit()

s=sum(A[:roopstart])

nn=n-roopstart
rooplen=len(A)-roopstart
roopnum=nn//rooplen
d=nn%rooplen

roopsum=sum(A[roopstart:])

s+=roopsum*roopnum
s+=sum(A[roopstart:roopstart+d])

print(s)

Solution (Python):
def solve(n, x, m):
    result = [x]
    checked = [0] * m
    checked[x] = 1
    while len(result) < n:
        x = x * x % m
        if checked[x] > 0:
            break
        result.append(x)
        checked[x] = len(result)
    else:
        return sum(result)

    l = len(result)
    i = checked[x]
    before_len = i - 1
    loop_len = l - i + 1
    loop_sum = sum(result[before_len:])
    d, e = divmod(n - before_len, loop_len)
    ans = sum(result[:before_len]) + loop_sum * d + sum(result[before_len:before_len + e])
    return ans


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

print(solve(n, x, m))

Solution (Python):

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

dic = {}
a = x
s = 0
c = m
for i in range(1, n + 1):
    if a not in dic:
        s += a
        dic[a] = [i]
    elif len(dic[a]) == 1:
        s += a * (1 + (n - i) // (i - dic[a][0]))
        dic[a].append(i)
    else:
        break
    a = pow(a, 2, m)
print(s)

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

if X == 0:
    print(0)
elif X == 1:
    print(N)
else:
    ans = 0
    check, dset = {}, set()

    roop = [0, 0]
    for i in range(2, M):
        j, temp, t = i**2, i, 1
        while j < M:
            temp += j
            t += 1
            j **= 2
        jump = j % M
        roop.append([temp, t, jump])

    while roop[X][1] <= N:
        check[X] = [ans, N]
        dset.add(X)
        ans += roop[X][0]
        N -= roop[X][1]
        X = roop[X][2]
        if X <= 1:
            print(ans + N*X)
            exit()
        if X in dset:
            cyc_ans = ans - check[X][0]
            cyc_N = check[X][1] - N
            ans += cyc_ans * (N//cyc_N)
            N %= cyc_N
    for i in range(N):
        ans += X
        X **= 2
    print(ans)

Solution (Python):
n, x, mod = [int(i) for i in input().split()]
ans = x
tmp = x
s = set()
s.add(x)
for i in range(1, n):
    tmp = (tmp * tmp) % mod
    if tmp in s:
        cycle = [tmp]
        t = (tmp * tmp) % mod
        while t != tmp:
            cycle.append(t)
            t = (t * t) % mod
        ans += sum(cycle) * ((n - i) // len(cycle))
        ans += sum(cycle[:(n-i)%len(cycle)])
        break
    else:
        s.add(tmp)
        ans += tmp
print(ans)

Solution (Python):
def main():
    n,x,m = map(int,input().split())
    
    
    rem = [(i**2)%m for i in range(m)]

    
    visited = [False for i in range(m)]
    idx = x
    s = x
    d = 1

    while not visited[idx]:
        visited[idx] = True
        s += rem[idx]
        idx = rem[idx]
        d += 1
        

    newsum = x
    newidx = x
    newd = 1
    while newidx!=idx:
        newsum += rem[newidx]
        newd += 1
        newidx = rem[newidx]

    
    
    d = d - newd
    s = s - newsum

    ans = x
    ansn = 1
    if newd<n:
        ans = newsum
        ansn = newd
    if ansn+d<=n:
        ans += s*((n-ansn)//d)
        ansn += ((n-ansn)//d) * d    
    
    while ansn<n:
        ansn += 1
        ans += rem[idx]
        idx = rem[idx]

    print(ans)
    


if __name__=="__main__":
    main()

Solution (Python):
n,x,m=map(int,input().split())
p=[x]
A=set([x])
f=0
for i in range(n-1):
	p.append(p[-1]**2%m)
	if p[-1] in A:
		f=1
		break
	else:
		A.add(p[-1])
if f==0:
	print(sum(p))
else:
	for i in range(len(p)):
		if p[i]==p[-1]:
			loop=len(p)-i-1
			break
	SUM=sum(p[i:-1])
	ans=sum(p)-p[-1]
	n-=len(p)-1
	ans+=SUM*(n//loop)+sum(p[i:i+n%loop])
	print(ans)

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

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

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

def main():
	N, X, M = getlist()
	if N <= 10 ** 6:
		cnt = 0
		A = X
		cnt += A
		for i in range(N - 1):
			A = (A ** 2) % M
			cnt += A

		print(cnt)
		return

	A = X
	D = defaultdict(int)
	L = [0] * (2 * 10 ** 5)
	L[1] = A
	D[A] = 1

	for i in range(2, N + 2):
		A = (A ** 2) % M
		if D[A] != 0:
			start = D[A]
			loop = i - D[A]
			break
		D[A] = i
		L[i] = A

	ans = 0
	for i in range(start, start + loop):
		ans += L[i]

	p = int((N - start + 1) // loop)
	ans *= p

	for i in range(1, start):
		ans += L[i]

	q = N - loop * p - start + 1
	for i in range(start, start + q):
		ans += L[i]

	print(ans)


if __name__ == '__main__':
	main()

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

a = X
count = 1
ai = [a]
mapping = [0 for i in range(10**5+1)]
mapping[a] = count
count += 1
for i in range(1, 10**5+1):
    a = (a ** 2 ) % M
    if mapping[a] == 0:
        ai.append(a)
        mapping[a] = count
    else:
        break
    count += 1
s = mapping[a]
e = mapping[ai[-1]]
loop = e - s + 1

if N <= e:
    print(sum(ai[:N]))
else:
    syo = (N - e) // loop
    amari = (N - e) % loop
    loop_total = sum(ai[s-1:e])
    
    ans = sum(ai) + loop_total * syo + sum(ai[s-1:s+amari-1])
    print(ans)

Solution (Python):
n, x, m = map(int,input().split())
rem = [0] * m
chk = [0] * (m + 1)
rem[0] = x
if x == 0:
  print(0)
  exit()

for i in range(1,m):
  rem[i] = (rem[i - 1] ** 2) % m
  if chk[rem[i - 1] ** 2 % m] > 1:
    temp1 = (rem[i - 1] ** 2) % m
    temp2 = i
  else:
    temp1 = (rem[i - 1] ** 2) % m
    temp2 = i

for i in range(m):
  if rem[i] == temp1:
    temp3 = i
    break

if temp2 != temp3:
  num = (n - temp3) // (temp2 - temp3)
  S = sum(rem[:temp3]) + sum(rem[temp3:temp2]) * num + sum(rem[temp3:n - (num * (temp2 - temp3))])
  print(S)
else:
  print(sum(rem))

Solution (Python):
n,x,m=map(int, input().split())
alist=[]
blist=[0]*m
num=x%m
while blist[num]==0:
  alist.append(num)
  blist[num]=1
  num=(num**2)%m
num1=alist.index(num)
num2=len(alist)
if x==1:
  print(n)
elif n<=num1:
  print(sum(alist[0:n]))
else:
  cycle=(n-num1)//(num2-num1)
  print(sum(alist[0:num1])+cycle*sum(alist[num1:num2+1])+sum(alist[num1:n-cycle*(num2-num1)]))

Solution (Python):
def pow_mod(x, y, mod=10**9 + 7):
    if y == 0:
        return 1
    res = 1
    for i in range(y.bit_length()):
        if y & (1 << i):
            res *= x
            res %= mod
        x *= x
        x %= mod
    return res


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

order = [0] * (m+1)
cnt = [-1] * (m+1)

now = x
a = -1
b = -1
for i in range(n):
    if cnt[now] != -1:
        a = cnt[now]
        b = i
        break
    order[i] = now
    cnt[now] = i
    now = pow_mod(now, 2, m)

if a == -1 and b == -1:
    print(sum(order))
    exit()

ans = 0
roop = [0]
for i in range(b):
    if i < a:
        ans += order[i]
    else:
        roop.append(order[i] + roop[-1])

n -= a

tmp = n % (b-a)
freq = n // (b-a)

ans += roop[-1] * freq
ans += roop[tmp]
print(ans)

Solution (Python):
N, X, M = map(int, input().split())
D = {i:0 for i in range(M)}
L = [X]
c = X
D[X]=0
S = X
for i in range(1, N):
  c = (c**2)%M
  if D[c]==0:
    D[c] = i
    L.append(c)
    S += c
    continue
  else:
    p, q = D[c], i
    break
else:
  print(S)
  exit()  
cycle = L[p:q]
cycle_sum = sum(cycle)
cycle_num = (N-q)//(q-p)
rest = (N-q)%(q-p)
S += cycle_sum*cycle_num
S += sum(cycle[:rest])
print(S)

Solution (Python):
N,X,M=map(int,input().split())
dist=[0 for i in range(M)]
A=X
loopin=-1
loopout=-1
ans=[0]
for i in range(N+1):
    if dist[A]!=0:
        loopin=dist[A]
        loopout=i
        ans.append(ans[-1]+A)
        break
    else:
        dist[A]=i
        ans.append(ans[-1]+A)
        A=(A*A)%M
if loopin==-1:
    print(ans[N])
    exit()


A=X
loop=loopout-loopin
def solve(l,r):
    assert 0<=l and l<=r
    if r<=loopout:
        return ans[r]-ans[l]
    if l<loopin:
        return ans[loopin]-ans[l]+solve(loopin,r)
    x=(l-loopin)//loop
    y=(r-loopin)//loop
    
    
    if x==y:
        return ans[r-y*loop]-ans[l-x*loop]
    
    tmp1=ans[l-x*loop]-ans[loopin]
    tmp2=(ans[loopout]-ans[loopin])*(y-x)
    tmp3=ans[r-y*loop]-ans[loopin]
    
    return tmp1+tmp2+tmp3
print(solve(0,N))

Solution (Python):
N,X,M=map(int,input().split())
lst=[]
n,s=X,0
for i in range(N):
  if n in lst:break
  lst.append(n)
  n=(n*n)%M
if len(lst)<N:
  k=lst.index(n)
  s1=sum(lst[:k])
  s2=sum(lst[k:])*((N-k)//(len(lst)-k))
  s3=sum(lst[k:k+(N-k)%(len(lst)-k)])
  s=s1+s2+s3
else:s=sum(lst)
print(s)

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

loop = [0]*m

a = x
is_loop = False
for i in range(n):
        if loop[a] == 1:
            
            loop[a] += 1
            is_loop = True
            break
        else:
            
            loop[a] = 1
            a = (a**2)%m

if not is_loop:
    
    ans = 0
    for i in range(m):
        ans += i*loop[i]
    print(ans)
else:
    
    
    def get_loop_length(b):
        c = 1
        s = b
        b_tmp = b
        while True:
            b_tmp = (b_tmp**2)%m
            if b == b_tmp:
                return c, s
            else:
                c += 1
                s += b_tmp
    loop_length, loop_sum = get_loop_length(a)
    
    ans = 0
    b = x
    
    while b != a:
        ans += b
        b = (b**2)%m
        n -= 1
    
    ans += loop_sum*(n//loop_length)
    n = n % loop_length
    b = a
    for i in range(n):
        ans += b
        b = (b**2)%m
    print(ans)

Solution (Python):
def solve(N, X, M):
    seen = set()
    front = [X]
    cycle = []
    for i in range(N - 1):
        x = (front[-1] * front[-1]) % M
        if x in seen:  
            index = front.index(x)
            front, cycle = front[:index], front[index:]
            break
        front.append(x)
        seen.add(x)
    if N <= len(front):
        return sum(front[:N])

    if N <= len(front) + len(cycle):
        return sum(front) + sum(cycle[: N - len(front)])

    q, r = divmod(N - len(front), len(cycle))

    if False:
        A = [pow(X, 2 ** i, M) for i in range(N)]
        B = front + cycle * q + cycle[:r]
        print(A, B)
        assert A == B
    return sum(front) + sum(cycle) * q + sum(cycle[:r])


N, X, M = [int(x) for x in input().split()]
print(solve(N, X, M))

Solution (Python):
n,x,m=map(int,input().split())
cnt2=set()
cnt2.add(x)
cnt3=[x]
cnt4=0
cnt5=0
cnt6=x
for i in range(1,m+10):
    num2=pow(cnt6,2,m)
    if num2 in cnt2:
        for j in range(len(cnt3)):
            if cnt3[j]==num2:
                cnt7=j
                break
        cnt10=len(cnt3)-cnt7
        num4=sum(cnt3[:cnt7])
        cnt4=len(cnt3)
        break
    cnt2.add(num2)
    cnt3.append(num2)
    cnt6=num2
    if num2==0:
        ans=sum(cnt3)
        cnt5=1
        break
if cnt5==0 and n>cnt4:
    ans=num4
    n-=cnt7
    ans+=(n//cnt10)*sum(cnt3[cnt7:])
    ans+=sum(cnt3[cnt7:(n%cnt10)+cnt7])
if cnt4>=n:
    ans=sum(cnt3[:n])
print(ans)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

n,x,m = inm()
k = -1
a = x
h = {}
f = [-1]*100001
f[0] = a
h[a] = 0
for i in range(1,n):
    a = (a*a)%m
    f[i] = a
    if a in h:
        k = i
        j = h[a]
        break
    else:
        h[a] = i

if k<0:
    print(sum(f[:n]))
else:
    p = k-j
    q = (n-j)//p
    r = (n-j)%p
    
    print(sum(f[:j+r])+q*sum(f[j:k]))

Solution (Python):
n,x,m = map(int,input().split())
rec = [-1 for _ in range(m)]
rec[x] += 1
now = x
cnt = 1
while True:
  now = now ** 2
  now %= m
  
  if rec[now] == -1:
    rec[now] = cnt
    cnt += 1
    
  else:
    
    
    break
end = rec[now]
cyc = cnt - end


if n <= end:
  ans = 0
  now = x
  for _ in range(n):
    ans += now
    now **= 2
    now %= m
  print(ans)
  exit()
ans = 0
now = x
for i in range(end):
  ans += now
  now **= 2
  now %= m
  n -= 1
ans2 = 0

for i in range(cyc):
  ans2 += now
  
  now **= 2
  now %= m

db = n // cyc
n %= cyc
ans += ans2 * db

ans3 = 0
for _ in range(n):
  ans3 += now
  now **= 2
  now %= m
  

print(ans+ans3)

Solution (Python):
n, x, m = map(int, input().split())
di = {}
for i in range(m+1):
    di[i] = -1
li = []
for i in range(m+1):
    li.append(x)
    di[x] = i
    x = pow(x, 2, m)
    if di[x]  >= 0:
        break


ans = 0

for j in range(di[x]):
    ans += li[j]
loop_sum = 0
for j in range(di[x], i+1):
    loop_sum += li[j]

loop = i+1-di[x] 

n -= di[x]
k = n//loop 
ans += loop_sum * k

kk = n-k*loop 

ans += sum(li[di[x]:di[x]+kk])
print(ans)

Solution (Python):
n,x,m = map(int, raw_input().split())
ans = 0

seen = {}
reverse = {}
c = 0
while(x not in seen):
	seen[x] = c
	reverse[c] = x
	c+=1
	x = (x**2) % m


def f(n,a,b,reverse):
	ans = 0
	
	for i in xrange(b+1):
		if n > 0:
			ans += reverse[i]
			n-=1
		else:
			break
	if n > 0:
		t = sum([reverse[uu] for uu in xrange(a,b+1)] or [0])
		ans += n/(b-a+1) * t
		n %= (b-a+1)

		for i in xrange(a,b+1):
			if n > 0:
				ans += reverse[i]
				n-=1
			else:
				break

	return ans


print f(n, seen[x], c-1, reverse)

Solution (Python):
n,x,m=map(int,input().split())
if n<=m+1:
    s=0
    a=x
    for c in range(n):
        s+=a
        a=pow(a,2,m)
else:
    l=[0]*m
    a=x
    l[a]=1
    for c in range(2,m+2):
        a=pow(a,2,m)
        if l[a]>0:
            d1=l[a]
            d2=c
            d3=a
            break
        l[a]=c
    q=(n-d1)//(d2-d1)
    r=(n-d1)%(d2-d1)+d1
    s=0
    for c in range(d2-d1):
        s+=a
        a=pow(a,2,m)
    s*=q
    for c in range(r):
        s+=x
        x=pow(x,2,m)
print(s)

Solution (Python):

import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
N,X,M=map(int,input().split())
l=[0]*(M+1)
l[X]=1
X2=X
ans=0
for i in range(10**5+1):
    
    X=pow(X,2,M)
    if l[X]==0:
        l[X]=i+2
    else:
        start=l[X]
        end=i+2
        
        break

res=[]
X=X2
loop=[]

for i in range(start-1):
    res.append(X)
    X=pow(X,2,M)
for i in range(start,end):
    loop.append(X)
    X=pow(X,2,M)

loopsum=sum(loop)
if N<=len(res):
    for i in range(N):
        ans=ans+res[i]
else:
    for i in range(len(res)):
        ans=ans+res[i]
    loopnum=(N-len(res))//len(loop)
    loopres=(N-len(res))%len(loop)
    for i in range(loopres):
        ans=ans+loop[i]
    ans=ans+loopnum*loopsum
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,m = list(map(int, input().split()))
v = x
seen = [0]*m
c = 0
val = 0
count = 0
tmp = 0
if n>m:
    while True:
        if seen[v]==2:
            break
        if seen[v]==1:
            count += 1
            tmp += v
        else:
            val += v
            c += 1
        seen[v] += 1
        v = (v**2)%m
    ans = val + ((n-c)//count) * tmp
    for i in range((n-c)%(count)):
        ans += v
        v = (v**2)%m
else:
    ans = 0
    v = x
    for i in range(n):
        ans += v
        v = (v**2)%m
print(ans)

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

i = 0
a = x
aa = set()
aal = []
s = 0
while a not in aa:
    aa.add(a)
    aal.append(a)
    s += a
    i += 1
    if i == n:
        print(s)
        exit(0)
    a = (a ** 2) % m
    if a == 0:
        print(s)
        exit(0)
st  = aal.index(a)
cont = aal[st:]
nc = len(cont)
n -= st
ans = sum(aal[:st]) + sum(cont) * (n // nc) + sum(cont[:(n % nc)])
print(ans)