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())

mn = min(n, m)
S = set()
A = []
a = x
sum_9 = 0 # sum of pre + cycle

for _ in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    sum_9 += a
    a = a*a % m
    if a == 0:
        print(sum_9)
        exit()

if len(A) >= mn:
    print(sum_9)
    exit()

st_len = A.index(a)
cyc_len = len(A) - st_len
ed_len = (n - st_len) % cyc_len

cyc_num = (n - st_len) // cyc_len

pre = sum(A[:st_len])
cyc = sum_9 - pre
btm = sum(A[st_len: st_len + ed_len])

print(pre + cyc * cyc_num + btm)

Submission status: Accepted

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

is_appear = [-1]*M
a = []
_len = 0
while is_appear[X] == -1:
    a.append(X)
    is_appear[X] = _len
    _len += 1
    X = X*X % M

loop_len = _len-is_appear[X]
loop_total = 0
for i in range(is_appear[X], _len):
    loop_total += a[i]

ans = 0
if N <= _len:
    for i in range(N):
        ans += a[i]
    
    print(ans)
else:
    for i in range(is_appear[X]):
        ans += a[i]
        N -= 1
    
    ans += loop_total * (N // loop_len)
    
    for i in range(N%loop_len):
        ans += a[is_appear[X]+i]
    
    print(ans)

Submission status: Accepted

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

mn = min(n, m)
S = set()
A = []
a = x
ans = 0

for i in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    ans += a
    a = a*a%m
    if a == 0:
        print(ans)
        exit()

if len(A) >= mn:
    print(ans)
    exit()

st_len = 0
while st_len < len(A) and a != A[st_len]: st_len += 1
st = sum(A[:st_len])
cyc_sum = sum(A[st_len:])
cyc_len = len(A) - st_len
cyc_num = (n - st_len) // cyc_len
cyc = cyc_sum * cyc_num
ed_len = (n - st_len) % cyc_len
ed = sum(A[st_len:][:ed_len])
print(st + cyc + ed)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
S = set()
A = []
a = x
ans = 0
for i in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    ans += a
    a = a*a%m
    if a == 0:
        print(ans)
        exit()

# print(S)
# print(A)
# print(len(A), n, m)
if len(A) < mn:
    st_len = 0
    while st_len < len(A) and a != A[st_len]: st_len += 1
    st = sum(A[:st_len])
    cyc_sum = sum(A[st_len:])
    cyc_len = len(A) - st_len
    cyc_num = (n - st_len) // cyc_len
    # print('m {} n {} st_len {} cyc_len {} cyc_num {}'.format(m,n,st_len,cyc_len,cyc_num))
    cyc = cyc_sum * cyc_num
    ed_len = (n - st_len) % cyc_len
    ed = sum(A[st_len:][:ed_len])
    print(st + cyc + ed)
else:
    print(ans)

Submission status: Accepted

Solution code:
from math import log2
n,x,m = map(int, input().split())

logn = int(log2(n))+1
db = [[0]*m for _ in range(logn)]
dbs = [[0]*m for _ in range(logn)]

for i in range(m):
    db[0][i] = (i**2)%m
    dbs[0][i] = (i**2)%m

for i in range(logn-1):
    for j in range(m):
        db[i+1][j] = db[i][db[i][j]]
        dbs[i+1][j] = dbs[i][db[i][j]] + dbs[i][j]


ans = x
now = x
for i in range(logn):
    if (n-1)&(1<<i) > 0:
        ans += dbs[i][now]
        now = db[i][now]

print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
if X <= 1:
    print(X*N)
    exit()
check = [0]*(M+1)
check[X] += 1
A = X
last_count = 0
while True:
    A = (A**2)%M
    if check[A] != 0:
        last_count = sum(check)
        target_value = A
        break
    check[A] += 1
A2 = X
first_count = 0
while A2 != target_value:
    first_count += 1
    A2 = (A2**2)%M

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3
if roop_count == 0:
    print(N*X)
    exit()
if first_count != 0:
    ans = X
    A = X
    for i in range(min(N,first_count)-1):
        A = (A**2)%M
        ans += A
else:
    ans = 0
if N > first_count:
    ans += ((N-first_count)//roop_count)*mass
    A4 = target_value
    if (N-first_count)%roop_count >= 1:
        ans += A4
    for i in range(((N-first_count)%roop_count)-1):
        A4 = (A4**2)%M
        ans += A4
print(ans)

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より大きい場合、超過分を先に計上する。
X %= M #これで 0 <= X <= M-1 が成り立つようにできた。

def fun(x): #問題の関数を用意（いちいち中身を書いていると面倒くさいため）
  return (x * x) % M

appear_set = {X} #すでに現れた数を格納する


i_0 = 1 #今までに調べた個数。現在は「X」の1つだけ。
x = X #このxに何度も関数funを作用させる
sum_0 = x #現在までの和

# ①：すでに出現したことのある数が現れるまで、ループを回す。
#  　この途中で目標回数Nに到達するなら、その時点で答えを出力する(31-33行目)。
while fun(x) not in appear_set: #次のxが初めて現れる数なら続ける。
  x = fun(x) #xにfunを作用
  appear_set.add(x) #xを「現れたものリスト」に格納
  sum_0 += x #和の更新
  i_0 += 1   #調べた個数の更新
  
  if i_0 == N: #目標回数に到達したら、その時点で答えを出力して終了。
    print(ans + sum_0)
    sys.exit()

# 現在、xには系列に初めて現れた最後の数が入っている。
# 次の数であるfun(x)は、前に現れたことのある数。したがって、ここからループが始まる。
# 整理のため、ここまでの和を計上し、残り回数も減らしておく。
ans += sum_0
N -= i_0

# ②：ループの性質を調べるため、もう一度ループを回したい。
#　欲しいものは3つ。
#   1.ループ１週の和
#   2.ループの途中までの和を記録した配列。
#   3.ループの長さ

#　以下、先ほどと異なる部分を中心に説明する。
x = fun(x) # 次の数へ行く(ループの最初の数)
appear_set_2 = {x} 
sum_1 = x        # 欲しいもの1。ループ１周の和を記録する。
sum_list = [0,x] # 欲しいもの2。i番目の要素がi番目までの数までの和を示すよう、この後要素を追加する。
i_1 = 1 # すでに調べた個数をカウントする。現在は「x」の1個だけ。
# このi_1が、最終的にループの長さ(欲しいもの3)になる。

# 以下、60行目以外の処理は先ほどと同様。
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_1, 途中までの和の記録sum_list, ループ長i_1）
#    を使って答えを求める。
ans += sum_1 * (N // i_1) + sum_list[(N % i_1)]

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, X, M = MI()
    S = list([X])
    num = X
    for i in range(N-1):
        num = (num**2) % M
        if not num in S:
            S.append(num)
        else:
            break

    len_s = len(S)
    if len_s == N:
        print(sum(S))
    else:
        index_s = S.index(num)
        #循環を開始する前までの個数
        num1 = index_s
        sum1 = sum(S[0:index_s])
        
        #循環後
        num2 = len_s - index_s
        sum2 = sum(S)-sum1
        
        #循環する個数
        num3 = (N-num1) // num2
        sum3 = sum2 * num3
        
        #あまり
        num4 = (N-num1) % num2
        sum4 = sum(S[index_s:index_s+num4])
        
        ans = sum1+sum3+sum4
        print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,x,mod=map(int,input().split())
d=[-1]*mod
ans=0
syu=0
al=[]
for i in range(n):
    if d[x]!=-1:
        en=i
        syu=i-d[x]    
        break
    ans+=x
    al.append(x)
    d[x]=i
    x=x*x%mod   
if syu==0:
    print(ans)
    exit()
ans+=((n-en)//syu)*sum(al[d[x]:en])
for i in range((n-en)%syu):
    ans+=x%mod
    x=x*x%mod
print(ans)

Submission status: Accepted

Solution code:
N,x,M=map(int,input().split())
k=x
L=list()
c=dict()
for i in range(M):
  if i==N:
    print(sum(L))
    exit()
  if x==0:
    print(sum(L))
    exit()
  L.append(x)
  x=(x*x)%M
  if x in c:
    q=x
    break
  c[x]=1
moto=sum(L)
N-=len(L)
for i in range(len(L)):
  if L[i]==q:
    roop=list(L[i:])
L=roop
a=len(L)
if N%a==0:
  print(moto+(sum(L)*(N//a)))
else:
  s=N//a
  t=N%a
  ans=sum(L)*s
  ans+=sum(roop[:t])
  print(moto+ans)

Submission status: Accepted

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

ans = 0
a = [0]
id = [0]*(m+1)
l = 1
while id[x] == 0:
    a.append(x)
    id[x] = l
    ans += x
    l += 1
    x = x**2 % m

c = l - id[x]
s=0

for i in range(id[x],l):
    s += a[i]

if n <= l-1:
    ans = 0
    for i in range(1,n+1):
        ans += a[i]
else:
    n -= l
    n += 1
    ans += s*(n//c)
    n %= c
    for i in range(n):
        ans += a[id[x] + i]
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, x, m = map(int, input().split())
    idx = [-1] * (m + 1)  # mで割った余り（0,1,...m-1）が何回目に出てきたか
    res = []  # 数列A

    for i in range(1, m + 3):  # 余りはm+1種類なのでm+2回計算すれば絶対ループが発生する
        if idx[x] == -1:  # 初めて
            idx[x] = i
            res.append(x)
            x = (x ** 2) % m
        else:  # 既出（ループ発見）
            len_loop = i - idx[x]
            len_head = idx[x] - 1
            break

    if n <= len_head + len_loop:  # 1ループ目までで出力する場合
        print(sum(res[:n]))
    else:
        ans = sum(res[:len_head])  # ループ前

        loop_count = (n - len_head) // len_loop
        ans += loop_count * sum(res[len_head:])  # ループ

        len_tail = (n - len_head) % len_loop
        ans += sum(res[len_head: len_head + len_tail])  # ループ後の余り

        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

N, X, M = map(int, sys.stdin.readline().split())

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

a = []
a.append(X)

exists = set()
exists.add(X)
ans = a[0]
for i in range(1, N):
    tmp = f(a[i-1], M)
    if tmp in exists:
        start = a.index(tmp)
        # print("start", start)
        break
    ans += tmp
    a.append(tmp)
    exists.add(tmp)
else:
    # ループ未満で終了する場合
    print(ans)
    sys.exit()

# print(a)
# print("ans", ans) 
 
before_score = sum(a[:start])
# print("before_score", before_score)

loop = a[start:]
# print(loop)
loop_score = sum(loop)
# print("loop_score", loop_score)
loop_n = len(loop)
N -= start
res_n = N % loop_n
print(before_score + loop_score * (N // loop_n) + sum(loop[:res_n]))

Submission status: Accepted

Solution code:
def main():
    n, x, m = map(int, input().split())
    idx = [-1] * (m + 1)  # mで割った余り（0,1,...m-1）が何回目に出てきたか
    res = []  # 数列A

    for i in range(1, m + 3):  # 余りはm+1種類なのでm+2回計算すれば絶対ループが発生する
        if idx[x] == -1:  # 初めて
            idx[x] = i
            res.append(x)
        else:  # 既出（ループ発見）
            len_loop = i - idx[x]
            len_head = idx[x] - 1
            break
        x = (x ** 2) % m

    if n <= len_head + len_loop:  # 1ループ目までで出力する場合
        print(sum(res[:n]))
    else:
        ans = sum(res[:len_head])  # ループ前
        ans += (n - len_head) // len_loop * sum(res[len_head:])  # ループ
        ans += sum(res[len_head: len_head + (n - len_head) %
                       len_loop])  # ループ後の余り
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
#from collections import deque
#from functools import *
#from fractions import Fraction as f
from copy import *
from bisect import *	
#from heapq import *
from math import gcd,ceil,sqrt
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1
mod=998244353



while t>0:
	t-=1
	n,k,m=mi()
	vis={}
	cycle=[]
	i=ans=0
	while k not in vis:
		cycle.append(k)
		vis[k]=i
		i+=1
		ans+=k
		if i==n:
			print(ans)
			exit(0)
		k=(k**2)%m
		if k in vis:
			cycle=cycle[vis[k]:]
			n-=i

	s=sum(cycle)
	p=n%len(cycle)
	z=len(cycle)
	print(ans+(n//z)*s+sum(cycle[:p]))

Submission status: Accepted

Solution code:
n, x, m = list(map(int, input().split()))
a = [x]
start = -1
end = -1
check = [0]*m
path = -1
loop = 0

for i in range(1, n):
    ans = (a[i-1]**2) % m
    p = check[ans]
    if p != 0:
        if start == -1:
            start = i
            path = ans
        if p == 1:
            end = i
    if p >= 3:
        break
    check[ans] += 1
    a.append(ans)


if start == -1 or end == -1:
    print(sum(a))
else:
    lenght = end-start+1
    loop, mod = divmod(n-start, lenght)
    ans = sum(a[:start])+sum(a[start:end+1])*loop + sum(a[start:start+mod])
    print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
N, X, M = map(int,input().split())
A = [0 for _ in range(M+1)]
A[1] = X
S = [0 if i == 0 else X for i in range(M+1)]
first = [-1 for i in range(M+1)]
if X <= M:
	first[X] = 1

n = 1
a = X
l,r = -1, -1
while True:
	if n == N:
		break
	a2 = (a*a) % M
	if a2 == 0:
		print(S[n])
		exit()
	if first[a2] > 0:
		l = first[a2]
		r = n
		break
	first[a2] = n + 1
	A[n+1] = a2
	S[n+1] = S[n] + a2
	a = a2
	n += 1

if n == N:
	print(S[N])
	exit()
t = r - l + 1
loop = (N-l+1) // t
rest = (N-l+1) % t
print(S[l-1] + loop * (S[r] - S[l-1]) + S[l + rest - 1] - S[l-1])

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)

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
id = [-1] * M
lis = []
tot = 0
le = 0
while id[X] == -1:
    id[X] = le
    le += 1
    lis.append(X)
    tot += X
    X = (X**2) % M

c = le - id[X]
sm = 0
for i in range(id[X],le):
    sm += lis[i]
if (N <= le):
    ans = 0
    for i in range(N):
        ans += lis[i]
    print(ans)
    exit()

ans = tot
N -= le
ans += N // c * sm
N %= c
for i in range(id[X],id[X]+N):
    ans += lis[i]
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
ans = x
L = [0 for i in range(m+1)]
L[x] = 1

A = [x]
t = True
count = 2
while t:
    x = (x*x)%m
    if L[x] != 0:
        start = L[x]
        t = False
    else:
        L[x] = count
        count += 1
        A.append(x)

if A[-1] == 0:
    if len(A) - 1 > n:
        ans = sum(A[:n])
    else:
        ans = sum(A)

elif len(A) >= n:
    ans = sum(A[:n])
else:
    length = len(A)-start+1
    ans = sum(A[:(start-1)])
    t = (n-start+1) // length 
    s = (n-start+1) % length
    ans += sum(A[(start-1):])*t 
    ans += sum(A[start-1:(start-1+s)])
print(ans)

Submission status: Accepted

Solution code:
N,X,M = [int(a) for a in input().split()]
amari = [0]*M
i = 1
A = X
amari[A] = i
l = [X]
ichi = i
while i<=M:
    i += 1
    A = A**2 % M
    if amari[A]: i += M
    else:
        amari[A] = i
        l.append(A)
    if i==N: i = M+1
else:
    if i>M+1: ni = i-M - amari[A]
    else: ni = 0
#for j in range(M):
#    if amari[j]: print(j, amari[j])
#print(i,len(l))
ichi = len(l) - ni
#print(l)
if ni:
    ni_times, san = divmod((N - ichi), ni)
    #print(ichi, '%d*%d'%(ni,ni_times), san)
    print(sum(l[:ichi]) + 
          sum(l[ichi:])*ni_times + 
          sum(l[ichi:ichi+san]))
else:
    #print(ichi, '%d*%d'%(ni,ni_times), san)
    print(sum(l))

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
tx = X % M
tl = []
ts = set()
ttl = []
for i in range(N):
    tl.append(tx)
    ts.add(tx)
    tx = pow(tx, 2, M)
    if tx in ts:
        ttl = tl[tl.index(tx):]
        break
ans = sum(tl)
if len(ttl)>0:
    d, m = divmod(N-len(tl), len(ttl))
    ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Submission status: Accepted

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

I = [-1] * M
A = []
total = 0
while (I[X] == -1):
    A.append(X)
    I[X] = len(A)
    total += X
    X = (X * X) % M

# print(f'{A=}')
# print(f'{I[:20]=}')
# print(f'{total=}')
# print(f'{X=}, {I[X]=}')

c = len(A) - I[X] + 1
s = sum(A[I[X] - 1:])
# print(f'{c=}, {s=}')
ans = 0
if N < len(A):
    ans += sum(A[:N])
else:
    ans += total
    N -= len(A)
    ans += s * (N // c)
    N %= c
    ans += sum(A[I[X] - 1:I[X] - 1 + N])
print(ans)

Submission status: Accepted

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

visited = [False] * M

tmp = X
total_sum = X
visited[tmp] = True

total_len = 1
while True:
    tmp = (tmp ** 2) % M
    if visited[tmp]:
        loop_start_num = tmp
        break
    total_sum += tmp
    visited[tmp] = True
    total_len += 1

path_len = 0
tmp = X
path_sum = 0

while True:
    if tmp == loop_start_num:
        break
    path_len += 1
    path_sum += tmp
    tmp = (tmp ** 2) % M

loop_len = total_len - path_len
loop_sum = total_sum - path_sum


result = 0
if N <= path_len:
    tmp = X
    for i in range(N):
        result += X
        tmp = (tmp ** 2) % M
    print(result)
else:
    result = path_sum
    N -= path_len
    loops_count = N // loop_len
    loop_rem = N % loop_len
    result += loop_sum * loops_count
    tmp = loop_start_num
    for i in range(loop_rem):
        result += tmp
        tmp = (tmp ** 2) % M
    print(result)

# print("loop_start_num", loop_start_num)
# print("path_sum", path_sum)
# print("loop_sum", loop_sum)

Submission status: Accepted

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

y=x
A=[]
A.append(y)
cnt=1
su=x

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)
        su+=y

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく


f=sum(A[c:c+(n-c)%d])
    #周期からはみでた最後の部分

g=su-e#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)

Submission status: Accepted

Solution code:
# -*- using utf8 -*-
import sys
inputlinevec = sys.stdin.readline().strip().split(' ')
n = int(inputlinevec[0])
x = int(inputlinevec[1])
m = int(inputlinevec[2])

sum_res = x
crcle_dict = dict()
crcle_list = list()
crcle_idx = 0
pre_a = x

for idx in range(1, n):
    #a范围在0-m之间，不会无限递增，因此很大概率会重复
    #a * a % m这种单变量的式子，一旦a出现了之前出现过的值
    #后续就会出现重复的序列，然后循环
    this_a = (pre_a * pre_a) % m
    pre_a = this_a
    
    if this_a not in crcle_dict:
        crcle_dict[this_a] = 1
        crcle_list.append(this_a)
        sum_res = sum_res + this_a
    else:
        crcle_step = len(crcle_list) - crcle_list.index(this_a)
        remain_crcle = int((n - idx) / crcle_step)
        remain_crcle_tail = int((n - idx) % crcle_step)
        
        crcle_sum = 0
        crcle_sum_tail = 0
        for a_item in crcle_list[crcle_list.index(this_a):]:
            crcle_sum = crcle_sum + a_item
            remain_crcle_tail = remain_crcle_tail - 1
            if remain_crcle_tail == 0:
                crcle_sum_tail = crcle_sum
        sum_res = sum_res + (remain_crcle * crcle_sum) + crcle_sum_tail
        break
    
print(sum_res)

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

    cur = 0
    cnt = 0
    value = defaultdict(int)
    history = defaultdict(int)
    for i in range(N):
        if X in history: break
        value[X] = cur
        history[X] = i
        cnt += 1
        cur += X
        X = X * X % M
        
    loop = cur - value[X]
    period = i - history[X]
    freq, rem = divmod(N - cnt, period)
    cur += freq * loop
    for i in range(rem):
        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())
r=[]
s=set()
ans=x
a=x
for i in range(n-1):
    b=a*a%m
    if b in s:
        j = r.index(b)
        N = n-1-i
        T = i-j
        S = sum(r[j:])
        ans += N//T*S
        N %= T
        ans += sum(r[j:j+N])
        break
    else:
        ans+=b
        s.add(b)
        r.append(b)
        a=b
print(ans)

Submission status: Accepted

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

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

nex = [(i ** 2) % M for i in range(M)]
cum = [i for i in range(M)]

ans = 0
while N:
  if N & 1:
    ans += cum[X]
    X = nex[X]
  cum = [cum[i] + cum[nex[i]] for i in range(M)]
  nex = [nex[nex[i]] for i in range(M)]
  N >>= 1

print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, X, M = map(int,input().split())
    past_a = {X}
    A = [X]
    ans = prev = X
    for i in range(1, min(M,N)):
        next_a = prev ** 2 % M
        if next_a in past_a:
            loop_start = A.index(next_a)
            loop_end = i
            loop_size = loop_end - loop_start
            loop_elem = A[loop_start:loop_end]

            rest_n = N-i
            ans += rest_n // loop_size * sum(loop_elem)
            ans += sum(loop_elem[:rest_n%loop_size])
            break

        ans += next_a
        past_a.add(next_a)
        A.append(next_a)
        prev = next_a
    
    print(ans)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

a = []
check = [-1] * m
i = 0
while check[x] == -1:
  a.append(x)
  check[x] = i
  x = x * x % m
  i += 1
if n <= i:
  print(sum(a[:n]))
else:
  print(
    sum(a[:check[x]])
    + (n - check[x]) // (i - check[x]) * sum(a[check[x]:])
    + sum(a[check[x] : check[x] + (n - check[x]) % (i - check[x])]))

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
flag = [False for _ in range(M)]
record = list()
record.append(X)
flag[X] = 1

An = X

for i in range(M + 1):
    An = pow(An, 2, M)
    if flag[An]:
        start = flag[An]
        cnt = i + 2 - start
        cost = record[-1] - record[start - 2] if start > 1 else record[-1]
        break

    else:
        record.append(An + record[-1])
        flag[An] = i + 2

if start >= N:
    print(record[N - 1])
else:
    print(((N - start) // cnt) * cost
                + record[(N - start) % cnt + start - 1])

Submission status: Accepted

Solution code:
N,X,M = map(int, input().split())
A = [X]
S = set(A)
cnt = 0
i = 0
for i in range(1, N):
    A.append(A[i-1] ** 2 % M)
    if A[i] in S:
        break
    else:
        S.add(A[i])
roup_cycle = i - A.index(A[i])
before_roup_sums = sum(A[:A.index(A[i])])
roup_sums = sum(A[A.index(A[i]):i])

if roup_cycle != 0:
    roup_amount = (N - A.index(A[i])) // roup_cycle
    roup_mod = (N - A.index(A[i])) % roup_cycle
    print(before_roup_sums + roup_sums * roup_amount + sum(A[A.index(A[i]):(A.index(A[i]) + roup_mod)]))
else:
    print(sum(A))

Submission status: Accepted

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

# https://en.wikipedia.org/wiki/Cycle_detection
def floyd_cycle_finding(f, x0):
    '''
    循環していない部分の長さをlam
    循環部分の長さをmuとして
    (lam, mu)
    を返す
    >>> floyd_cycle_finding(lambda x: x**2 % 3, 2)
    (1, 1)
    >>> floyd_cycle_finding(lambda x: x**2 % 1001, 2)
    (2, 4)
    >>> floyd_cycle_finding(lambda x: x**2 % 16, 2)
    (2, 1)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 3)
    (0, 4)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 0)
    (0, 1)
    '''
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    lam = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        lam += 1
    mu = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        mu += 1
    return lam, mu

def solve(N: int, X: int, M: int):
    f = lambda x: x**2 % M

    def g(x):
        while True:
            yield x
            x = f(x)
            
    lam, mu = floyd_cycle_finding(f, X)
    ans = 0
    gg = g(X)
    k = max((N - lam) // mu, 0)
    for i in range(min(N, lam)):
        ans += next(gg)
    for i in range(mu):
        ans += k * next(gg)
    for i in range(max((N-lam)%mu, 0)):
        ans += next(gg)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(solve(N, X, M))


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

# https://en.wikipedia.org/wiki/Cycle_detection
def floyd_cycle_finding(f, x0):
    '''
    循環していない部分の長さをlam
    循環部分の長さをmuとして
    (lam, mu)
    を返す
    >>> floyd_cycle_finding(lambda x: x**2 % 3, 2)
    (1, 1)
    >>> floyd_cycle_finding(lambda x: x**2 % 1001, 2)
    (2, 4)
    >>> floyd_cycle_finding(lambda x: x**2 % 16, 2)
    (2, 1)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 3)
    (0, 4)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 0)
    (0, 1)
    '''
    # a_i = a_j
    # の関係が成り立つ時
    # a_{lam+n+k*mu} = a_{lam+n+k'*mu}
    # より|i-j|は循環の長さの整数倍になる
    # そこで
    # a_m = a_2m
    # なるmを見つける
    # 前述の性質からmは循環の長さの整数倍となっているため
    # 2m - m = m = k*mu = lam + n + k'*mu
    # したがって、lam + nはmuの倍数となるので
    # 地点mからlamステップ進むと循環の開始点に到達する
    # lamが求まれば後は流れでmuも求まる
    
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    lam = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        lam += 1
    mu = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        mu += 1
    return lam, mu

def solve(N: int, X: int, M: int):
    f = lambda x: x**2 % M

    def g(x):
        while True:
            yield x
            x = f(x)
            
    lam, mu = floyd_cycle_finding(f, X)
    ans = 0
    gg = g(X)
    k = max((N - lam) // mu, 0)
    for i in range(min(N, lam)):
        ans += next(gg)
    for i in range(mu):
        ans += k * next(gg)
    for i in range(max((N-lam)%mu, 0)):
        ans += next(gg)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(solve(N, X, M))


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Submission status: Accepted

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

# https://en.wikipedia.org/wiki/Cycle_detection
def floyd_cycle_finding(f, x0):
    '''
    循環していない部分の長さをlam
    循環部分の長さをmuとして
    (lam, mu)
    を返す
    >>> floyd_cycle_finding(lambda x: x**2 % 3, 2)
    (1, 1)
    >>> floyd_cycle_finding(lambda x: x**2 % 1001, 2)
    (2, 4)
    >>> floyd_cycle_finding(lambda x: x**2 % 16, 2)
    (2, 1)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 3)
    (0, 4)
    >>> floyd_cycle_finding(lambda x: x*2 % 5, 0)
    (0, 1)
    '''
    # a_i = a_j
    # の関係が成り立つ時
    # a_{lam+n+k*mu} = a_{lam+n+k'*mu}
    # より|i-j|は循環の長さの整数倍になる
    # そこで
    # a_m = a_2m
    # なるmを見つける
    # 前述の性質からmは循環の長さの整数倍となっているため
    # 2m - m = m = k*mu = lam + n + k'*mu
    # したがって、lam + nはmuの倍数となるので
    # 地点mからlamステップ進むと循環の開始点に到達する
    # lamが求まれば後は流れでmuも求まる
    
    tortoise = f(x0)
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
    lam = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        lam += 1
    mu = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        mu += 1
    return lam, mu

def solve(N: int, X: int, M: int):
    f = lambda x: x**2 % M

    def g(x):
        while True:
            yield x
            x = f(x)
            
    lam, mu = floyd_cycle_finding(f, X)
    ans = 0
    gg = g(X)
    k = max((N - lam) // mu, 0)
    for i in range(min(N, lam)):
        ans += next(gg)
    for i in range(mu):
        ans += k * next(gg)
    for i in range((N-lam)%mu):
        ans += next(gg)
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    print(solve(N, X, M))


def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()