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 main():
    N, X, M = map(int, input().split())

    n = [-1] * M
    n[X] = 0

    A = X
    history = [X]
    loop_start = -1
    loop_start_num = -1
    for i in range(1, M+2):
        Anext = A*A % M
        if n[Anext] != -1:
            loop_start = n[Anext]
            loop_start_num = Anext
            break
        history.append(Anext)
        n[Anext] = i
        A = Anext

    
    ans = 0
    for i in range(min(loop_start, N)):
        ans += history[i]
        N -= 1
    
    loop = history[loop_start:]
    loop_len = len(loop)
    sum_loop = sum(loop)
    

    n_loop = N // loop_len
    ans += sum_loop * n_loop
    N -= loop_len * n_loop

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

if __name__ == '__main__':
    main()

Solution (Python):
a = [int(s) for s in input().split()]
b = a[1]
c = [b]
d = {b:0}
flag = int(0)
k = int(0)
t = int(0)
m = int(0)
suma = int(0)
sumb = int(0)
cnt = int(0)
newc = []
newnewc = []

for i in range(1, a[0]):
    b = (b ** 2) % a[2]
    if d.get(b) == None:
        d[b] = i
        c.append(b)
    else:
        flag = 1
        sumb = sum(c)
        k = int(c.index(b))
        newc = c[k:]
        suma = sum(newc)
        k = len(newc)
        t = i
        m = (a[0] - t) % k
        break

if flag == 1:
    newnewc = newc[:m]
    print((a[0] - t) // k * suma + sumb + sum(newnewc))
else:
    print(sum(c))

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float("inf")

N,X,M = map(int,input().split())
A = [0]*100010
A[0] = X
d = defaultdict(int)
d[X] = 1
l = [X]

ans = X
for i in range(1,N):
    num = pow(A[i-1],2,M)
    l.append(num)
    if d[num] == 0:
        A[i] = num
        d[num] += 1
        ans += num
    else:
        kaburi = num
        break
else:
    print(ans)
    exit()

kaburi_index = l.index(kaburi)
loop_len = len(l)-1-kaburi_index
loop_sum = sum(l[kaburi_index:len(l)-1])

nokori = N-i
loop = nokori//loop_len
amari = nokori%loop_len

ans += loop_sum*loop
ans += sum(l[kaburi_index:kaburi_index+amari])


print(ans)

Solution (Python):
N,X,M = map(int,input().split(" "))
q = [-1] * (M + 1)
A = X
i = 0
su = []
p1 = 0
p2 = 0
while q[A] == -1:
    q[A] = i
    su.append(A)
    A = (A * A) % M
    i += 1

if N == len(su):
    print(sum(su))
else:
    r = q[A]
    r2 = (N - r) % (i - r)

    ans1 = sum(su[0:r])
    ans2 = sum(su[r:r + r2])
    ans3 = sum(su[r::])

    print(ans1 + ans2 + ans3 * ((N - r) // (i - r)))

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

ai = x
i = 0

memo = []
d = {}
tmp = 0

while True:
    if ai in d:
        break
    d[ai] = i
    memo.append(ai)

    ai = (ai ** 2) % m
    i += 1

s = d[ai]
e = i
su = sum(memo[s:])

if n <= e+1:
    print(sum(memo[0:n]))
else:
    zan = n - s
    ans = sum(memo[:s]) + (zan // (e-s)) * su
    if zan % (e-s):
        ans += sum(memo[s:s+(zan % (e-s))])
    print(ans)

Solution (Python):
N,X,M=map(int,input().split())
A=[0 for i in range(10**5)]
A[X]=1
c=[]
d=[]
now=X
for i in range(2,N+1):
  now=now**2%M
  if A[now]==0:
    A[now]=i
  else:
    s=A[now]
    p=i-s
    cycle=[0 for i in range(p)]
    f=[]
    for j in range(10**5):
      if s<=A[j]<i:
        cycle[A[j]-s]=j
      if A[j]<s and A[j]!=0:
        f.append(j)
    c=cycle
    d=f
    break
if c==[]:
  ans=0
  for i in range(len(A)):
    if A[i]!=0:
      ans+=i
  print(ans)
else:
  x=len(d)
  y=len(c)
  ccount=(N-x)//y
  amari=(N-x)%y
  ans=sum(d)+sum(c)*ccount+sum(c[:amari])
  print(ans)

Solution (Python):
import sys
import math


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


def main():
    N, X, M = map(int, input().split())
    L = [X]
    D = [0] * M
    D[X] = 1
    k = 2
    while k < N + 1:

        
        l = L[-1] ** 2 % M


        if D[l] != 0:
            n = N - k+1  
            one_cycle = k - D[l]
            mass = sum(L[D[l]-1:])
            ans = n//one_cycle *mass
            res = sum(L[D[l]-1:D[l]+(n%one_cycle)-1])
            print(ans +res +sum(L))
            exit()

        if l == 0:
            print(sum(L))
            exit()

        L.append(l)
        D[l] =k
        k += 1

    print(sum(L))


if __name__ == "__main__":
    main()

Solution (Python):
N,X,M = map(int,input().split())
c1 = [X]
c2 = {X}
ans = X
for i in range(N-1):
    X = pow(X,2,M)

    if X not in c2:
        c1.append(X)
        c2.add(X)
        ans += X
    else:
        b = c1.index(X)
        break
else:
    print(ans)
    exit()
l = len(c1) - b
t = N-i -1
ans += (t//l) * sum(c1[b:]) + sum(c1[b:b+t%l])
print(ans)

Solution (Python):

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


def main():
    n, x, m = map(int, input().split())
    sedic = dict()
    sedic[x] = 1
    wa=[x]
    for i in range(2, min(10**5+100,n+1)):
        x = (x**2) % m
        if x in sedic:
            ans=sum(wa)
            roop,amari=divmod(n-i,i-sedic[x])
            ans+=sum(wa[sedic[x]-1:])*roop
            ans+=sum(wa[sedic[x]-1:sedic[x]+amari])
            print(ans)
            break
        sedic[x]=i
        wa.append(x)
    else:
        print(sum(wa))

if __name__ == '__main__':
    main()

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

col=[x]
sude=[0]*m
sude[x]=1
now=x
ishu=0
hajimari=0
for i in range(m):
    now**=2
    now%=m
    
    if(sude[now]==0):
        sude[now]=i+2
        col.append(now)
    else:
        ishu=i-sude[now]+2
        hajimari=sude[now]-1
        break




saisho=0
loop=0
for i in range(hajimari):
    saisho+=col[i]
for i in range(hajimari,len(col)):
    loop+=col[i]



ans=0

if(n<hajimari):
    ans+=col[i]
else:
    ans=saisho+loop*((n-hajimari)//ishu)
    nokori=n-hajimari-ishu*((n-hajimari)//ishu)
    for i in range(hajimari,hajimari+nokori):
        ans+=col[i]

print(ans)

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

order = []
hist = [0] * M

for i in range(N):
    if hist[X]:
        j = order.index(X)
        rem = N-i
        d,m = divmod(rem,i-j)
        for k in order[j:]:
            hist[k] += d
        for k in order[j:j+m]:
            hist[k] += 1
        break
    order.append(X)
    hist[X] += 1
    X = (X*X)%M

ans = 0
for i,h in enumerate(hist):
    ans += i*h
print(ans)

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, X, M = map(int, readline().split())
ans = X
x = X
data = [0]*M
data[x] = 0
t = [x]
for i in range(1,N):
    nx = x ** 2 % M     
    if nx == 0:
        break
    if data[nx] != 0:
        res = N-i
        s = i-data[nx]
        syuki_cnt = res // s
        rem_cnt = res % s
        nt = t[data[nx]:i]
        ans += sum(nt)*syuki_cnt+sum(nt[:rem_cnt])
        break
    ans += nx
    x = nx
    data[nx] = i
    t.append(nx)
print(ans)

Solution (Python):
def main():
    N, X, M = list(map(int, input().split()))
    visited = [0] * M
    a = X
    path = list()
    while visited[a] == 0:
        visited[a] = 1
        path.append(a)
        a = (a**2) % M
    
    
    offset_size = 0
    for p in path:
        if p == a:
            break
        offset_size += 1
    loop_size = len(path) - offset_size
    
    count = [0] * M
    n = 0
    
    for p in path[:offset_size]:
        count[p] += 1
        n += 1
        if n == N:
            break
    
    count_loop = (N - n) // loop_size
    for p in path[offset_size:]:
        count[p] += count_loop
        n += count_loop
    
    for p in path[offset_size:]:
        if n == N:
            break
        count[p] += 1
        n += 1
    print(sum([m * c for m, c in enumerate(count)]))


if __name__ == '__main__':
    main()

Solution (Python):


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

fresh = [True] * M 
fresh[X] = False
turn = [-1] * M 
turn[X] = 0
status = True




def search_loop():
    log = [X] 
    last  = X 
    counter = 0
    loop_count = -1
    loop_start = -1
    while status:
        
        next_spot = (last * last) % M 
        counter += 1
        
        if(fresh[next_spot]):
            
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            turn[next_spot] = counter
        else:
            log.append(next_spot)
            last = next_spot
            fresh[next_spot] = False
            loop_count = counter - turn[next_spot]
            loop_start = turn[next_spot]
            
            break
    
    return log, last, turn, counter, loop_count, loop_start



ret = search_loop()

log = ret[0]
last = ret[1]
turn = ret[2]
counter = ret[3]
loop_count = ret[4]
loop_start = ret[5]






if(N <= len(log)):
    ans = sum(log[:N])
else:
    ans = sum(log[:loop_start])
    
    
    sum_loop = sum(log[loop_start:len(log)-1])
    mawaru_kaisuu = (N-loop_start) // loop_count
    
    ans += (sum_loop * mawaru_kaisuu)
    nokori = (N-loop_start) - (loop_count*mawaru_kaisuu)
    ans += sum(log[loop_start:loop_start+nokori]) 


print(ans)

Solution (Python):









INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,x,m=INTM()
    bool=[False]*m
    mod=[]
    temp=x
    for i in range(m+1):
        if bool[temp]:
            break
        else:
            bool[temp]=True
            mod.append(temp)
            temp=(temp*temp)%m
    b=mod.index(temp)
    if b>0:
        sumt=sum(mod[0:b])
        mod=mod[b:]
    else:
        sumt=0
    lm=len(mod)
    sumr=0
    if (n-b)%lm!=0:
        sumr=sum(mod[0:(n-b)%lm])
    print(sumt+sumr+sum(mod)*((n-b)//lm))

if __name__=='__main__':
    do()

Solution (Python):
N, X, M = map(int, input().split())
if M==1:
  print(0)
  exit()
lis = [0]*M
lis[0] = X
check = [-1]*M
check[X] = 0
for i in range(1,M):
  lis[i] = pow(lis[i-1],2,M)
  if check[lis[i]]>=0:
    cyc = i-check[lis[i]]
    start = check[lis[i]]
    break
  check[lis[i]] = i
from itertools import groupby, accumulate, product, permutations, combinations
cum = list(accumulate(lis))
cyc_cum = cum[-1]-cum[start]
if N-1<=start+cyc:
  ans = cum[N-1]
else:
  ans = cyc_cum*((N-1-start)//cyc)+cum[(N-1-start)%cyc+start]
print(ans)

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

A = X
loop_end = N
loop = [A]
loop_set = set(loop)
loop_last = -1
for i in range(1, N):
	A = (A * A) % M
	if A in loop_set:
		loop_last = A
		loop_end = i
		break
	loop_set.add(A)
	loop.append(A)

total_head = 0
total_loop = 0
total_tail = 0

i = 0
while i < N:
	A = loop[i]
	if A == loop_last:
		break
	total_head += A
	loop_set.remove(A)
	i += 1

if loop_end < N:
	loop_len = loop_end - i
	loop_rest = (N - i) % loop_len
	loop_count = (N - i - loop_rest) // loop_len
	while i < loop_end:
		total_loop += loop[i]
		i += 1
	i += loop_len * (loop_count - 1)
	A = loop[-1]
	A = (A * A) % M
	while i < N:
		total_tail += A
		A = (A * A) % M
		i += 1
else:
	loop_count = 0



print(total_head + total_loop * loop_count + total_tail)

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

ans = X
N -= 1
prev = X
used = [0]*M

while N:
    new = pow(prev, 2, M)
    if used[new] == 1:
        cnt = 1
        num = new
        while new != prev:
            num += pow(new, 2, M)
            new = pow(new, 2, M)
            cnt += 1
        ans += (N//cnt)*num
        N %= cnt
        break
    used[new] = 1
    ans += new
    prev = new
    N -= 1

while N:
    new = pow(prev, 2, M)
    ans += new
    prev = new
    N -= 1
print(ans)

Solution (Python):
n , x , m = map(int,input().split())
amari = [-1 for i in range(m)]
amari[x] = 0
cou = 0
now = x
p = 0
zyun = [x]
while True:
    nex = (now**2) % m
    if nex == 0:
        p = 1
        break
    elif amari[nex] == -1:
        amari[nex] = amari[now] + 1
        now = nex
        zyun.append(nex)
    elif amari[nex] != -1:
        p = 2
        break

if p == 1:
    ans = 0
    for i in range(m):
        if amari[i] != -1:
            ans += i
    print(ans)
elif p == 2:
    ans = 0
    ans += sum(zyun[:amari[nex]])
    ans += sum(zyun[amari[nex]:]) * ((n-amari[nex])//(amari[now]-amari[nex]+1))
    y = (n-amari[nex]) % (amari[now]-amari[nex]+1)
    if y != 0:
        ans += sum(zyun[amari[nex]:amari[nex]+y])
    print(ans)

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

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

history = []
visited = set()

x = X
for _ in range(N):
    if x in visited:
        break
    visited.add(x)
    history.append(x)
    x = next_a(x)

if len(history) == N:
    
    print(sum(history))
else:
    loop_start = history.index(x)
    loop_size = len(history) - loop_start
    loop_sum = sum(history[loop_start:])
    if ((N - len(history)) % loop_size) == 0:
        
        print(sum(history) + loop_sum * ((N - len(history)) // loop_size))
    else:
        
        hasu = sum(history[loop_start:loop_start+((N - len(history)) % loop_size)])
        print(sum(history) + loop_sum * ((N - len(history)) // loop_size) + hasu)

Solution (Python):
n,x,m=map(int,input().split())
s=set()
ct=x
ans=[x]
s.add(x)
f=0
for i in range(n-1):
  ct**=2
  ct%=m
  if ct not in s:
    s.add(ct)
    ans.append(ct)
  else:
    f=1
    break
if f==0:
  print(sum(ans))
  exit()
y=ans.index(ct)
z=sum(ans[y:len(ans)])
z2=0
for i in range(((n-y)%(len(ans)-y))):
  z2+=ans[y+i]
print(sum(ans[0:y])+z*((n-y)//(len(ans)-y))+z2)

Solution (Python):
import sys

input = sys.stdin.readline

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

arr = [-1] * m
cumsum = [x]
a = x
for i in range(1, n):
    a *= a
    a %= m
    if arr[a] == -1:
        arr[a] = i
        cumsum.append(cumsum[-1] + a)
    else:
        di, mo = divmod(n - i, i - arr[a])

        ans = cumsum[-1]
        ans += di * (cumsum[-1] - cumsum[arr[a] - 1])
        ans += cumsum[arr[a] - 1 + mo] - cumsum[arr[a] - 1]
        break
else:
    ans = cumsum[-1]

print(ans)

Solution (Python):
n,x,m = map(int,input().split())
if x == 1:
  print(n)
  exit()
u = [0 for _ in range(m)]
rs = [0 for _ in range(m+1)]
s = x
u[x] = 1
rs[1] = x
i = 2
while True:
  x = (x*x)%m
  if u[x] == 0:
    u[x] = i
    s += x
    rs[i] = s
    i += 1
  else:
    ls = u[x]
    le = i-1
    break
if n <= le:
  print(rs[n])
  exit()
ans = rs[ls-1]
ll = le-ls+1
nl = n-ls+1
lsum = rs[le] - rs[ls-1]
q = nl//ll
r = nl%ll
ans += q*lsum
ans += rs[ls-1+r] - rs[ls-1]
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, x, m = LI()
check = [-1] * (m+1)
cnt = [-1] * (m+1)
ans = x
tmp = x
for i in range(min(n-1, m-1)):
    if check[tmp % m] < 0:
        check[tmp % m] = ans
        cnt[tmp % m] = i
        ans += tmp**2 % m
        tmp = tmp**2 % m
    else:
        roop = i - cnt[tmp % m]
        tmp2 = ans - check[tmp % m]
        r, l = (n-1 - i) // roop, (n-1 - i) % roop
        ans += tmp2 * r
        for j in range(l):
            ans += tmp**2 % m
            tmp = tmp**2 % m
        print(ans)
        break
else:
    print(ans)

Solution (Python):
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict






def solve(n,x,m):  
    console("----- solving ------")
    if m == 1:
        return 0

    arr = [x]
    pos = {}

    for i in range(min(n-1, 2*m)):
        x = arr[-1]
        new = (x*x)%m
        if new in pos:
            break
        pos[new] = i           
        arr.append(new)

    sumarr = sum(arr)
    lenarr = len(arr)

    if len(arr) == n:
        console(arr)
        return sumarr

    m = len(arr) - pos[new] - 1

    cycles = (n-lenarr) // (m)
    remainder = (n-lenarr) % (m)

    console(m, cycles, remainder)
    sumarr += cycles*sum(arr[-m:])
    sumarr += sum(arr[-m:-m+remainder])

    console(492443256176507 - sumarr)
    
    return sumarr 


def console(*args):  
    
    return




for case_num in [1]:
    
    

    
    
    
    
    

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

    
    
    
    
    
    

    res = solve(n,x,m)  
    
    
    

    
    print(res)

Solution (Python):
n,x,m = map(int,input().split())
appeared=[False]*(m+1)
appeared[x]=True
ans = [0]
ANS = 0
div = x
DIV=[]
llen = 0
cnt = 0
while cnt < n:
  if div == 0:
    break
  cnt += 1
  ANS += div
  DIV.append(div)
  ans.append(ANS)
  llen += 1
  appeared[div] = True
  if appeared[div**2%m]:
    PPP=DIV.index(div**2%m)
    ANS = (ANS-ans[PPP])*((n-PPP)//(llen-PPP))
    rem = (n-PPP)%(llen-PPP)
    ANS+=ans[rem+PPP]
    break
  div **= 2
  div %= m
  
print(ANS)

Solution (Python):
N, X, M = map(int, input().split())
cnt = [0] * M
cnt[X] = 1
start = -1
seq = [X]
for i in range(1, N):
    X = X * X % M
    if cnt[X] > 0:
        start = X
        break
    seq.append(X)
    cnt[X] += 1

if start < 0:
    print(sum(seq))
    exit()

cycle_start_idx = seq.index(start)
header = seq[:cycle_start_idx]
cycle = seq[cycle_start_idx:]
in_cycle_N = N - len(header)
q, r = divmod(in_cycle_N, len(cycle))
ans = sum(header) + sum(cycle) * q + sum(cycle[:r])
print(ans)

Solution (Python):
from collections import deque
N,X,M = map(int, input().split())

nodeset = set()
nodeset.add(X)

nodeq = deque()
nodeq.append(X)

is_finish = False
s,e = 0, N
for i in range(N-1):
    X = (X*X) % M
    if X in nodeset:
        is_finish = True
        
        for p, start in enumerate(nodeq):
            if X == start:
                s = p
                break
        
        break

    nodeq.append(X)
    nodeset.add(X)

nodelist = list(nodeq)
if is_finish:
    loop_size = len(nodelist) - s 
    loop_cnt = (N - s) //loop_size 
    loop_sum = sum(nodelist[s:]) 
    alpha = (N - s) % loop_size 
    result = sum(nodelist[:s]) + loop_cnt * loop_sum + sum(nodelist[s:s+alpha])
    print(result)
else:
    print(sum(nodelist))

Solution (Python):
n, x, m = map(int, input().split())
dp = [x]
s = set([x])
for i in range(1000000):
    if ((dp[-1] ** 2) % m) in s:
        dp.append((dp[-1] ** 2) % m)
        break
    s.add((dp[-1] ** 2) % m)
    dp.append((dp[-1] ** 2) % m)
ind = dp.index(dp[-1])
del dp[-1]
print(sum(dp[:ind]) + sum(dp[ind:]) * ((n - ind) // (len(dp) - ind)) + sum(dp[ind:ind + ((n - ind) % (len(dp) - ind))]))

Solution (Python):
n,x,m = map(int,input().split())
first = [0] * (m+1)

a = [x]
first[x] = 1
for i in range(2,m+10):
    x = pow(x,2,m)
    if(first[x] != 0):
        break
    first[x] = i
    a.append(x)



if(i-1 >= n):
    ans = sum(a[:n])
    print(ans)
    exit()

cyc = a[first[x]-1:]
for j in range(1,len(cyc)):
    cyc[j] += cyc[j-1]

ans = sum(a[:first[x]-1])

rem = n - first[x] + 1
ans += cyc[-1] * (rem//len(cyc))

if(rem%len(cyc) != 0):
    ans += cyc[rem%len(cyc) - 1]
print(ans)

Solution (Python):
n, x, m = map(int, input().split())
ans = [x]
for _ in range(m):
    ans.append(pow(ans[-1], 2, m))
loop = [ans[-1]]
check = ans[-1]
for _ in range(m):
    next = pow(loop[-1], 2, m)
    if next == check:
        break
    else:
        loop.append(next)
if n <= m+1:
    A = sum(ans[:n])
else:
    times = (n - m) // len(loop)
    amari = (n - m) % len(loop)
    A = sum(ans[:-1]) + sum(loop) * times + sum(loop[:amari])
print(A)

Solution (Python):
n,x,m=map(int,input().split())
A=dict()
i=0
y=x
while True:
    if not(y in A.keys()):
        A[y]=i
        i+=1
        y=(y**2)%m
    else:
        break
j=A[y]



A=list(sorted(A.items(),key=lambda x:x[1]))

s=0
for k in range(j):
    s+=A[k][0]
p=(n-j)//(i-j)
q=(n-j)%(i-j)
t=0
for k in range(j,i):
    t+=A[k][0]
u=0
if q!=0:
    for k in range(j,j+q):
        u+=A[k][0]
else:
    u=0
print(s+t*p+u)

Solution (Python):
def main():
	N, X, M = [int(a) for a in input().split(" ")]
	used_r = [0] * M
	r = [-1, X]
	used_r[X] = 1
	loop_start_elm = -1
	loop_start_n_2 = -1
	for i in range(M):
		A = r[-1]
		B = (A * A) % M
		if used_r[B] == 0:
			r.append(B)
			used_r[B] = 1
		else:
			loop_start_elm = B
			loop_start_n_2 = i + 2
			break
	loop_start_n = r.index(B)

	s1 = sum(r[:loop_start_n]) + 1
	s2 = sum(r[loop_start_n:loop_start_n_2])
	loop_len = loop_start_n_2 - loop_start_n
	loop_n = int((N - loop_start_n + 1) / loop_len)
	rest_n = (N - loop_start_n + 1) % loop_len
	s3 = sum(r[loop_start_n:(loop_start_n + rest_n)])
	print(s1 + s2 * loop_n + s3)

main()

Solution (Python):
n, x, m = map(int, input().split())
tmp = x
t = [0] * m
cnt = 0
s = 0
while t[x] == 0:
    t[x] += 1
    cnt += 1
    s += x
    x = x * x % m
k = tmp
cnt2 = 0
ans2 = 0
while k != x:
    cnt2 += 1
    ans2 += k
    k = k * k % m
if n <= cnt2:
    s = 0
    x = tmp
    for i in range(n):
        s += x
        x = x * x % m
    print(s)
else:
    n -= cnt2
    s = (s - ans2) * (n // (cnt - cnt2))
    for i in range(n % (cnt - cnt2)):
        s += x
        x = x * x % m
    print(s + ans2)

Solution (Python):
def main():
    n, x, m = map(int, input().split())
    a = x
    a_dict = {a: 0}
    loop_s, loop_e = -1, -1
    res = a

    for _ in range(n-1):
        a = a * a
        a %= m
        if a in a_dict:
            loop_s = a_dict[a]
            loop_e = len(a_dict)
            break
        else:
            a_dict[a] = len(a_dict)
            res += a

    if loop_s != -1:
        a_loop = list(a_dict.keys())[loop_s:]
        l_size = len(a_loop)
        r_size = n - len(a_dict)
        res += (r_size // l_size) * sum(a_loop) + sum(a_loop[:r_size%l_size])

    print(res)
        



if __name__ == "__main__":
    main()

Solution (Python):
import sys
N, X, M = map(int, input().split())
if N == 1:
  print(X)
  sys.exit()

ans = 0
ans += X - (X%M)
X %= M

def fun(x):
  return (x * x) % M

appear_list = [X]
appear_set = {X}

x = X
i_0 = 1
sum_0 = x

while fun(x) not in appear_set:
  x = fun(x)
  appear_list.append(x)
  appear_set.add(x)
  sum_0 += x
  i_0 += 1
  
  
  if i_0 == N:
    print(ans + sum_0)
    sys.exit()

ans += sum_0
N -= i_0

x = fun(x)
appear_set_2 = {x}
sum_1 = x
sum_list = [0,x]
i_1 = 1
while fun(x) not in appear_set_2:
  x = fun(x)
  appear_set_2.add(x)
  sum_1 += x
  sum_list.append(sum_1)
  i_1 += 1
  
sum_0 -= sum_1
i_0 -= i_1


ans += sum_1 * (N // i_1) + sum_list[(N % i_1)]

print(ans)

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

s = 0
mt = []
def f(x):
    return x**2 % M
i = 0
while True:
    i += 1
    mt.append(X)
    a = f(X)
    if i == N:
        f = 1
        break
    elif a in mt:
        f = 0
        break
    else:
        X = a

if f == 1:
    print(sum(mt))
else:
    e = mt.index(a)
    s1 = mt[:e]
    s2 = mt[e:]
    l = i - e
    c, d = divmod(N - e, l)
    print(sum(s1) + sum(s2) * c + sum(s2[:d]))

Solution (Python):
N,X,M=map(int,input().split())
ans=[X]
flag=0
for n in range(N):
    a=ans[-1]**2%M
    if a in ans:
        num=n
        flag=1
        break
    ans.append(a)
if flag==0:
    print(sum(ans[:-1]))
else:
    first = ans.index(a)
    if num==first:
        answer=sum(ans[:-1])+a*(N-num)
        print(answer)
    else:

        nums = ans[first:]
        rest = N - num
        answer = sum(ans)
        kaisuu = rest // (num - first + 1)
        answer += sum(nums) * kaisuu
        nokori = rest - kaisuu * (num - first + 1)
        answer += sum(nums[:nokori - 1])
        print(answer)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, X, M = map(int, readline().split())
    L = [X]
    A = X
    
    used = [-1] * M
    used[X] = 0
    i = 1
    while True:
        i += 1
        A = A * A % M
        if used[A] == -1:
            used[A] = i
            L.append(A)
        else:
            i
            break
    i2 = L.index(A) + 1
    l = len(L)
    if l >= N:
        ans = sum(L[:N])
    else:
        ans = sum(L)
        ans += sum(L[i2 - 1:]) * ((N - l) // (i - i2))
        ans += sum(L[i2 - 1:i2 - 1 + ((N - l) % (i - i2))])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N, X, M = map(int, input().split())
A = [X]
S = set()

for i in range(3 * 10 ** 6):
    nx = (A[-1]** 2) % M
    if nx in S:
        break
    S.add(nx)
    A.append(nx)

L = []
R = []
for i, a in enumerate(A):
    if a != nx:
        L.append(a)
    else:
        R = A[i:]
        break

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

RS = sum(R)
ans += RS * (N // len(R))
if R:
    for i in range(N % len(R)):
        ans += R[i]

print(ans)

Solution (Python):
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

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

sumA=[0]
res=0
MOD=[0]*(10**5+10)
x=X
A,B=[],[]
for i in range(1,N+1):
    if MOD[x]==1:
        point=x
        B=[]
        res=0
        while 1:
            res+=x
            B.append(res)
            x=(x*x)%M
            if x==point:
                break
    else:
        MOD[x]=1
        res+=x
        A.append(res)
        x=(x*x)%M        
    if B:
        break
if not B:
    print(A[-1])
else:
    C=[0]+B
    N-=len(A)
    print(A[-1]+B[-1]*(N//len(B))+(C[N%len(B)]))

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

visited = [-1] * (M + 1)
x = X
i = 0
while visited[x] == -1 :
  visited[x] = i
  x = x * x % M
  i += 1

loop_l = i - visited[x]
loop_s = x

ret = 0
x = X
while x != loop_s :
  ret += x
  x = x * x % M
  N -= 1
  if N == 0 : break
    
if N > 0 :
  i = 0
  while i != loop_l :
    ret += x * ((N - i + loop_l - 1) // loop_l)
    x = x * x % M
    i += 1
  
print(ret)

Solution (Python):
n, x, m = map(int, input().split())
s = 0
R = [-1]*m
R[x] = 0
T = [x]
for i in range(1, m+1):
    x = (x**2)%m
    T.append(x)
    if R[x] != -1:
        r = R[x]
        q = i-R[x]
        break
    else:
        R[x] = i




c = 0
for i in range(q):
    c += T[r+1+i]

X = [-1]*m
for i, e in enumerate(R):
    if e == -1:
        continue
    else:
        X[e] = i

n -= 1
if n <= r:
    ans = 0
    for i in range(n+1):
        ans += X[i]
else:
    ans = 0
    for i in range(r+1):
        ans += X[i]
    n -= r
    s, t = divmod(n, q)
    for i in range(t):
        ans += T[r+1+i]
    ans += c*s
print(ans)

Solution (Python):
N, X, M = map(int,input().split())
ans = X
lst = [X]
check = [0] * M
check[X] += 1
A = X
flag = False
for i in range(N-1):
    A = A**2 % M
    if check[A] == 0:
        check[A] += 1
        lst.append(A)
        ans += A
    else:
        flag = True
        init = lst.index(A)
        last = i+1
        break
if flag:
    new_list = lst[init:]
    l = len(new_list)
    s = sum(new_list)
    num = N - last
    ans += s * (num//l)
    for i in range(num%l):
        ans += new_list[i]

print(ans)

Solution (Python):
N, X, M = [int(_) for _ in input().split()]
seen = {}
i = 0
A = []
while True:
    if X in seen:
        i2 = seen[X]
        i3 = i
        break
    seen[X] = i
    A += [X]
    i += 1
    X = X**2 % M
if N < i3:
    ans = sum(A[:N])
elif i2 == i3:
    ans = sum(A[:i2]) + A[i2] * (N - i2)
else:
    q, r = divmod(N - i2, i3 - i2)
    ans = sum(A[:i2]) + sum(A[i2:]) * q + sum(A[i2:i2 + r])
print(ans)

Solution (Python):


import os,sys
from io import BytesIO, IOBase

def main():
    n,x,m = map(int,input().split())
    val,se = [x],{x}
    y = pow(x,2,m)
    while len(val) != n and y not in se:
        val.append(y)
        se.add(y)
        y = pow(y,2,m)
    if len(val) == n:
        print(sum(val))
    else:
        ans = sum(val)
        n -= len(val)
        ind = 0
        for i in range(len(val)):
            if val[i] == y:
                ind = i
                break
        val = val[ind:]
        xxx = sum(val)
        ans += xxx*(n//len(val))
        ans += sum(val[:n%len(val)])
        print(ans)
    

BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

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

loop_start = pos[cur]
ans = None
if N <= len(path):
    ans = sum(path[:N])
else:
    ans = sum(path)
    left = N - len(path)
    q, r = divmod(left, len(path) - loop_start)
    ans += q * sum(path[loop_start:]) + sum(path[loop_start:loop_start + r])
print(ans)

Solution (Python):
n,x,m = map(int,input().split())
exist = [0] * (m+1)
ans = 0
imamade = []
cnt = 0
for i in range(1,n+1):
    if exist[x] == 1:
        break
    else:
        ans += x
        exist[x] = 1
        imamade.append(x)
        x *= x
        x %= m
        cnt += 1
    if i == n:
        print(ans)
        exit()
num = imamade.index(x)
print(sum(imamade[:num]) + sum(imamade[num:]) * ((n-num) // (cnt-num)) + sum(imamade[num:num+((n-num) % (cnt-num))]))