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



Sample input:
6 2 1001


Sample output:
1369

Submission status: Accepted

Solution code:
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)

print(total_head + total_loop * loop_count + total_tail)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(n,x,m):  # fix inputs here
    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 a string (i.e. not a list or matrix)
    return sumarr 


def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    n,x,m = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    # grid = []
    # for _ in range(nrows):
    #     grid.append(list(map(int,input().split())))

    res = solve(n,x,m)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))]))

Submission status: Accepted

Solution code:
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)

# print(a)

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])
# print(ans)
rem = n - first[x] + 1
ans += cyc[-1] * (rem//len(cyc))
# print(ans)
if(rem%len(cyc) != 0):
    ans += cyc[rem%len(cyc) - 1]
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]
#print(A)
#print(i)
#print(j)
A=list(sorted(A.items(),key=lambda x:x[1]))
#print(A)
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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
  #print(appear_list, x, fun(x))
  #print(i_0, N, appear_set)
  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

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

print(ans)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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: 何回目で出てきたか
    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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)]))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
#print(R)
#print(r)
#print(q)

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# by the authority of GOD     author: manhar singh sachdev #

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)
    
#Fast IO Region
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))]))

Submission status: Accepted

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

s = set()
l = [x]
while x ** 2 % m not in s:
    v = x ** 2 % m
    s.add(v)
    l.append(v)
    x = v

idx = l.index(x ** 2 % m)
loop = len(l) - idx

if n < len(l):
    print(sum(l[:n]))
elif (n - idx) % loop == 0:
    print(sum(l[:idx]) + ((n - idx) // loop) * sum(l[idx:]))
else:
    print(sum(l[:idx]) + ((n - idx) // loop) * sum(l[idx:]) + sum(l[idx:idx+(n-idx)%loop]))

Submission status: Accepted

Solution code:
n, x, m = [int(e) for e in input().split()]

s = set()
l = []

a = x % m
total = a
for i in range(1, n):
    a = (a * a) % m
    if a == 0:
        break
    
    if a in s:
        r = n - i
        p = l.index(a)
        
        lo_total = 0
        for j in range(p, len(l)):
            lo_total += l[j]
        total += lo_total * (r // (len(l) - p))

        r %= (len(l) - p)        
        for j in range(p, p + r):
            total += l[j]
        break
    
    s.add(a)
    l.append(a)
    total += a

print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    # mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    
    n, x, m = mi()

    def check_loop(x, m):
        memo = dict()
        arr = [0] * m
        val = x
        memo[val] = 0
        arr[0] = val
        for i in range(1, m + 1):
            val = (val ** 2) % m
            if val in memo:
                return memo[val], i - memo[val], arr
            memo[val] = i
            arr[i] = val
        raise RuntimeError

    head_len, loop_len, arr = check_loop(x, m)
    # print(head_len)
    # print(loop_len)
    # print(arr)
    if n <= head_len:
        print(sum(arr[:n]))
    else:
        num_loop, res_len = divmod(n - head_len, loop_len)
        ans = sum(arr[:head_len])
        ans += num_loop * sum(arr[head_len:head_len+loop_len])
        ans += sum(arr[head_len:head_len+res_len])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = X
sum_A = A
A_list = [X]
for i in range(1, N):
    A = A ** 2 % M

    if (A in A_list):
        start = A_list.index(A)
        loop = A_list[start:]
        sum_A += sum(loop)*((N-i)//len(loop)) + sum(loop[:(N-i) % len(loop)])
        break
    else:
        A_list.append(A)
    sum_A += A

    if (A == 0):
        break

print(sum_A)

Submission status: Accepted

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

def next_f(a):
    return a * a % M

visited = [None] * M
sum_at_visit = [None] * M
loop_done = False

time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        # found cycle                                                                                                                                         
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)