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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from sys import exit

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353





N, X, M = getNM()

lista = [[-1, -1] for i in range(M)]

n = X
for i in range(2 * M + 1):
    if lista[n][0] == -1:
        lista[n][0] = i
    elif lista[n][1] == -1:
        lista[n][1] = i
    n *= n
    n %= M

cnt = 0
for i in range(M):
    s, e = lista[i]
    
    if s >= 0 and e >= 0:
        cnt += i * (((N - 1) - s) // (e - s) + 1)
    
    elif s >= 0:
        cnt += i
print(cnt)

Solution (Python):
n,x,m=map(int,input().split())
a=[]
mod_check_list = [False for _ in range(m)]
a.append(x*x%m)
ind=0
s=0
for i in range(m):
    t=a[i]*a[i]%m
    if mod_check_list[t]:
        ind=a.index(t)
        break
    mod_check_list[t] = True
    a.append(t)
s=sum(a[ind:])
l=len(a)-ind
loop_times = (n-1-ind)//l
answer=loop_times*s
for i in range((n-1-ind)%l):
    answer+=a[i+ind]
print(answer+x+sum(a[:ind]))

Solution (Python):
"""
何回足されるかで考えればよい。
真っ二つに切っていく。

各項は必ずM未満。
M項以内に必ずループが現れる。
"""
N,X,M = map(int,input().split())
memo1 = set()
memo2 = []
ans = 0
a = X
flag = True
rest = N
while rest > 0:
    if a in memo1 and flag:
        flag = False
        for i in range(len(memo2)):
            if memo2[i] == a:
                loopStart = i
        setSum = 0
        for i in range(loopStart,len(memo2)):
            setSum += memo2[i]**2 % M
        loopStep = len(memo2)-loopStart
        loopCount = rest // loopStep
        ans += loopCount*setSum
        rest -= loopCount*loopStep
    else:
        memo1.add(a)
        memo2.append(a)
        ans += a
        a = a**2%M
        rest -= 1

print(ans)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy


def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)
class ModInt:
    def __init__(self, x, MOD=1000000007): self.x, self.MOD = x % MOD, MOD
    def __str__(self): return str(self.x)
    def __add__(self, other): return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)
    def __sub__(self, other): return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)
    def __mul__(self, other): return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)
    def __truediv__(self, other): return ModInt(self.x * other.inverse()) if isinstance(other, ModInt) else ModInt(self.x * pow(other, self.MOD - 2, self.MOD))
    def __pow__(self, other): return ModInt(pow(self.x, other.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, self.MOD))
    def __rsub__(self, other): return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)
    def __rtruediv__(self, other): return ModInt(other.x * other.inverse()) if isinstance(other, ModInt) else ModInt(other * pow(self.x, self.MOD - 2, self.MOD))
    def __rpow__(self, other): return ModInt(pow(other.x, self.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, self.MOD))
    __repr__, __radd__, __rmul__ = __str__, __add__, __mul__
    def inverse(self): return pow(self.x, self.MOD - 2, self.MOD)

def main():
    N, X, M = LI()
    tmp = X
    s = set()
    while True:
        if tmp in s: break
        s.add(tmp)
        tmp = (tmp * tmp) % M

    f = len(s)
    s = set()

    while True:
        if tmp in s: break
        s.add(tmp)
        tmp = (tmp * tmp) % M

    mid = len(s)
    summid = sum(s)
    rest = (N - f + mid) % mid
    cnt = (N - f + mid) // mid

    first = f - mid
    tmp = X
    s = set()
    for _ in range(first):
        s.add(tmp)
        tmp = (tmp * tmp) % M
    first_res = sum(s)

    s = set()
    for _ in range(rest):
        s.add(tmp)
        tmp = (tmp * tmp) % M
    last_res = sum(s)

    print(first_res+ summid*cnt+ last_res)




if __name__ == '__main__':
    main()

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

count = 0










is_used = [0] * (m + 1)

count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    
    an = pow(pre_an, 2, m)
    if is_used[an] == 1:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    is_used[an] = 1
    count = count + an
    pre_an = an

print(count)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools
def main():
    N, X, M = MI()
    circle = [X]
    ans = 0
    i = 1
    num_list = [0] * (M + 1)
    a = X
    while num_list[a] == 0:
        num_list[a] = i
        a = pow(a, 2, M)
        circle.append(a)
        i += 1
    b = num_list[a]
    del circle[-1]
    sta = circle[:b - 1]
    v = len(sta)
    w = sum(sta)
    circle = circle[b - 1:]
    x = len(circle)
    y = sum(circle)
    if N <= v:
        ans = sum(sta[:N + 1])
        print(ans)
        exit()
    else:
        ans = w
        p, q = divmod(N - v, x)
        ans += y * p
        if q != 0:
            for i in range(q):
                ans += circle[i]

        print(ans)
if __name__ == "__main__":
    main()

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

ans = 0
flag = [0]*(10**5 + 2)
lst = [X]

for i in range(N):
    X = (X**2)%M

    if flag[X] == 1:
        break

    flag[X] = 1
    lst.append(X)

preindex = lst.index(X)

preloop = lst[:preindex]
loop = lst[preindex:]

loopnum = (N - len(preloop))//len(loop)
loopafternum = (N - len(preloop))%len(loop)

ans = sum(preloop) + sum(loop)*loopnum + sum(loop[:loopafternum])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)


def li():
    return [int(x) for x in input().split()]


N, X, MOD = li()


n = X
nums = [X]
loop_start_i = -INF
for i in range(1, N):
    n = pow(n, 2, MOD)
    if n in nums:
        loop_start_i = nums.index(n)
        break
    nums.append(n)

loop_length = len(nums) - loop_start_i
loop_cnt = (N - loop_start_i) // loop_length
r = (N - loop_start_i) % loop_length
sum_per_loop = sum(nums[loop_start_i:])
ans = sum(nums[:loop_start_i]) + sum_per_loop * loop_cnt + sum(nums[loop_start_i:loop_start_i+r])
print(ans)

Solution (Python):

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

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

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

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

print(ans)

Solution (Python):
n, x, m = map(int, input().split())
ans = 0
prev_set = set()
prev_list = list()
ans_hist = list()
r = x

for i in range(n):
    if i == 0:
        pass
    else:
        r = (r * r) % m
    
    if r == 0:
        break
    
    if r in prev_set:
        index = prev_list.index(r)
        period = i - index
        count = (n - index) // period
        rest = (n - index) % period

        ans = sum(prev_list[:index])
        ans += sum(prev_list[index:i]) * count
        

        ans += sum(prev_list[index:index+rest])
        
        break
    else:
        ans += r
        prev_set.add(r)
        prev_list.append(r)
        ans_hist.append(ans)
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))


 
def floor(a,b):
    return a//b

N,X,M = LI()


used = [-1]*M
end_index = -1
A = [X]
sum_ = 0
for i in range(N):
    if i == 0:
        sum_ += A[0]
    else:
        val = pow(A[i-1],2,M)
        A.append(val)
        if used[val] == -1:
            used[val] = i
            sum_ += val
        else:
            end_index = i
            start_val = val
            start_index = used[val]
            break

if end_index == -1:
    print(sum_)
    exit()
else:
    ans = sum_



n = floor(N-start_index,end_index-start_index)
sum_ = 0
A2 = [start_val]
for j in range(end_index-start_index):
    if j == 0:
        val2 = start_val
        sum_ += val2
    else:
        val2 = pow(A2[j-1],2,M)
        A2.append(val2)
        sum_ += val2

ans += (n-1)*sum_



sum_ = 0
A2 = [start_val]
for j in range(N-n*end_index+(n-1)*start_index):
    if j == 0:
        val2 = start_val
        sum_ += val2
    else:
        val2 = pow(A2[j-1],2,M)
        A2.append(val2)
        sum_ += val2

ans += sum_

print(ans)

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

for i in range(1, m + 1):
    x = pow(x, 2, m)
    if loop_list[x] != 1:
        loop_list[x] = 1
        order_list.append(x)
    else:
        break

index = order_list.index(x)
time = (n - index) // (len(order_list) - index)
mod = (n - index) % (len(order_list) - index)

ans += sum(order_list[:index])
ans += sum(order_list[index:]) * time
ans += sum(order_list[index:index + mod])

print(ans)

Solution (Python):
N, X, M = map(int, input().split())
A = [[0] * (10**5+1) for _ in range(34)]
B = [[0] * (10**5+1) for _ in range(34)]

for i in range(10**5+1):
    A[0][i] = B[0][i] = i**2 % M
for i in range(33):
    for j in range(10**5+1):
        A[i+1][j] = A[i][A[i][j]]
        B[i+1][j] += B[i][j] + B[i][A[i][j]]
now = X
ans = X
i = 0
N -= 1
while N > 0:
    if N & 1:
        ans += B[i][now] 
        now = A[i][now]
    N >>= 1
    i += 1
print(ans)

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):
def f(x, m):
    return (x**2) % m

N, X, M = map(int, input().split())
A = [X]
S = {X}
while True:
    X = f(X, M)
    if X in S:
        break
    else:
        A.append(X)
        S.add(X)


start = A.index(X)
l = len(A) - start
ans = sum(A[:start])
N -= start

ans += sum(A[start:]) * (N//l)
N %= l

ans += sum(A[start:start+N])
print(ans)

Solution (Python):
import sys
import math


def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,X,M = MI()

if M == 1:
    print(0)
    exit()

flag = [-1]*M
Z = [X]
flag[X] = 1
r = X
for i in range(2,M+2):
    r = r ** 2
    r %= M
    if flag[r] != -1:
        a,b = flag[r],i  
        break
    else:
        flag[r] = i
        Z.append(r)

z = len(Z)
ans = 0

for i in range(a-1):
    ans += Z[i]
    
n = N-a+1
q = n//(b-a)
r = n % (b-a)

for i in range(a-1,a+r-1):
    ans += (q+1)*Z[i]
for i in range(a+r-1,b-1):
    ans += q*Z[i]

print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

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

    A = []
    seen = set()
    tmp = X
    head_idx = -1
    while True:
        A.append(tmp)
        seen.add(tmp)
        tmp = pow(tmp, 2, M)
        if tmp in seen:
            head_idx = A.index(tmp)
            break
    

    cnt = [0] * len(A)
    for i in range(len(A)):
        if i < head_idx:
            if i <= N:
                cnt[i] = 1
        else:
            l = len(A) - head_idx
            cnt[i] = (N - head_idx) // l
    for i in range(head_idx, head_idx + (N - head_idx) % l):
        cnt[i] += 1
    

    ans = sum([a * c for a, c in zip(A, cnt)])
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


n,x,m=map(int,input().split())
s=[x]
g=set()
cnt=0
l=-1
g.add(x)
b=x
for i in range(1,n):
    nt=pow(b,2,m)
    b=nt
    if nt not in g:
        s.append(nt)
        g.add(nt)
    else:
        cnt=i
        l=nt
        break
if l==0:
    
    ans=sum(s)
elif l==1:
    
    ans=n-cnt+sum(s)
else:
    if l!=-1:
      idx=s.index(l)
      c=len(s)-idx
      r=(n-cnt)%c
      ans=((n-cnt)//c)*sum(s[idx:])+sum(s[idx:idx+r])+sum(s)
    else:
      ans=sum(s)
print(ans)

Solution (Python):
N, X, M = map(int, input().split())
A = [0]*(M+1)
A[0] = X
ls, rs = 0, 0
m = [-1]*(M+1)
m[X] = 0
for i in range(1, M+1):
    A[i] = (A[i-1]*A[i-1]) % M
    if m[A[i]] >= 0:
        ls = m[A[i]]
        rs = i
        break
    m[A[i]] = i

if rs == 0:
    print(sum(A[:N]))
else:
    if ls > N:
        print(sum(A[:N]))
    else:
        ans = sum(A[:ls])
        N -= ls
        w = rs-ls
        ans += sum(A[ls:rs])*(N//w)
        ans += sum(A[ls:ls+N % w])
        print(ans)

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

amari = [0]*m
v = [x]

cnt = 0
while True:
    xn_1 = x**2%m
    cnt += 1
    if x == 0:
        break
    amari[x] = xn_1
    if amari[xn_1]:
        break
    v.append(xn_1)
    x = xn_1



if 0 in v:
    ans = sum(v)
else:
    ind = v.index(xn_1)
    rooplen = len(v) - ind
    ans = sum(v[0:ind])
    l = n-ind
    if rooplen:
        ans += (l//rooplen)*sum(v[ind:])
        nokori = l - rooplen*(l//rooplen)
        ans += sum(v[ind:ind+nokori])
    

print(ans)

Solution (Python):


import sys
input=sys.stdin.readline

n,x,m=map(int,input().split())
values=[]
s=set()
loop_start=-1
for i in range(n):
    if x in s:
        loop_start=values.index(x)
        break
    values.append(x)
    s.add(x)
    x=(x*x)%m
if loop_start==-1:
    ans=sum(values)
    print(ans)
    exit()
else:
    ans=sum(values[:loop_start])
    loops=values[loop_start:]
    loops_sum=sum(loops)
    n-=loop_start
    l=len(loops)
    ans+=n//l*loops_sum+sum(loops[:n%l])
    print(ans)

Solution (Python):



from math import gcd
from itertools import combinations,permutations,accumulate, product 

from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq














import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7


INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n,x,m = readInts()
lis = []
prv = None
dic = defaultdict(int)
for i in range(m):
    if i == 0:
        A = x%m
        lis.append(A)
        dic[A] = 1
    else:
        A = (A*A)%m
        if dic[A]:
            prv = A
            break
        else:
            dic[A] = 1
        lis.append(A)
cnt = None
for i in range(len(lis)):
    if lis[i] == prv:
        cnt = i
        break
if cnt == None:
    cnt = len(lis)
front_arr = lis[:cnt]
loop_arr = lis[cnt:]
if x == 0:
    print(0)
    exit()
len_loop_arr = len(loop_arr)
if n < cnt:
    ans = sum(front_arr[:n])
else:
    ans = sum(front_arr)
    sum_loop_arr = sum(loop_arr)
    n -= cnt

    loop = n//len_loop_arr
    rest = n - (loop*len_loop_arr)
    mid = loop * sum_loop_arr
    ans += mid
    ans += sum(loop_arr[:rest])
print(ans)

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

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

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

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

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

ans = sum(num)
if flag:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)

Solution (Python):
import sys
n, x, m = map(int, input().split())
mod_cnt = [False for _ in range(m)]
mod_cnt[x] = True
cycle = [x]
while len(cycle) < n and not mod_cnt[(x*x) % m]:
	x = (x*x) % m
	mod_cnt[x] = True
	cycle.append(x)

if len(cycle) == n:
	print(sum(cycle))
	sys.exit()

nxt = (x*x) % m
for i in range(len(cycle)):
	if cycle[i] == nxt:
		head = i
		break

ans = sum(cycle[:head])
cycle = cycle[head:]
period = len(cycle)
n -= head
for i, x in enumerate(cycle):
	if i < n % period:
		ans += (n // period + 1) * x
	else:
		ans += (n // period) * x
print(ans)

Solution (Python):
n, x, m = map(int,input().split())
lst = [0 for i in range(m)]
lst2 = [x]
i = 2
lst[x] = 1
c = 0
while True:
    if (i > n):
        break
    x = x**2%m
    if (lst[x] == 0):
        lst[x] = i
        lst2.append(lst2[i - 2] + x)
        i = i + 1
    else:
        lst2.append(lst2[i - 2] + x)
        c = 1
        break
if (c == 1):
    a = i - lst[x]
    b = lst2[i - 1] - lst2[i - 1 - a]

    c = (n - i)//a
    d = (n - i)%a
    ans = lst2[i - 1] + b*c + lst2[i - 1 - a + d] - lst2[i - 1 - a]
    print(ans)

else:
    print(lst2[n - 1])

Solution (Python):
N,X,M = map(int,input().split())
ls = [X]
for i in range(M):
    Ai = ls[-1]**2 % M
    if Ai in ls:
        loop = ls[ls.index(Ai):]
        lenloop = len(loop)
        sumloop = sum(loop)
        startls = ls[:ls.index(Ai)]
        break
    ls.append(Ai)
if N <= len(startls):
    ans = sum(startls[:N])
else:
    ans = sum(startls) + ((N-len(startls))//lenloop)*sumloop + sum(loop[:(N-len(startls))%lenloop])
print(ans)

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

v = list(range(m))
p = [-1 for _ in range(m)]

a = x
p[a - 1] = 0
s = [x]
l, r = n, n
for i in range(n):
    a = a ** 2 % m
    if p[a - 1] >= 0:
        l, r = p[a - 1], i + 1
        break
    else:
        s.append(a)
        p[a - 1] = i + 1
ans = sum(s[:l])
if l != r:
    b = (n - 1 - i) // (r - l) + 1
    c = (n - 1 - i) % (r - l)
    ans += b * sum(s[l:r]) + sum(s[l:l + c])
print(ans)

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

lst_sum = [0,x]
loop = [0]*(10**5)
loop[x] = 1
s = 1
for i in range(2,n+1):
  y = ((lst_sum[-1] - lst_sum[-2])**2)%m
                          
  if loop[y] != 0:
    l = i-loop[y]
    d = (n-loop[y]+1) // l
    q = (n-loop[y]+1) % l
    sum_loop = lst_sum[-1]-lst_sum[loop[y]-1]
    sum_first = lst_sum[loop[y]-1]
    if q == 0:
      sum_rest = 0
    else:
      sum_rest = lst_sum[loop[y] + q-1] - lst_sum[loop[y]-1]
    print(sum_first+d*sum_loop+sum_rest)
    sys.exit()      
  else:
    s += 1
    loop[y] = s
    lst_sum.append(lst_sum[-1] + y)
    
print(lst_sum[-1])

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, x, m = map(int, input().split())
    ans = 0

    
    index = [-1] * m
    now = x
    i = 0
    while index[now] == -1:
        index[now] = i
        i += 1
        ans += now
        now = now * now % m
        n -= 1
        if n == 0:
            print(ans)
            return

    l = i - index[now]
    cycle = 0
    for _ in range(l):
        cycle += now
        now = now * now % m

    q, r = divmod(n, l)
    ans += q * cycle

    for _ in range(r):
        ans += now
        now = now * now % m

    print(ans)
resolve()

Solution (Python):
n, x, m = map(int, input().split())
amr = []
for i in range(n):
    if i == 0:
        x %= m
        amr.append(x)
        continue
    x = pow(x, 2, m)

    if x in amr:
        break
    if x == 0:
        break
    amr.append(x)

if x == 0:
    print(sum(amr[:n]))
else:
    idx = amr.index(x)

    loop = sum(amr[idx:])
    l = len(amr[idx:])

    if n >= idx:
        cnt = (n-idx)//l
        print(cnt*loop + sum(amr[:idx]) + sum(amr[idx:idx+n-idx-cnt*l:]))
    else:
        print(sum(amr[:n]))

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

count = X
bef = X
_sum = [bef]
dic = {}

for i in range(1, N):
    bef = pow(bef, 2, M)
    if bef in dic:
        posi = dic[bef]
        l = len(_sum) - posi
        plus = sum(_sum[posi:])
        count += plus * ((N - i) // l)
        mod = ((N - i) % l)
        count += sum(_sum[posi:posi + mod])
        break
    else:
        dic.setdefault(bef, i)
        _sum.append(bef)
    count += bef

print(count)

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

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


index = A.index(X)


loop_bef = A[0:index]


loop = A[index:]


num_loop = (N - len(loop_bef)) // len(loop)
num_aft_loop = (N - len(loop_bef)) % len(loop)

ans = sum(loop_bef) + sum(loop)*num_loop + sum(loop[:num_aft_loop])

print(ans)

Solution (Python):
from collections import deque

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

A = [-1] * (10 ** 5)

i = 1
A[x] = i
sum = []
sum.append(0)
sum.append(x)
while i < n:
    i += 1
    x = (x * x) % m
    if A[x] != -1:
        break
    A[x] = i
    sum.append(sum[-1] + x)

if i == n:
    print(sum[n])
    exit()

pre_i = A[x]
dis = i - pre_i
cnt = (n + 1 - pre_i) // dis
div = (n + 1 - pre_i) % dis
ans = sum[pre_i - 1]
ans += (sum[i - 1] - sum[pre_i - 1]) * cnt
if div != 0:
    ans += sum[pre_i + div - 1] - sum[pre_i - 1]
print(ans)

Solution (Python):


n, x, m = map(int, input().split())
x_set = set()
x_list = []
for i in range(n):
    if x not in x_set:
        x_set.add(x)
        x_list.append(x)
    else:
        break
    x = x**2 % m
total = 0
start = n
for i in range(n):
    if x_list[i] == x:
        start = i
        break
    else:
        total += x_list[i]
if start != n:
    m = len(x_list) - start
    k = (n - start) // m
    total += k * sum(x_list[start:])
    for i in range(0, n - k * m - start):
        total += x_list[start + i]
print(total)

Solution (Python):
n, x, m = map(int, input().split())
A = [0, x]
d = {x:1}
for i in range(2, n+1):
    A.append(A[i-1]**2 % m)
    if A[i] in d:
        j = d[A[i]]
        q, r = divmod(n-j+1, i-j)
        print(sum(A[:j]) + q*sum(A[j:i]) + sum(A[j:j+r]))
        break
    else:
        d[A[i]] = i
else:
    print(sum(A))

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

pre = X
table[pre] = 0
seq = [pre]
cnt = 0
while True:
    cnt += 1
    A = pre**2%M
    if not table[A]:
        seq.append(A)
        table[A] = cnt
        pre = A
    else:
        f = table[A]
        s = cnt
        break
    
ans = 0
for i in range(f + (N-f)%(s-f)):
    ans += seq[i]
m = (N-f)//(s-f)
for i in range(f, s):
    ans += seq[i]*m

print(ans)

Solution (Python):
N, X, M = map(int,input().split())
ans = 0
ls = [X%M] + [-1]*(M+1)
ls_app = [0]*(M+1)

for i in range(N):
    a = ls[i]
    ls_app[a] = i
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls_app[ls[i+1]] != 0:
        b = ls[i+1]
        L = ls_app[b]
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)

Solution (Python):
n,x,m = map(int, input().split())
be = x % m
ans = be
memo = [[0,0] for i in range(m)]
am = [be]
memo[be-1] = [1,0]  
for i in range(n-1):
    be = be**2 % m
    if be == 0:
        break
    elif memo[be-1][0] == 1:
        kazu = memo[be-1][1]
        l = len(am) -  kazu
        syou = (n-i-1) // l
        amari = (n-i-1)%l
        sum = 0
        for k in range(kazu, len(am)):
            sum += am[k]
        ans = ans + syou*sum
        if amari > 0:
            for j in range(kazu,kazu + amari):
                ans += am[j]
        break
    else:
        ans += be
        am.append(be)
        memo[be-1][0] = 1
        memo[be-1][1] = len(am) -1
print(ans)

Solution (Python):
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*m
lis = [-1]*m
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        for j in range(lis[x],lis[x]+b):
            ans += l[j]
        break
    l[i] = x
    lis[x] = i
    ans += x
print(ans)

Solution (Python):
n, x, m = [int(x) for x in input().split()]
A = [x]
while len(A) < n:
    a = (A[-1] * A[-1]) % m
    if a not in A:
        A.append(a)
    else:
        i = A.index(a)
        loop_len = len(A) - i
        print(sum(A[:i]) + sum(A[i:]) * ((n - i) // loop_len) + sum(A[i:i + ((n - i) % loop_len)]))
        break
else:
    print(sum(A))

Solution (Python):
N, X, M = map(int,input().split())
ans = 0
ls = [X%M] + [-1]*(M+1)
ls_app = [0]*(M+1)

for i in range(N):
    a = ls[i]
    ls_app[a] = i
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls_app[ls[i+1]] != 0:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)

Solution (Python):


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

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

check = [False for _ in range(M)]
d = [X]
max_x = 0
for _ in range(1, N+1):
    X = f(X, M)
    if check[X]:
        break
    else:
        check[X] = True
    d.append(X)

idx = d.index(X)
ans = sum(d[:idx])
N -= idx
d = d[idx:]

sumd = sum(d)
ans += N//len(d) * sumd

ans += sum(d[:N%len(d)])

print(ans)

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

    else:
        t.append(temp)

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

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

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