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())
count=x
now=x
flag=-1
sled=[now]
for i in range(1,n):
     now=(now*now)%m
     if now==0:
         flag=0
         break
     if now in sled:
         start=sled.index(now)
         nokori=n-i
         flag=2
         break
     
     else:
         sled.append(now)
     count+=now
     #print(i,now,count)

if flag==2:
    #print(count)
    sled=sled[start:]
    roopnum=int(nokori/len(sled))
    amari=nokori%len(sled)
    
    one_roop=sum(sled)
    count+=one_roop*roopnum
    #print(count)
    for i in range(amari):
        count+=sled[i]
print(count)

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
p = [0 for i in range(m)]
p[x] = 1
k = x
ans = 0
ans += k
me = [k]
mem = [k]
fin = 0
for i in range(n-1):
    k = k**2%m
    if p[k] == 0:
        p[k] = i+2
        ans += k
        mem.append(k)
        me.append(ans)
    else:
        sp = k
        ss = i+2
        fin = 1
        break
if fin == 0:
    print(ans)
else:
    for i in range(m):
        if mem[i] == sp:
            spi = i+1
            break
    if spi == 1:
        ans0 = 0
    else:
        ans0 = me[spi-2]
    uu = ans - ans0
    ans0 += ((n-spi+1)//(ss-spi))*uu
    for i in range((n-spi+1)%(ss-spi)):
        ans0 += mem[spi+i-1]
    print(ans0)

Submission status: Accepted

Solution code:
# coding: utf-8
N,X,M = map(int,input().split())
INF = 10**10+1
flg = [INF for i in range(M)]
loop = INF
ruiseki = [X]
ans = 0

An = X

for i in range(1,N):
    flg[An] = i
    An = (An**2)%M
    
    ruiseki.append(ruiseki[-1] + An)
    
    if flg[An] != INF:
        k = flg[An]
        loop = i - flg[An] + 1
        loop_v = ruiseki[-1] - ruiseki[k-1]
        break


if N > loop:
    l = (N-k+1)%loop
    if k >=2:
        ans += ruiseki[k-2]
        if l != 0:
            ans += ruiseki[k+l-2] - ruiseki[k-2]
    else:
        if l != 0:
            ans += ruiseki[k+l-2]
    ans += ((N-k+1)//(loop))*loop_v

else :
    ans = ruiseki[-1]

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

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

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

    ans = x
    tmp = x

    tmp_list = [x]

    has_find = False

    for i in range(n-1):
        if tmp*tmp%m in tmp_list:
            before_index = tmp_list.index(tmp*tmp%m)
            loop_list = []
            for l in range(before_index, i+1):
                loop_list.append(tmp_list[l])
            has_find = True
            break
        tmp_list.append(tmp*tmp%m)
        tmp = tmp*tmp%m
        ans += tmp

    if not has_find:
        print(ans)
        exit()

    # print(i,before_index)
    # print(loop_list)

    if before_index == 0:
        ans = 0
    else:
        ans = x
    tmp = x
    for _ in range(before_index-1):
        tmp = tmp*tmp%m
        ans += tmp

    n -= before_index

    loop_sum = sum(loop_list)

    loop_num = n // len(loop_list)
    mod_num = n % len(loop_list)

    ans += loop_sum * loop_num

    for i in range(mod_num):
        ans += loop_list[i]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from collections import deque
#from heapq import heapify, heappop, heappush
#from bisect import insort
#from math import gcd
#mod = 10**9 + 7
#N = int(input())
N, X, M = map(int, input().split())
count = [(-1, 0) for _ in range(M)]
now = X
cnt = 0
ans = 0
roop = 0
roopsum = 0
while count[now][0] < 0 and cnt < N:
	cnt += 1
	ans += now
	count[now] = (cnt, ans)
	now = now*now%M
	#print(ans)
	if count[now][0] > 0 and cnt < N-1:
		start = count[now][0]
		end = cnt+1
		roop = end - start
		roopsum = ans+now - count[now][1]
#print(count)
#print(start, end)
#print(roop)

#print(roopsum)
if roop == 0:
	print(ans)
	exit()
ans += ((N-end+1)//roop)*roopsum
res = (N-end+1)%roop
for k in range(res):
	ans += now
	now = now*now%M
print(ans)

#A = list(map(int, input().split()))
#flag = True
#for k in range(N):
#ans = 0
#print(ans)
#print('Yes')
#print('No')

Submission status: Accepted

Solution code:
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))


def solve():
    N, X, M = it()
    if N == 1:
        return X % M
    value = defaultdict(int)
    history = defaultdict(int)
    cur = 0
    cnt = 0
    for i in range(N):
        if X in history:
            break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
    period = i - history[X]
    cur += (N - cnt) // period * (cur - value[X])
    for i in range((N - cnt) % period):
        cur += X
        X = X * X % M
    return cur

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

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

memo=[0 for i in range(M)]

A=[0 for i in range(100001)]
A[1]=X
memo[0]=1
memo[X]=1
b=0
s=1
for i in range(2,100001):
    A[i]=f(A[i-1]**2, M)
    if memo[A[i]]:
        memo[A[i]]=2
        b=A[i]
        s=i
        break
    else:
        memo[A[i]]=1

#周期突入前の部分を取得
mae=[]
m=0
while True:
    if A[m]==b and m!=0:
        break
    else:
        mae.append(A[m])
        m+=1
#print(mae)

#周期部分を取得
shuuki=A[len(mae):s]
if shuuki==[]:
    shuuki=[0]
#print(shuuki)

#print(b,s)


#周期数とあまりで答えを調整

ans=0
#1 周期に入る前におわるパターン
if N<=s-1:
    ans=sum(A[:N+1])
else:
    ans+=sum(mae)
    N-=len(mae)-1
    kai=N//len(shuuki)
    amari=N%len(shuuki)
    ans+=kai*sum(shuuki)
    ans+=sum(shuuki[:amari])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,X,M = map(int,input().split())
ans = 0
d = defaultdict(lambda:-1)
x = X%M
for n in range(M+100):
    if x in d:
        T = n-d[x]
        break
    else:
        d[x] = n
    x *= x
    x %= M
p = 0
y = x
for m in range(d[x],n):
    p += y
    y *= y
    y %= M

ans = 0
n = N
z = X%M
while n:
    ans += z
    n -= 1
    z *= z
    z %= M
    if z==x:
        ans += n//T*p
        n %= T
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n, x, m = map(int, input().split())
appear = [False] * m
r = [x]
appear[x] = True
a = x
i = 1
while True:
    a = (a * a) % m
    if appear[a]:
        if a == 0:
            print(sum(r))
            exit()
        # print(a)
        break
    else:
        appear[a] = True
        r.append(a)
        # if a == 10000:
        #     print(i, a)
        i += 1
        if i == n:
            print(sum(r))
            exit()
cycle_start_i = r.index(a)
cycle_len = len(r) - cycle_start_i
cycle_sum = sum(r[cycle_start_i:])
# print(r[:4]) [10, 100, 10000, 41000]
# print('aa,', cycle_start_i)
# print(cycle_len)
# print(r)
c = Counter(r)
# ans = sum(r) * (n // cycle_len) + sum(r[:(n % cycle_len)])
ans = sum(r[:cycle_start_i]) + cycle_sum * ((n - cycle_start_i) // cycle_len) + sum(r[:((n - cycle_start_i) % cycle_len)])
ans = sum(r[:cycle_start_i]) + cycle_sum * ((n - cycle_start_i) // cycle_len) + sum(r[cycle_start_i:cycle_start_i + ((n - cycle_start_i) % cycle_len)])
print(ans)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline

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

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

#sum(sa[:n%len(a)])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

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

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

# 結果出力
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

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

    N,X,M = LI()

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

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

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

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

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


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(cnt)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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


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


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



SUM3 = 0

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

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

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

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

Submission status: Accepted

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

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

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

        pow_x *= pow_x
        pow_x %= m
        idx += 1
    # x^{2^idx} = 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

repeat_size = i - i_repeat
repeat_interval = N - i_repeat

num_repeats = repeat_interval // repeat_size
num_red = repeat_interval % repeat_size


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

print(res)

Submission status: Accepted

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


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


# 処理内容
def main():
    N, X, M = map(int, input().split())

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
import decimal
import itertools
from collections import deque
from functools import reduce
import heapq
import copy
#import numpy as np
#n = int(input())
n, x, m = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))


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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

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

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


print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, X, M):
    mods = [-1 for i in range(M)]
    number = 1
    mods[X] = number
    An = X ** 2 % M
    while mods[An] == -1:
        number += 1
        mods[An] = number
        # print('aaa', An, mods[An],An ** 2 % M)
        An = An ** 2 % M
    # print(An, mods[An], max(mods))
    loop_num = max(mods) - (mods[An] - 1)
    tag = (N - (mods[An] - 1)) % loop_num
    ans = 0
    for i in range(M):
        # if mods[i] - 1 == tag:
        #     print(i)
        #     return
        if mods[i] == -1:
            continue
        elif mods[i] < mods[An]:
            ans += i
        else:
            x = N - (mods[An] - 1)
            if tag != 0 and mods[i] - mods[An] < tag:
                ans += i * (x // loop_num + 1) if x >= 0 else 0
            else:
                ans += i * (x // loop_num) if x >= 0 else 0
    print(ans)



if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, X, M = map(int, input().split())
    # A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    # AB = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, X, M)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    x = {}

    ruiseki = [0] * (M + 1)

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

repStartIndex = rList.index(repeatStart)

extraPart = rList[0:repStartIndex]
repPart = rList[repStartIndex:]
# print(extraPart, repPart)
extraLen = len(extraPart)
repLen = len(repPart)

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


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

Submission status: Accepted

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

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


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

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

print(S)

Submission status: Accepted

Solution code:
import sys

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

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

if __name__ == "__main__":
      solve()

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

print(e_sequence_sum())

Submission status: Accepted

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

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

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

if hazimari == -1:#ループするまでもなくnが小さかったとき
    print(sum(check))
    exit()

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

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

Submission status: Accepted

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


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

Submission status: Accepted

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

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

# print(mod)
# num = n // len(mod)
# if mod[-1] == 0:
#   ans = sum(mod)
# else:
#   ans = sum(mod) * num + sum(mod[:n % len(mod)])

# print(ans)
# print(mod)
# print(len(mod))
# print(app[i])

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

print(ans)

Submission status: Accepted

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

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

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

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

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

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


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

print(count)

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

#Solve
if __name__ == "__main__":
    solve()