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:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n, x, m = map(int,input().split())
    sum_lis = [-1] * m #余りが最初にiのときの和
    a_lis_i = [-1] * m #余りが最初にiのときのindex
    a = x
    sum_a = a
    sum_lis[a] = sum_a
    a_lis_i[a] = 0
    for i in range(1, n):
        a = pow(a, 2, m)
        sum_a += a
        if sum_lis[a] != -1: #2週目
            loop_i = i - a_lis_i[a] #1循環の個数
            loop_sum = sum_a - sum_lis[a] #1循環の和
            loop_cunt = (n - 1 - i)//loop_i #i+1以降の循環個数
            sum_a += loop_sum*loop_cunt #ループ分まとめて足す
            i += loop_i*loop_cunt
            for j in range(i + 1, n):
                a = pow(a, 2, m)
                sum_a += a             
            print(sum_a)
            sys.exit()
        sum_lis[a] = sum_a
        a_lis_i[a] = i
    print(sum_a)

if __name__=='__main__':
    main()

Submission status: Accepted

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

isUsed = [False] * M
isUsed[X] = True
S = [X]
st = X
while True:
    nx = X**2 % M
    if isUsed[nx]:
        st = nx
        break
    isUsed[nx] = True
    S.append(nx)
    X = nx

idx = S.index(st)
L, R = S[:idx], S[idx:]

ans = sum(L[:N])
N = max(0, N - len(L))

q, r = divmod(N, len(R))
ans += q * sum(R) + sum(R[:r])

print(ans)

Submission status: Accepted

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

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

memo = set()
lis = []
while X not in memo:
    memo.add(X)
    lis.append(X)
    X = cal(X)
pos = lis.index(X)

if pos >= N:
    print(sum(lis[:N]))
else:
    print(sum(lis[:pos]) + ((N-pos)//(len(memo)-pos)) * sum(lis[pos:]) + sum(lis[pos:(N-pos)%(len(memo)-pos)+pos]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, X, M = map(int, rl().split())
    
    A = []
    idx = dict()
    cnt = 0
    while 1:
        if X in idx:
            roop_start = idx[X]
            roop_size = cnt - roop_start
            break
        A.append(X)
        idx[X] = cnt
        X = X ** 2 % M
        cnt += 1
    
    if N <= roop_start:
        print(sum(A[:N]))
        return
    
    roop_cnt, rem = divmod(N - roop_start, roop_size)
    ans = sum(A[:roop_start])
    ans += roop_cnt * sum(A[roop_start:roop_start + roop_size])
    ans += sum(A[roop_start:roop_start + rem])
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
checked = [-1] * M
a = X
i = 0
while checked[a] == -1 and i < N:
    checked[a] = i
    a = a**2 % M
    i += 1

if i == N:
    a = X
    ans = 0
    for _ in range(N):
        ans += a
        a = a**2%M
    print(ans)
else:
    cycle_size = i - checked[a]
    cycle_num = a
    cycle = []
    cycle_sum = 0
    for _ in range(cycle_size):
        cycle.append(cycle_num)
        cycle_sum += cycle_num
        cycle_num = cycle_num**2 % M

    before_cycle_size = checked[a] 
    before_cycle = []
    before_cycle_sum = 0
    num = X
    for _ in range(before_cycle_size):
        before_cycle.append(num)
        before_cycle_sum += num 
        num = num**2 % M
    ans = before_cycle_sum
    ans += (N-before_cycle_size)//cycle_size * cycle_sum
    after_cycle_size = (N-before_cycle_size)%cycle_size
    for i in range(after_cycle_size):
        ans += cycle[i]
    
    print(ans)

Submission status: Accepted

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

def f(x):
    return (x ** 2) % M

m = [-1] * M

A = []
length = 0
total = 0
while m[X] == -1:
    A.append(X)
    m[X] = length
    length += 1
    total += X
    X = f(X)

# 周期
c = length - m[X]

# 周期の和
s = 0
for i in range(m[X], length):
    s += A[i]

res = 0
# 周期に入る前に終了
if N <= length:
    for i in range(N):
        res += A[i]
else:
    # とりあえず2週目に突入するまでの和を足して回数を減らす
    res += total
    N -= length
    # 周期をフルで使う回数分周期の和をかける
    res += s * (N // c)
    # 周期に満たないあまり
    N %= c
    for i in range(N):
        res += A[m[X] + i]

print(res)

Submission status: Accepted

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

a = x
r = [True for _ in range(m)]
s = []
while(r[a]):
  r[a] = False
  s.append(a)
  a = pow(a,2,m)
ai = s.index(a)
c = (n-len(s))//(len(s)-ai)
d = (n-len(s))-(len(s)-ai)*c
# print(i,ai,c,d)
ans = sum(s)+sum(s[ai:])*c+sum(s[ai:ai+d])
print(ans)

Submission status: Accepted

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

a = x
r = [False for _ in range(m)]
s = []
i = 0
while(r[a] == False and i < n):
  r[a] = True
  s.append(a)
  a = pow(a,2,m)
  i += 1
if i == n:
  ans = sum(s)
else:
  ai = s.index(a)
  c = (n-len(s))//(len(s)-ai)
  d = (n-len(s))-(len(s)-ai)*c
  # print(i,ai,c,d)
  ans = sum(s)+sum(s[ai:])*c+sum(s[ai:ai+d])
print(ans)

Submission status: Accepted

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

def input_int_array():
    return map(int, input().split())


def answer(n, x, m):
    a1 = x
    ai = a1
    loop_start = -1
    loop_end = n
    a[1] = a1
    ans = a1
    for i in range(2, n + 1):
        ai = ai*ai % m
        a.append(ai)
        ans += ai
        for j in range(1, i):
            if a[j] == ai:
                loop_start = j
                loop_end = i
                break
        if loop_start >= 0:
            break
    if loop_start < 0 or ai == 0:
        print(ans)
        return
    ans -= ai
    loop_count, remaining = divmod(n - (loop_start - 1), loop_end - loop_start)
    if loop_count > loop_start:
        start_ans = 0
        for i in range(1, loop_start):
            start_ans += a[i]
        loop_sum = ans - start_ans
        ans += loop_sum * (loop_count-1)
        for i in range(loop_start, loop_start + remaining):
            ans += a[i]
    else:
        for i in range(loop_start, loop_end):
            if i < remaining:
                ans += a[i]
            loop_sum += a[i]
        ans += loop_sum * (loop_count-1)
    print(ans)


n, x, m = input_int_array()
a = [0, 0]

answer(n, x, m)

Submission status: Accepted

Solution code:
import collections
n,x,m=map(int,input().split())
if n==1 or x==0:
  print(x)
  exit()
start,end,loopcnt=0,0,0
a={x:0}
wk=x
for i in range(1,m):
  wk=(wk*wk)%m
  if not wk in a:
    a[wk]=i
  else:
    start=a[wk]
    end=i
    break
a=sorted(a.items(),key=lambda x:x[1])
koteiindex=min(n,start)
koteiwa=0
for i in range(koteiindex):
  koteiwa+=a[i][0]
loopcnt=(n-koteiindex)//(end-start)
loopindex=start-1+(n-koteiindex)%(end-start)
loopwa=0
amariwa=0
for i in range(start,end):
  if i<=loopindex:
    amariwa+=a[i][0]
  loopwa+=a[i][0]
ans=koteiwa+loopwa*loopcnt+amariwa
print(ans)

Submission status: Accepted

Solution code:
import sys
n, x, m = map(int, input().split())
A = [0] * (10**5 + 1)
val = x
val_visited = set()
val_record = []
for i in range(n):
    if val in val_visited:
        break
    val_visited.add(val)
    val_record.append(val)
    val = val**2 % m
else:
    print(sum(val_record))
    sys.exit()

entry_idx = val_record.index(val)
loop_len = len(val_record) - entry_idx
loop_total_val = sum(val_record[entry_idx:])
head_len = len(val_record)

n -= head_len
loop_num = n // loop_len
tail_len = n % loop_len

ans = 0
#head
ans += (sum(val_record))
#loop
ans += loop_total_val * loop_num
#tail
for i in range(tail_len):
    ans += val_record[entry_idx + i]
print(ans)

Submission status: Accepted

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

ans=0
count=0
now=X
done=[-1]*(M-1)
L=[]
if now==0:
    print(ans)
    exit()
j=False
while True:
    if count==N:
        break

    if now==0:
        print(ans)
        exit()
    else:
        if done[now-1]==-1:
            done[now-1]=1
            L.append(now)
        else:
            for i in range(len(L)):
                if L[i]==now:
                    j=i
            break
    ans+=now
    count+=1
    now=(now**2)%M

if j:
    L=L[j:]

total=sum(L)
length=len(L)

ans+=((N-count)//length)*total
ans+=sum(L[:(N-count)%length])
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n,x,m = (int(x) for x in input().split())
lst = []
ans = 0
cnt = 0
i = 0
visited = [-1 for _ in xrange(m)]
stop_c = False
while i < n:
    if i == 0:
        ret = pow(x,1,m)
    else:
        ret = pow(x,2,m)
    x = ret
    if visited[ret] == -1:
        visited[ret] = i
    else:
        stop_c = True
        # i += 1
        break
    ans += ret
    lst.append(ret)
    i += 1

if stop_c:
    cycle_len = len(lst[visited[ret]:])
    cycle_sum = sum(lst[visited[ret]:])
    remsum  = sum(lst[visited[ret]:][:(n-visited[ret]) % cycle_len])
    print((ans -cycle_sum) + (cycle_sum * ((n-visited[ret]) // cycle_len)) + remsum)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,X,M=map(int, input().split())
m=[0]*M
t={}

def f(x,y):
    return x*x % y
a = X
s=0
for i in range(N):
    if a in t:
        x = t[a]
        nn = N - x
        q,r = divmod(nn,i-x)
        s = m[x-1] + (m[i-1] - m[x-1])*q + m[x-1+r] - m[x-1]
        break
    t[a]=i
    s += a
    m[i] = s
    a = f(a,M)
print(s)

Submission status: Accepted

Solution code:
import sys

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

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

l = [x]
s = {x}
prev = x

for i in range(1, m):
    next = prev ** 2
    next = next % m
    if next in s:
        break
    s.add(next)
    l.append(next)
    prev = next
start = l.index(next)
length = i - start

ans = 0
if n < start + length:
    ans += sum(l[:n])
else:
    ans += sum(l[:start])
    ans += sum(l[start:]) * ((n - start) // length)
    ans += sum(l[start:(start + ((n - start) % length))])

print(ans)

Submission status: Accepted

Solution code:
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    P = [p]
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
        P.append(p)
    front = P[:L]
    if L != N:
        cycle, end = P[L:R], P[L:L+(N-L)%period]
        cnt = (N-L)//period
    return front, cycle, end, cnt

################################################################################


import sys
input = sys.stdin.readline

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

N, X, M = map(int, input().split())
front, cycle, end, cnt = cycle_getter(N,X)
# print(front, cycle, end, cnt)
print(sum(front)+sum(cycle)*cnt+sum(end))

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
list=[0]*M
X1=X
for i in range(M):
  list[i]=(i**2)%M
  
l=[0]*M
l[X]=1
while l[list[X]]==0:
  l[list[X]]+=1
  X=list[X]
while l[list[X]]==1:
  l[list[X]]+=1
  X=list[X]
  
n1=l.count(1)
n2=l.count(2)

loop1=[0]*n1
for i in range(n1):
    loop1[i]+=X1
    X1=list[X1]
    
loop2=[0]*n2
for i in range(n2):
    loop2[i]+=X1
    X1=list[X1]
        
if N<=n1:
  print(sum(loop1[:N]))
else:
  print(sum(loop1)+(N-n1)//n2*sum(loop2)+sum(loop2[:(N-n1)%n2]))

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ans=x
count=1
table=[0]*m
table[x]=1
r=[0,x] #一般項
f=1
for i in range(n-1):
    x=pow(x,2,m)
    ans+=x
    count+=1
    if table[x]:
        f=0
        break
    r.append(x)
    table[x]=count
if f or table[0]:
    print(ans)
    exit()
ans=0
'''
table[x]項目とcount項目が同じ
loop前の項+loopの項*loop数+足りない分
'''
ans=sum(r[:table[x]])
loop=(n-table[x]+1)//(count-table[x])
ans+=sum(r[table[x]:])*loop
nokori=(n-table[x]+1)%(count-table[x])
for i in range(nokori):
    ans+=r[table[x]+i]
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
A = []
al = [-1]*(m+1)
cnt = 0
for i in range(n):
    if al[x%m] >= 0:
        break
    al[x%m] = cnt
    A.append(x)
    cnt += 1   
    x = x**2 % m

if n <= al[x]:
    print(sum(A[:al[x]]))
    exit()

lena = len(A)
loop = A[al[x]:]
lenl = cnt-al[x]
n -= al[x]
cnt = n//lenl
print(sum(A[:al[x]]) + sum(loop)*cnt + sum(loop[:n%lenl]))

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

n,x,m = readInts()
an = x
ans = an
moddict = {an:1}
for i in range(2,n+1):
  an = pow(an,2,m)
  if an in moddict:
    break
  else:
    moddict[an]=i
  ans += an
#print(ans)
if an in moddict:
  rep = (n-len(moddict))//(len(moddict)-moddict[an]+1)
  rem = (n-len(moddict))%(len(moddict)-moddict[an]+1)
  #print(rep,rem)
  rep_sum = 0
  boo = 0
  for key in moddict:
    if boo or key==an:
      boo = 1
      rep_sum+=key

  ans += rep_sum*rep
  for i in range(rem):
    ans+=an
    an=pow(an,2,m)


print(ans)

Submission status: Accepted

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

A_change_list = [0] * (M + 1)
check_list = [0] * (M + 1)

for i in range(1, M + 1):
    A_change_list[i] = i**2 % M

A = X
count = 0
sum_value = 0
ans = 0
for i in range(1, N + 1):
    if check_list[A] != 2:
        if check_list[A] == 1:
            count += 1
            sum_value += A
        ans += A
        check_list[A] += 1
        A = A_change_list[A]
    else:
        if A == 0:
            break
        elif A == 1:
            ans += N - i + 1
            break
        else:
            div, mod = divmod((N - i), count)
            ans += sum_value * div
            for _ in range(mod + 1):
                ans += A
                A = A_change_list[A]
            break

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n,x,m = readInts()
an = x
ans = an
moddict = {an:1}
for i in range(2,n+1):
	an = pow(an,2,m)
	if an in moddict:
		break
	else:
		moddict[an]=i
	ans += an
#print(ans)
if an in moddict:
	rep = (n-len(moddict))//(len(moddict)-moddict[an]+1)
	rem = (n-len(moddict))%(len(moddict)-moddict[an]+1)
	#print(rep,rem)
	rep_sum = 0
	boo = 0
	for key in moddict:
		if boo or key==an:
			boo = 1
			rep_sum+=key

	ans += rep_sum*rep
	for i in range(rem):
		ans+=an
		an=pow(an,2,m)


print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X, M = MAP()
visited = [0]*M
now = X
cnt = 0
l = []

while not visited[now]:
    l.append(now)
    visited[now] = True
    now = (now*now)%M
    cnt += 1
    if cnt == N:
        print(sum(l))
        exit()

idx = l.index(now)
loop = l[idx:]
loop_cnt = len(loop)
loop_sum = sum(loop)

cnt, m = divmod(N-(len(l)-loop_cnt), len(loop))
ans = sum(l[:idx])+loop_sum*cnt+sum(loop[:m])
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, x, m = map(int, input().split())
    d1 = defaultdict(int)
    r = 0
    while n:
        if d1[x]:
            cycle = d1[x] - n
            t0 = 0
            cycle2 = cycle
            while cycle2:
                t0 += x
                x = x**2 % m
                cycle2 -= 1
            c, rem = divmod(n,  cycle)
            r += c * t0
            while rem:
                r += x
                x = x**2 % m
                rem -= 1
            print(r)
            sys.exit()
        else:
            d1[x] = n
            r += x
            x = x**2 % m
        n -= 1
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if N < M:
    ans = 0
    val = X
    for i in range(N):
        ans += val
        val = (val%M)*(val%M)%M
        
    print(ans)
    exit()

until_start_loop = 0
loop_len = 0
cum_sum = [0]
until_start_loop_sum = 0
loop_sum = 0

ls = [0]*M
val = X
cnt = 0 #TimeStamp
while True:
    if ls[val]:
        until_start_loop = ls[val] - 1
        loop_len = cnt - until_start_loop
        # until_start_loop -= 1
        until_start_loop_sum = cum_sum[until_start_loop]
        loop_sum = cum_sum[cnt] - until_start_loop_sum
        break
    cnt += 1
    ls[val] = cnt
    cum_sum.append(cum_sum[-1] + val)
    val = (val%M)*(val%M)%M


how_many_loop = (N-until_start_loop)//(loop_len)
ans = until_start_loop_sum + how_many_loop * loop_sum
remained = N - how_many_loop * loop_len - until_start_loop
ans += cum_sum[until_start_loop + remained] - cum_sum[until_start_loop]
print(ans)

Submission status: Accepted

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

ans = X
A = X
TF = True
srt = 1000000
retu = [X]
d = dict()
d[X] = 0
loop = X
flag = False
for i in range(N-1):
    if TF:
        A = A**2 % M
        if d.get(A) != None:
          srt = d[A]
          goal = i
          TF = False
          
        if TF:
          retu.append(A)
          d[A] = i + 1
          loop += A
    else:
      flag = True
      break
      
if flag:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Accepted

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

existence = [False] * M
a = []
A = X
for i in range(N):
    if existence[A]:
        break
    existence[A] = True
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        break
loop_start = i

result = sum(a[:loop_start])
a = a[loop_start:]
N -= loop_start
loops = N // len(a)
remainder = N % len(a)
result += sum(a) * loops + sum(a[:remainder])
print(result)

Submission status: Accepted

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

existence = [0] * M
a = []
A = X
for i in range(N):
    if existence[A] != 0:
        break
    existence[A] = 1
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        break
j = i

result = sum(a[:j])
a = a[j:]
N -= j
x = N // len(a)
y = N % len(a)
result += sum(a) * x + sum(a[:y])
print(result)

Submission status: Accepted

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

dic = {}
tmp = []

a = x
sum_a = x
for i in range(n - 1):
    if a in dic:
        tmp.append(sum_a)
        idx0 = dic[a] - 1
        idx1 = i - 1
        period = idx1 - idx0
        times = (n - 1 - idx0) // period
        res = (n - 1 - idx0) % period
        before = tmp[idx0]
        if idx0 >= 0:
            ans = tmp[idx0 + res] + (tmp[idx1] - tmp[idx0]) * times
            print(ans)
        elif idx0 < 0:
            if res > 0:
                ans = (tmp[idx1 + 1] - tmp[idx0 + 1]) * times + tmp[res - 1]
                print(ans)
            else:
                ans = (tmp[idx1 + 1] - tmp[idx0 + 1]) * times
                print(ans)
        break
    else:
        tmp.append(sum_a)
        dic[a] = i
        a = a ** 2 % m
        sum_a += a
else:
    print(sum_a)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
A = [X,]
setA = {X,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if flag:
    if alast==0:
        ans = sum(A)
    else:
        res = (N-d)%len(C)
        ans = sum(A[:d])+((N-d)//len(C))*sum(C) + sum(C[:res])
else:
    ans = sum(A) 
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, X, M = NMI()
    
    tmp = X%M
    
    ls = []
    ls.append(tmp)
    
    for n in range(N-1):
        tmp = (tmp ** 2)%M
        
        if tmp in ls:
            ls_before_loop = ls[:ls.index(tmp)]
            ls_in_loop = ls[ls.index(tmp):]
            break
        else:
            ls.append(tmp)


    
    if len(ls) == N:
        print(sum(ls))
    else:
        sum_before_loop = sum(ls_before_loop)
        sum_in_loop = ((N-len(ls_before_loop))//(len(ls_in_loop)))*sum(ls_in_loop)
        sum_after_loop = sum(ls_in_loop[:(N-((N-len(ls_before_loop))//(len(ls_in_loop)))*len(ls_in_loop))-len(ls_before_loop)])
        print(sum_before_loop+sum_in_loop+sum_after_loop)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
ans = 0
l = [x]
s = [0]*m
s[0] = 1

for i in range(n):
	x = (x*x)%m
	if s[x] == 1:
		break
	s[x] = 1
	l.append(x)

if x == 0:
	print(sum(l))
else:
	p = l[0]
	k = 1
	Su = 0
	while p != x and k < len(l):
		Su += p
		p = l[k]
		k += 1
	l = l[k-1:]

	Su2 = 0
	for r in range((n-k)%len(l) + 1):
		Su2 += l[r]
	print(Su + ((n-k)//len(l))*sum(l) + Su2)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
a = X
hist = [a]
indices = [-1]*M
indices[a] = 0
flag=0
for i in range(1,min(10**6,N)):
  a = a**2 % M
  if indices[a] != -1:
    idx = indices[a]
    flag=1
    break
  hist.append(a)
  indices[a] = i
  
if flag==0:
  print(sum(hist))
  exit()
  
cycle = hist[idx:]
margin = hist[:idx]
q,r = divmod((N-len(margin)),len(cycle))
print(sum(margin)+sum(cycle)*q+sum(cycle[:r]))

Submission status: Accepted

Solution code:
import math


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

    A = [X]
    vis = [-1] * M
    vis[X] = 0
    for i in range(1, M + 1):
        X = X ** 2 % M
        if vis[X] != -1:
            prefix = A[:vis[X]]
            cycle = A[vis[X]:]
            break
        A.append(X)
        vis[X] = i

    if N < len(prefix):
        return sum(prefix[:N])
    else:
        n_full_period = (N - len(prefix)) // len(cycle)
        suffix_length = N - len(prefix) - n_full_period * len(cycle)
        ans = 0
        ans += sum(prefix)
        ans += sum(cycle) * n_full_period
        ans += sum(cycle[:suffix_length])
        return ans

print(solve())

Submission status: Accepted

Solution code:
import math


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

    if N == 1:
        return X % M

    A = [X]
    vis = [-1] * M
    vis[X] = 0
    for i in range(1, M + 1):
        X = X ** 2 % M
        if vis[X] != -1:
            pref = A[:vis[X]]
            cycle = A[vis[X]:]
            break
        A.append(X)
        vis[X] = i

    n_full_period = (N - len(pref)) // len(cycle)
    suffix_length = N - len(pref) - n_full_period * len(cycle)

    ans = 0
    ans += sum(pref)
    ans += sum(cycle) * n_full_period
    ans += sum(cycle[:suffix_length])
    return ans

print(solve())

Submission status: Accepted

Solution code:
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [], [], []
    cnt = 0
    visit = {p:0}
    L, R = N, -1
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに入るまでに移動した回数, サイクルの終端に着くまでに移動した回数)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (1, 6)
            """
            L, R = visit[p], i
            period = R-L
            break
        visit[p] = i
    p = start
    for _ in range(L):
        front.append(p)
        p = lift(p)
    if L != N:
        for _ in range(L,R):
            cycle.append(p)
            p = lift(p)
        for _ in range(N-(N-L)%period,N):
            end.append(p)
            p = lift(p)
        cnt = (N-L)//period
    return front, cycle, end, cnt

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

################################################################################
import sys
input = sys.stdin.readline

N, X, M = map(int, input().split())
front, cycle, end, cnt = cycle_getter(N,X)
print(sum(front)+sum(cycle)*cnt+sum(end))

Submission status: Accepted

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

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

A=[0]*(M+1)
A[0]=X
D=[0]*(M+1)

s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if D[a] == 1:
        s=A.index(a)
        break
    else:
        A[i]=a
        D[a]=1

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


print(ans)

Submission status: Accepted

Solution code:
def solve(N, X, M):
    x = X
    table = [-1] * M
    a = []
    length = 0
    # ループするまで配列に値を入れていく
    while table[x] == -1:
        a.append(x)
        table[x] = length
        length += 1
        x = x**2 % M

    # ループの開始位置とループの合計値を求める
    start = table[x]
    loop_total = 0
    for i in range(table[x], length):
        loop_total += a[i]

    # 答えの計算
    ans = 0
    if N <= length:
        for i in range(N):
            ans += a[i]
    else:
        # フルで何周するかを計算
        count = N - start
        count //= (length-start)
        ans += count * loop_total
        count *= (length-start)
        count = N - count
        for i in range(count):
            ans += a[i]

    return ans


if __name__ == "__main__":
    N, X, M = map(int, input().split())
    print(solve(N, X, M))

Submission status: Accepted

Solution code:
import sys
import copy
#import math
#import itertools
#import numpy as np
#import re

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

N,X,M=[int(c) for c in input().split()]
myset = {X}
mydict = {X:0}
A = []
A.append(X)
s = X
i = 0
i_stop = i
#i=0は計算したので1から
for i in range(1,N):
    A.append(func(A[i-1],M))
    if A[i] in myset:
        i_stop = i
        break
    myset.add(A[i])
    mydict[A[i]] = i
    s+=A[i]
    if i == N-1:
        print(s)
        sys.exit(0)
    if A[i] == 0:
        print(s)
        sys.exit(0)

if i!=0:
    #最後にA[i]が出現したのは？
    A_repeat = A[mydict[A[i_stop]]:i_stop]
    s+=((N-1)-(i_stop-1))//len(A_repeat)*sum(A_repeat)

    for k in range(((N-1)-(i_stop-1))%len(A_repeat)):
        s+=A_repeat[k]

print(s)

Submission status: Accepted

Solution code:
'''
Doubling

nxt[i][r] = the value of r mod M after 2 ** i squaring
dp[i][r] = the sum of sequence of lenght 2 ** i starting from r

We split sequence A into multiple disjoint parts, 
where the lengths of each parts are the binary decomposition of N.

e.g.
N = 11 = 1 + 2 + 8
A = A[0:1], A[1:3], A[3:11]
Sum of each parts are:
sum(A[0:1]) = dp[0][A[0] % M]
sum(A[1:3]) = dp[1][A[1] % M]
sum(A[3:11]) = dp[3][A[3] % M]
'''

import math

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

H = math.ceil(math.log2(N)) + 1

nxt = [[0] * M for _ in range(H)]
dp = [[0] * M for _ in range(H)]
nxt[0] = [r ** 2 % M for r in range(M)]
dp[0] = list(range(M))

for i in range(1, H):
    for r in range(M):
        nxt[i][r] = nxt[i - 1][nxt[i - 1][r]]
        dp[i][r] = dp[i - 1][r] + dp[i - 1][nxt[i - 1][r]]

ans = 0
r = X % M
for i in range(H):
    if N & (1 << i):
        ans += dp[i][r]
        r = nxt[i][r]
print(ans)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N, X, M = rl()

Xs = [None] * M

ans = 0
dif_i = 0
dif_v = 0
cur_i = 0
for i in range(1, N+1):
	ans += X
	if Xs[X] != None:
		cur_i = i
		dif_v = ans - Xs[X][1]
		dif_i = i - Xs[X][0]
		cur_x = X
		break
	Xs[X] = (i, ans)
	X = (X**2) % M
if cur_i > 0 and cur_i < N:
	remain = N - cur_i
	ans += (remain // dif_i) * dif_v
	X = cur_x
	for i in range(remain % dif_i):
		X = (X**2) % M
		ans += X
print(ans)

Submission status: Accepted

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

A = [0] * (M + 1)
firstApearAt = {i:0 for i in range(M)}
A[1] =  X
firstApearAt[X] = 1
l, r = 1, 2
for i in range(2, M + 1):
    A[i] = (A[i - 1] * A[i - 1]) % M
    if firstApearAt[A[i]] > 0:
        r = i
        l = firstApearAt[A[i]]
        break
    firstApearAt[A[i]] = i

ans = 0
if N <= l - 1:
    ans = sum(A[1:N + 1])
else:
    q, p = (N - l + 1) // (r - l), (N - l + 1) % (r - l)
    ans = sum(A[1:l]) + q * sum(A[l:r]) + sum(A[l:l + p])

print(ans)