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

ans = 0
f = [-1]*m # a->f
f[x] = 0

ansl = [x]
curr_x = x
loop_start = -1
for i in range(n-1):
    cnt = i+1
    x2 = (curr_x**2)%m
    if f[x2] == -1:
        ansl.append(x2)
        f[x2] = cnt
    else:
        loop_start = f[x2]
        break
    curr_x = x2
else:
    print(sum(ansl))
    exit()

amari = ansl[0:loop_start]

n_rem = n - loop_start
loop_l = ansl[loop_start:]
loop_len =len(loop_l)
loop_sum = sum(loop_l)

loop_cnt = n_rem//loop_len
loop_amari = n_rem - loop_cnt*loop_len

ans = sum(amari) + sum(loop_l)*loop_cnt + sum(loop_l[:loop_amari])
print(ans)

Submission status: Accepted

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

D = [X]

E = set([X])

F = [0,X]

for i in range(M+1):
    X = X**2
    X%=M
    if X in E:
        break
    D.append(X)
    E.add(X)
    F.append(F[-1]+X)
if N<=len(D):
    print(F[N])
else:
    for i in range(len(D)):
        if D[i]==X:
            break
    #print(D)
    num = (N-i-1)//(len(D)-i)
    res = (N-i-1)%(len(D)-i)
    print(F[res+i+1] + num*(F[-1]-F[i]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N, X, M = map(int, input().split())
now = X
l = [X]
s = set()
s.add(X)

for i in range(N-1):
    now = now*now%M
    
    if now in s:
        for i in range(len(l)):
            if l[i]==now:
                mark = i
                break
        
        ans = sum(l[:mark])
        siz = len(l)-mark
        tot = sum(l[mark:])
        ans += (N-mark)//siz*tot
        ama = (N-mark)%siz
        
        for i in range(mark, mark+ama):
            ans += l[i]
        
        print(ans)
        exit()
    
    l.append(now)
    s.add(now)

print(sum(l))

Submission status: Accepted

Solution code:
N, X, M = map(int,input().split())
visited = [(-1,-1)]*M
ans = 0
for i in range(N):
    if visited[X][0] >= 0:
        d = ans - visited[X][0]
        left = N-i
        length = i-visited[X][1]
        ans += (left//length)*d
        left %= length
        for j in range(left):
            ans += X
            X = X*X % M
        break
    visited[X] = (ans, i)
    ans += X
    X = X*X % M
print(ans)

Submission status: Accepted

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

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

A = [0] * m
for i in range(m):
    A[i] = (i*i)%m

V = [-1] * m
B = [x]
xx = x

cnt = 0
while V[xx] == -1:
    V[xx] = cnt
    cnt += 1
    xx = A[xx]
    B.append(xx)

end = V[xx]
# print(end)

# print(B[:10])
# print(len(B))
# print()
S = [B[0]]
for i in range(1, len(B)):
    S.append(B[i] + S[-1])

# print(S[:10])
# print(sum(S) * (n//len(B)) + sum(S[:n%len(B)]))

if end >= n:
    print(sum(B[:n]))
else:
    n -= end+1
    # print("newn",n)
    ans = sum(B[:end+1])
    # print("ans",ans)
    ans += sum(B[end+1:]) * (n // (len(S)-end-1))
    # print("ans",ans)
    ans += sum(B[end+1:end+1+n % (len(S)-end-1)])
    print(ans)

Submission status: Accepted

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

val = [-1] * (mod + 100)
val[X] = 1

a = X
idx = 2
memo = [X]

while True:
    a = a * a % mod
    if val[a] != -1:
        last = a
        break
    memo.append(a)
    val[a] = idx
    idx += 1

# print(memo)
# print(last)

if N <= len(memo):
    print(sum(memo[:N]))
else:
    ans = sum(memo)
    N -= len(memo)
    i = memo.index(last)
    L = len(memo) - i

    sm = sum(memo[i:])
    d, m = divmod(N, L)
    ans += sm * d
    for x in range(i, i + m):
        ans += memo[x]
    print(ans)

Submission status: Accepted

Solution code:
def f(a, m):
    return a**2%m

def main():
    N, X, M = map( int, input().split())
    A = [X]
    T = [False]*M
    T[X] = True
    now = X
    while True:
        now = f(now, M)
        if T[now]:
            break
        T[now] = True
        A.append(now)
    R = len(A)
    for i in range(R-1,-1,-1):
        if now == A[i]:
            L = i
            break
    # L<= < Rでループ、R-L
    if N <= L:
        print( sum(A[:N]))
        return
    ans = sum(A[:L])
    loopsum = sum(A[L:])
    loopsize = R-L
    N -= L
    ans += N//loopsize*loopsum
    N -= N//loopsize*loopsize
    now = A[L]
    while N > 0:
        ans += now
        now = f(now,M)
        N -= 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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



set_ = set([x])
res = [x]
for i in range(m + 200):
    x = x ** 2 % m
    if x in set_:
        break
    res.append(x)
    set_.add(x)

if len(res) >= n:
    print(sum(res[0:n]))
    exit()

init = 0
init_terms = 0
ans = 0
for i in range(len(res)):
    if res[i] == x:
        l = i
        break
    init += res[i]
    init_terms += 1

ans = init
lap = res[l:]
sum_lap = sum(lap)
len_lap = len(lap)



div, mod = divmod(n - init_terms, len_lap)
ans += div * sum_lap + sum(lap[0:mod])
print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
A=[[0]*2 for i in range(m)]
A[x]=[1,x]
a=x
f=-1
for i in range(10**5+100):
  if i==n-1:
    f=0
    break
  x=x**2%m
  a=a+x
  if A[x][0]!=0:
    f=1
    break
  A[x]=[i+2,a]
if f==0:
  print(a)
elif f==1:
  ans=A[x][1]+(a-A[x][1])*((n-A[x][0])//(i+2-A[x][0]))
  for i in range((n-A[x][0])%(i+2-A[x][0])):
    x=x**2%m
    ans=ans+x
  print(ans)

Submission status: Accepted

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

A = [X]
x = (X**2)%M

while x not in A:
  A.append(x)
  x = (x**2)%M

if len(A) >= N:
  answer = sum(A[:N])
else:
  index = 0
  while A[index] != x:
    index += 1
  len_loop = len(A) - index
  num_loop = (N-index)//len_loop
  num_last = N - index - len_loop*num_loop
  answer = sum(A[:index]) + num_loop*sum(A[index:]) + sum(A[index:index+num_last])

print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, X, M = map(int, input().split())
table = [0] * M
c = [0] * M
c[X] = 1
x = X
while table[x] <= 1:
  table[x] += 1
  if c[x ** 2 % M] == 0: c[x ** 2 % M] = c[x] + 1
  x = x ** 2 % M
loop = table.count(2)
#print(loop)
res = 0
for x in range(M):
  if c[x] in range(1, N + 1):
    res += x
    if c[x] + loop in range(1, N + 1) and (table[x] >= 2): res += x * ((N - c[x]) // loop)
print(res)

Submission status: Accepted

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

L = [-1] * M

a = X
i = 0
while True:
    if L[a] != -1:
        B = L[a]
        C = i - L[a]
        break
    L[a] = i
    a = a * a % M
    i += 1


ans = 0
if N <= B + C:
    a = X
    for i in range(N):
        ans += a
        a = a * a % M
else:
    a = X
    for i in range(B):
        ans += a
        a = a * a % M
    temp = 0
    for i in range(B, B+C):
        temp += a
        a = a * a % M
    ans += (N-B) // C * temp
    for i in range((N-B)%C):
        ans += a
        a = a * a % M
print(ans)

Submission status: Accepted

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

# 循環が先頭ではなく途中に戻るパターンもある

mod_list = [x]
mod_dict = {x: 0}
now = x
idx = 0

while True:
    now = now ** 2
    now %= m

    idx += 1
    if now in mod_dict:
        # 周期が見つかった
        period = idx - mod_dict[now]
        initial = mod_dict[now]
        break
    else:
        mod_list.append(now)
        mod_dict[now] = idx
    
# print(mod_list)
# print(mod_list[:initial])
# print(initial)

if n <= initial:
    print(sum(mod_list[:n]))
else:
    ans = 0
    ans += sum(mod_list[:initial])

    loop_num = (n - initial) // period
    rest = (n - initial) % period

    ans += sum(mod_list[initial:]) * loop_num
    ans += sum(mod_list[initial: initial+rest])
    print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
loop = [X]
appeared = set(loop)
while True:
  n = loop[-1] ** 2 % M
  if n in appeared:
    break
  else:
    loop.append(n)
    appeared.add(n)
if N <= len(loop):
  print(sum(loop[:N]))
  exit()
  
i = loop.index(n)
preloop = loop[:i]
loop = loop[i:]

total = sum(preloop)
N -= len(preloop)
#print(total, N)
total += sum(loop) * (N // len(loop))
for l, _ in zip(loop, range(N % len(loop))):
  total += l
print(total)

Submission status: Accepted

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

yj=[x]
lps=0
for i in range(n):
  an=(yj[i]**2)%m
  if an in yj:
    lps=yj.index(an)
    break
  yj.append(an)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,x,m = map(int, readline().split())
#lr = [list(map(int, readline().split())) for _ in range(k)]


nxt = [x*x%m for x in range(m)]
wa = list(range(m))
ans = 0

while n:
    if n&1:
        ans += wa[x]
        x = nxt[x]
    wa = [wa[nxt[i]] + wa[i] for i in range(m)]    
    nxt = [nxt[i] for i in nxt]
    n >>= 1

print(ans)

Submission status: Accepted

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

N,X,M=map(int,input().split())
LIST=[X]
SET={X}

a=X

while True:
    if a*a%M in SET:
        break
    else:
        a=a*a%M
        LIST.append(a)
        SET.add(a)

l=LIST.index(a*a%M)
LEN=len(LIST)

if N<=LEN:
    print(sum(LIST[:N]))
else:
    ANS=sum(LIST[:l])
    N-=l
    LIST=LIST[l:]
    S=sum(LIST)

    r,q=divmod(N,len(LIST))

    print(ANS+S*r+sum(LIST[:q]))

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
L = []
used = set()
while x not in used:
    used.add(x)
    L.append(x)
    x = x*x%m
cnt = 0
while L[cnt] != x:
    cnt += 1
l = len(L)
if n <= l:
    print(sum(L[:n]))
    exit()
s = sum(L)
t = sum(L[cnt:])
q, r = divmod(n-l, l-cnt)
ans = s + q*t
for i in range(r):
    ans += L[cnt]
    cnt += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8, i8, i8), cache=True)
def main(N, X, M):
    A = np.empty(M + 10, np.int64)
    A[0] = X
    first = np.full(M, -1, np.int64)
    n = 0
    while True:
        n += 1
        A[n] = A[n - 1] * A[n - 1] % M
        if first[A[n]] >= 0:
            period = n - first[A[n]]
            offset = first[A[n]] + 1
            break
        first[A[n]] = n
    if N <= offset:
        return A[:N].sum()
    x = A[:offset].sum()
    N -= offset
    q, r = divmod(N, period)
    x += q * A[offset:offset + period].sum()
    x += A[offset:offset + r].sum()
    return x

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

print(main(N, X, M))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

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

N,X,M=mint()
ans=X
se={X:1}
l=[0,X]
tmp=X
for k in range(2,N+1):
    tmp=(tmp*tmp)%M
    if tmp in se:
        i=se[tmp]
        ans=sum(l[:i])
        N-=(i-1)
        ans+=(N//(k-i))*sum(l[i:k])
        N-=(N//(k-i))*(k-i)
        for t in range(N):
            ans+=l[i+t]
        break
    se[tmp]=k
    l.append(tmp)
    ans+=tmp
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
mod_appeared = [False] * M
A_cycle = [X]
mod_appeared[X] = True
A = X * X % M
while not mod_appeared[A]:
    A_cycle.append(A)
    mod_appeared[A] = True
    A = A * A % M


if N < len(A_cycle):
    print(sum(A_cycle[:N]))
    exit()

cycle_start = A_cycle.index(A)
cycle_len = len(A_cycle) - cycle_start
cycle_sum = sum(A_cycle[cycle_start:])
prefix_sum = sum(A_cycle[:cycle_start])

q, r = divmod(N - cycle_start, cycle_len)
ans = prefix_sum + q * cycle_sum + sum(A_cycle[cycle_start:cycle_start + r])
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
A = [X]
S = [0, X]
Y = [-1] * M
f = 0
s = X
for i in range(1, M * 5 + 10):
    a = A[-1] ** 2 % M
    s += a
    A.append(a)
    S.append(s)
    if f == 0 and Y[a] >= 0:
        rp = i - Y[a]
        t = Y[a]
        f = 1
    Y[a] = i
if N < M * 5 * 0:
    print(S[N])
else:
    j = N % rp + (t // rp + 1) * rp
    print(S[j] + (S[t + rp] - S[t]) * (N - j) // rp)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
a=[x]
su=x
s={x}
for i in range(n-1):
  x=(x**2)%m
  if x in s:
    n-=i+1
    a=a[a.index(x):]
    l=len(a)
    su+=sum(a)*(n//l)
    n-=(n//l)*l
    su+=sum(a[:n])
    print(su)
    exit()
  a.append(x)
  su+=x
  s.add(x)
print(su)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, x, mod = map(int, input().split())

    seen = [0] * mod
    ans = 0
    A = []
    ii = -1
    for i in range(N):
        if seen[x] == 0:
            seen[x] = 1
        elif seen[x] == 1:
            A.append(x)
            seen[x] = 2
        elif seen[x] == 2:
            ii = i
            break
        ans += x
        x = (x * x) % mod
    if ii == -1:
        print(ans)
    else:
        rem = N - ii
        ans += sum(A) * (rem // len(A))
        rem %= len(A)
        for j in range(rem):
            ans += A[j]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    sums = [0]
    s = 0
    seen = {}
    for i in range(N):
        if X in seen:
            previ = seen[X]
            # repeats from previ, ... i-1
            seq_length = i - previ
            remaining_full = (N - i) // seq_length
            remaining_part = (N - i) - remaining_full * seq_length
            s += (sums[-1] - sums[-seq_length-1]) * remaining_full
            s += sums[remaining_part-seq_length-1] - sums[-seq_length-1]
            print(s)
            return
        s += X
        sums.append(s)
        seen[X] = i

        X = X * X % M

    print(s)

main()

Submission status: Accepted

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

slow = x
fast = x
out = 0

while n:
    if n != nn and slow == fast:
        break
    out += slow
    n -= 1

    slow = (slow * slow) % m
    fast = (fast * fast) % m
    fast = (fast * fast) % m

head = slow
curr_sum = slow
curr_count = 1
slow = (slow * slow) % m
while slow != head:
    curr_count += 1
    curr_sum += slow
    slow = (slow * slow) % m

while n % curr_count:
    out += slow
    n -= 1
    slow = (slow * slow) % m

out += (n // curr_count) * curr_sum
print(out)

Submission status: Accepted

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

def main():
    n, x, m = map(int, input().split())
    loop = [x]
    check = [False for _ in range(m + 1)]
    check[x] = True
    x2 = x
    for _ in range(n - 1):
        x2 = x2 ** 2 % m
        if check[x2]:
            break
        check[x2] = True
        loop.append(x2)
    else:
        print(sum(loop))
        return
    pos = loop.index(x2)
    ans = sum(loop[:pos])
    loop2 = loop[pos:]
    l = len(loop2)
    n -= pos
    ans += sum(loop2) * (n // l)
    ans += sum(loop2[:n % l])
    print(ans)
    
    
main()

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
Q=0
for i in range(min(100,N)):
  Q+=X
  X=X*X%M
N-=min(N,100)
S=set([X])
P=X
A=X
R=0
for i in range(M):
  A=A*A%M
  if A in S:
    R=i+1
    break
  S.add(A)
  P+=A
P*=(N//R)
N%=R
for i in range(N):
  P+=X
  X=X*X%M
print(P+Q)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, x, m = na()
hit = {}
hit[x] = 0
a = [x]

pe = -1
while True:
    v = a[-1] * a[-1] % m
    if v in hit:
       pe = len(a)-hit[v]
       break
    a.append(v)
    hit[v] = len(a)-1
ta = len(a) - pe
if n <= len(a):
    print(sum(a[0:n]))
else:
    cy = (n-ta) // pe
    u = (n-ta) % pe + ta
    print(sum(a[0:u]) + cy*sum(a[ta:]))

Submission status: Accepted

Solution code:
n,x,m = map(int, input().split())
ai = x
tmp = [ai]
used = set(tmp)
for i in range(n):
    nxt = ai**2 % m
    if nxt in tmp:
        break
    tmp.append(nxt)
    ai = nxt
if len(tmp) == n:
    ans = sum(tmp)
    print(ans)
    exit()

first = tmp.index(nxt)
ans = 0
l = []
for i in range(len(tmp)):
    if i < first:
        ans += tmp[i]
        n -= 1
    else:
        l.append(tmp[i])
m = len(l)
x,y = divmod(n, m)
ans += sum(l)*x
for i in range(y):
    ans += l[i]
print(ans)

Submission status: Runtime Error

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

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

a_list = [x]
a = x
i = 1
while (i<n and i < m):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    
#print(i)
#print(a_list)
    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    #print(blen)
    #print(amari)
    #print(sum1, sum2, repeat, sum3)

print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m

if n < len(P):
    print(P[n+1]) # next pre sum_p
    exit()
if n == len(P):
    print(sum_p) # full sum_p
    exit()

cyc_times, nxt_len = divmod(n-X[x], len(P) - X[x])
cyc = (sum_p - P[X[x]]) * cyc_times
remain = P[X[x] + nxt_len]
print(cyc + remain)

Submission status: Runtime Error

Solution code:
# 繰り返しの始まり + 繰り返し + 途中で終わった繰り返し分
N,X,M = map(int,input().split())
p = [0] * (M+2)
sum = [0] * (M+2)
p[X] = 1
sum[1] = X

repeat_start = 0
repeat_end = 0

for i in range(2,N+1):
  X = (X**2) % M
  if p[X] != 0:
    repeat_start = p[X]
    repeat_end = i
    break
  else:
    sum[i] = sum[i-1] + X
    p[X] += i

if repeat_start == 0:
  print(sum[N])
else:
  repeat_cnt,mod=divmod(N-repeat_start-1,repeat_end-repeat_end)
  print(d*(sum[repeat_end-1]-sum[repeat_start-1]) + sum[repeat_start+mod-1])

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
X = [-1] * m
P = []
sum_p = 0
while X[x] == -1: # preset
    X[x] = len(P) # pre length
    P.append(sum_p) # pre sum_p
    sum_p += x # now sum_p
    x = x*x % m

if n < len(P):
    print(P[n+1]) # next pre sum_p
    exit()
if n == len(P):
    print(sum_p) # full sum_p
    exit()

cyc_len = len(P) - X[x]
n -= X[x]
cyc = (sum_p - P[X[x]]) * (n // cyc_len)
remain = P[X[x] + n % cyc_len]
print(cyc + remain)

Submission status: Runtime Error

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

cnt = [False] + [1] + [0] * (M-1)
numbers = [X]
ans = 0

if M == 0:
  print(0)
  exit()
for n in range(N):
  X = pow((X % M),2)%M
  cnt[X] += 1
  if (cnt[X] >= 2) or X == 0:
    break
  else:
    numbers.append(X) 

if X == 0:
  print(sum(numbers))
  exit()

repeat_before = numbers[0:numbers.index(X)]
repeat = numbers[numbers.index(X):X]

repeat_cnt,mod  = divmod(N-numbers.index(X),len(repeat))


print(sum(repeat_before) + sum(repeat) * repeat_cnt + sum(repeat[:mod]))

Submission status: Runtime Error

Solution code:
# 繰り返しの始まり + 繰り返し + 途中で終わった繰り返し分
N,X,M = map(int,input().split())

cnt = [False] + [1] + [0] * (M-1)
numbers = [X]
ans = 0
for n in range(N):
  X = pow((X % M),2)%M
  cnt[X] += 1
  if (cnt[X] >= 2) or X == 0:
    break
  else:
    numbers.append(X) 

if X == 0:
  print(sum(numbers))
  exit()

repeat_before = numbers[0:numbers.index(X)]
repeat = numbers[numbers.index(X):X]

repeat_cnt,mod  = divmod(N-numbers.index(X),len(repeat))


print(sum(repeat_before) + sum(repeat) * repeat_cnt + sum(repeat[:mod]))

Submission status: Runtime Error

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

chk = [0 for i in range(m)]
a = x
s = x
c = 1
ary = [x]
flg = False
while True:
  if c == n:
    break
  x = (x**2)%m
  s += x
  c += 1
  if chk[x]:
    flg = True
    break
  ary.append(x)
  chk[x] = c
if flg == False:
  print (s)
  exit()
cyc = ary[chk[x]:]
l1 = len(cyc)
ss = ary[:chk[x]]
l2 = len(ss)
tot = sum(ss) + sum(cyc)*((n-l2)//l1) + sum(cyc[:(n-l2)%l1])
print (tot)

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    x, y = min(x,y), max(x,y)
    if y % x == 0:
        return x
    else:
        return gcd(x, y % x)
def SUM(n):
    return n*(n+1)//2
N, X, M = map(int, input().split())
count = 0
if gcd(X, M) != 1:
    A = X
    while A != 0:
        count += A
        A = A**2 % M
    print(count)
else:
    p = N // M
    q = N % M
    count += SUM(M-1) * p
    A = X
    for i in range(q):
        count += A
        A = A**2 % M
    print(count)

Submission status: Runtime Error

Solution code:
def my_func(n, x, m):
    if n == 1:
        return x
    elif n == 2:
        b = x ** 2 % m
        return b
    else:
        b = my_func(n-1, x, m) ** 2 % m
        return b

if __name__ == "__main__":


    n,x,m = (int(k) for k in input().split())

    ans = 0

    for i in range(1, n+1):
        ans += my_func(i,x,m)

    print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x]+nxt_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Runtime Error

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

start_loop = 0

for n in range(N):
        tmp = a[n]*a[n]%M
        if(tmp in a):
                start_loop = a.index(tmp)
                break
        a.add(tmp)

if start_loop:
        loop_num = len(a) - start_loop
        sum_before_loop = sum(a[:start_loop])
        sum_loop = sum(a[start_loop:])* (N - start_loop)//loop_num
        sum_after_loop = sum(a[start_loop: start_loop+ (N - start_loop) % loop_num])
        print(int(sum_before_loop + sum_after_loop + sum_loop))
else:
        sum_before_loop = sum(a)
        print(sum_before_loop)

Submission status: Runtime Error

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

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

for len_9 in range(mn):
    if x in S: break
    S.add(x)
    A.append(x)
    sum_9 += x
    x = x*x % m

pre_len = A.index(x)
cyc_len = len(A) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(A[:pre_len])
cyc = sum_9 - pre
nxt = sum(A[pre_len: pre_len + nxt_len])

print(pre + cyc * cyc_num + nxt)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
print(last)
"""if last >= N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))
"""

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if last >= N:
  print(sum(ls_mod[:N]))
"""else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))
"""

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if fast >= N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if last - 1 > N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if last > N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if last >= N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if last >= N:
  print(sum(ls_mod[:N]))
else:
  shou = (N-fast) // diff
  amari = (N-fast) % diff
  print(sum(ls_mod[:fast])+sum([fast:])*shou+sum([fast:fast+amari]))

Submission status: Runtime Error

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 True:
    first_count += 1
    A2 = (A2**2)%M
    if A2 == target_value:
        break

roop_count = last_count-first_count

A3 = target_value
mass = A3
for i in range(roop_count-1):
    A3 = (A3**2)%M
    mass += A3

ans = X
A = X
for i in range(min(N,first_count)-1):
    A = (A**2)%M
    ans += A
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)