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: Runtime Error

Solution code:
n, x, m = map(int, input().split())
ans = 0
a = x
arr = []
for i in range(n):
  if a in arr:
    break
  else:
    arr.append(a)
  a = a ** 2 % m
f = sum(arr[:arr.index(a)])
r = sum(arr[arr.index(a):])
k = (n - arr.index(a)) // (len(arr) - arr.index(a))
b = sum(arr[arr.index(a): arr.index(a) + (n - (arr.index(a) + (len(arr) - arr.index(a)) * k))])
ans = f + r * k + b
print(ans)

Submission status: Runtime Error

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
#        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=x*n
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
if X == 1:
    print(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
if roop_count == 0:
    pass

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)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    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
if roop_count == 0:
    pass

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)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    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
print(first_count,last_count,target_value,mass)
if roop_count == 0:
    pass

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)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
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)

Submission status: Runtime Error

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)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
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)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
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)
d, m = divmod(N-len(tl), len(ttl))
ans += sum(ttl)*d+sum(ttl[:m])
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
check = [0]*(M+1)
check[X] += 1
A = X
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)

Submission status: Runtime Error

Solution code:

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

if x==0:
    print(0)
elif m==1:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    asumr=0
    air=ai
    for i in range(nr):
        asumr+=air
        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Runtime Error

Solution code:

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

if x==0:
    print(0)
elif n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    asumr=0
    air=ai
    for i in range(nr):
        asumr+=air
        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Runtime Error

Solution code:

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

if n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(m):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    asumr=0
    air=ai
    for i in range(nr):
        asumr+=air
        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
ida = [-1] * (m + 1)
a = [-1] * (m + 1)
sa = [-1] * (m + 1)
a[1] = x
sa[1] = x
ida[x] = 1
l_len = 1
l_start = 1
for i in range(2, m + 1):
    fx = a[i - 1] ** 2 % m
    if ida[fx] < 0:
        ida[fx] = i
        a[i] = fx
        sa[i] = sa[i - 1] + a[i]
    else:
        a[i] = fx
        l_start = a.index(fx)
        l_len = i - l_start
        break

    q = (n - l_start + 1) // l_len
    r = (n - l_start + 1) % l_len
if n == 1:
    ans = sa[1]
else:
    ans = (sa[l_start + l_len - 1] - sa[l_start - 1]) * q + sa[l_start + r - 1]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
ans = x
memo_array = [-1]*(m+1)
for i in range(1,n):
    ans = ans**2%m
    idx = memo_array[ans]
    if idx != -1:
        loop_num, mod = divmod((n-idx),(i-idx))
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*(loop_num)+np.sum(l[loop_start:loop_start+mod]))
        sys.exit()
    l = np.append(l,ans)
    memo_array[ans]=i
print(np.sum(l))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
ans = x
memo_array = [False]*(m+1)
for i in range(1,n):
    ans = ans**2%m
    if memo_array[ans]:
        loop_start = int(np.where(l==ans)[0])
        loop_num, mod = divmod((n-loop_start),(i-loop_start))
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*(loop_num)+np.sum(l[loop_start:loop_start+mod]))
        sys.exit()
    l = np.append(l,ans)
    memo_array[ans]=True
print(np.sum(l))

Submission status: Runtime Error

Solution code:

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

if n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(icnt):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    asumr=0
    air=ai
    for i in range(nr):
        asumr+=air
        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys

n,x,m = (int(i) for i in input().split())
l = np.array([x])
ans = x
memo_array = [False]*m
for i in range(1,n):
    ans = ans**2%m
    if memo_array[ans]:
        loop_start = int(np.where(l==ans)[0])
        loop_num, mod = divmod((n-loop_start),(i-loop_start))
        print(np.sum(l[:loop_start]) + np.sum(l[loop_start:])*(loop_num)+np.sum(l[loop_start:loop_start+mod]))
        sys.exit()
    l = np.append(l,ans)
    memo_array[ans]=True
print(np.sum(l))

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
if X == 0:
    print(0)
    exit(0)
t = X
A = [0]*(M+1)
A[X] = 1
B = [X]
k = 1
while True:
    X = (X*X)%M
    if X == 0 or k == N:
        print(sum(B))
        exit(0)
    elif A[X] != 0:
        s, e = A[X], k
        r = k-A[X]
        break
    else:
        A[X] = k
        B.append(X)
        k += 1
print(sum(B[:s])+((N-s)//r)*sum(B[s:e])+sum(B[s:s+(N-s)%r]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
t = X
A = [0]*(M+1)
A[X] = 1
B = [X]
k = 1
while True:
    X = (X*X)%M
    if X == 0 or k == N:
        print(sum(B))
        exit(0)
    elif A[X] != 0:
        s, e = A[X], k
        r = k-A[X]
        break
    else:
        A[X] = k
        B.append(X)
        k += 1
print(sum(B[:s])+((N-s)//r)*sum(B[s:e])+sum(B[s:s+(N-s)%r]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
t = X
A = [0]*(M)
A[X] = 1
B = [X]
k = 1
while True:
    X = (X*X)%M
    if X == 0 or k == N:
        print(sum(B))
        exit(0)
    elif A[X] != 0:
        s, e = A[X], k
        r = k-A[X]
        break
    else:
        A[X] = k
        B.append(X)
        k += 1
print(sum(B[:s])+((N-s)//r)*sum(B[s:e])+sum(B[s:s+(N-s)%r]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
t = X
A = [0]*(M)
A[X] = 1
B = [X]
k = 1
while True:
    X = (X*X)%M
    if X == 0:
        print(sum(B))
        exit(0)
    elif A[X] != 0:
        s, e = A[X], k
        r = k-A[X]
        break
    else:
        A[X] = k
        B.append(X)
        k += 1
print(sum(B[:s-2])+(N//r)*sum(B[s:e])+sum(B[:N%r]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
t = X
A = [0]*(M)
A[X] = 1
B = [X]
k = 1
while True:
    X = (X*X)%M
    if X == 0:
        print(sum(B))
        exit(0)
    elif A[X] != 0:
        s, e = A[X], k
        r = k-A[X]
        break
    else:
        A[X] = k
        B.append(X)
        k += 1
print((N//r)*sum(B[s:e])+sum(B[:N%r]))

Submission status: Runtime Error

Solution code:
n,x,m = map(int, input().split())
b = x%m
add = 0

# nがm以下なら全部足せば良い
ans = 0
if n <= m:
    for i in range(n):
        ans += b    
        b = pow(b,2,m)
    print(ans)
    exit()

# nがmより大のとき、効率化
cnt = 0
while 2 ** cnt < m:
    cnt += 1

# 位数と初期値を出す
s = set()
for i in range(m):
    if i < cnt:
        add += b
        tmp = b
    else:
        s.add(b)
    b = pow(b, 2, m)

if len(s) == 0:
    print(add)
    exit()
# cnt以降、和*位数+残りの和で計算
rest = (n-cnt)%len(s)
div = (n-cnt)//len(s)

rep = []
for i in range(len(s)):
    tmp = pow(tmp, 2, m)
    rep.append(tmp)

ans = add + sum(rep)*div + sum(rep[:rest])
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int, input().split())
b = x%m
add = 0

# nがm以下なら全部足せば良い
ans = 0
if n <= m:
    for i in range(n):
        ans += b    
        b = pow(b,2,m)
    print(ans)
    exit()

# nがmより大のとき、効率化
cnt = 0
while 2 ** cnt < m:
    cnt += 1

# 位数と初期値を出す
s = set()
for i in range(m):
    if i < cnt:
        add += b
        tmp = b
    else:
        s.add(b)
    b = pow(b, 2, m)
# cnt以降、和*位数+残りの和で計算
rest = (n-cnt)%len(s)
div = (n-cnt)//len(s)

rep = []
for i in range(len(s)):
    tmp = pow(tmp, 2, m)
    rep.append(tmp)

ans = add + sum(rep)*div + sum(rep[:rest])
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int, input().split())
b = x%m
add = 0

# nがm以下なら全部足せば良い
ans = 0
if n <= m:
    for i in range(n):
        ans += b    
        b = pow(b,2,m)
    print(ans)
    exit()

# nがmより大のとき、効率化
cnt = 0
while 2 ** cnt < m:
    cnt += 1

# 位数と初期値を出す
s = set()
for i in range(m):
    if i < cnt:
        add += b
        tmp = b
    else:
        s.add(b)
    b = pow(b, 2, m)
# cnt以降、和*位数+残りの和で計算
rest = (n-cnt)%len(s)
div = (n-cnt)//len(s)

rep = []
for i in range(len(s)):
    tmp = pow(tmp, 2, m)
    rep.append(tmp)

print(len(s),len(rep))
ans = add + sum(rep)*div + sum(rep[:rest])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X, mod = mapint()
first = set()
second = set()
in_loop = []
ans = 0
for i in range(min(10**5*2, N)):
    if X in first:
        if X in second:
            break
        in_loop.append(X)
        second.add(X)
    first.add(X)
    ans += X
    X = pow(X, 2, mod)
else:
    print(ans)

loop_len = len(in_loop)
rest = N-len(first)-len(in_loop)
ans += (rest//loop_len)*sum(in_loop)
amari = rest%loop_len
for i in range(amari):
    ans += in_loop[i]
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = 0
    for j in range(cy_st):
        if j == 0 :
            b = x
            ans2 += b
        else:
            b = (b**2)% mod
            ans2 += b
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    for i in range(cy_amari):
        b = (b**2)% mod
        ans3 += b

    print(ans2+ans3)
else:
    print(ans)

Submission status: Runtime Error

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

a = x
li = [a]
exists = dict()
for i in range(2, n + 1):
    a = a * a % m
    if a in exists:
        break
    li.append(a)
    exists[a] = i

ans = sum(li)
if i != n:
    loop, left = divmod(n - i + 1, i - exists[a])
    ans += loop * sum(li[exists[a]-1:]) + sum(li[exists[a]-1:exists[a]-1+left])
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = 0
    for j in range(cy_st):
        if j == 0 :
            b = x
            ans2 += b
        else:
            b = (a**2)% mod
            ans2 += b
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    for i in range(cy_amari):
        b = (b**2)% mod
        ans3 += b

    print(ans2+ans3)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = x
    a = x
    for j in range(1,cy_st):
        a = (a**2)% mod
        ans2 += a
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    for i in range(cy_amari):
        a = (a**2)% mod
        ans3 += a

print(ans2+ans3)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x

#ループの始まりを特定
while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch #ループの開始している配列の初めの数字
        break
    ch *= ch
    ch %= mod

#ループの始まりの配列の添え字を特定
for i in range(len(num)):
    if num[i] == st:
        stnum = i #ループ開始の最初の配列のの番号
        break
else:
    stnum = len(num) - 1


if 0 in num:
    ans = sum(num[:n])
else:
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum) #余り
        qu = (n-stnum)//(len(num)-stnum)  #商
    else:
        rest = n
        qu = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*sho
print(ans)

Submission status: Runtime Error

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

nxt = X
lst = []
dic = {}

for i in range(M):
    if nxt in dic:
        loop_st = dic[nxt]
        loop_ed = i - 1
        break

    lst.append(nxt)
    dic[nxt] = i

    nxt = (nxt ** 2) % M


v = N - loop_st
q, r = divmod(v, loop_ed - loop_st + 1)

pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])
print(pre_sum + loop_sum + post_sum)

Submission status: Runtime Error

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

l = []
l[0] = x

ans = x

for i in range(n):
    l[i] = (l[i-1]*l[i-1]) % m
    ans += l[i]

print(ans)

Submission status: Runtime Error

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

nxt = X
lst = []
dic = {}

for i in range(M):
    if nxt in dic:
        loop_st = dic[nxt]
        loop_ed = i - 1
        break

    lst.append(nxt)
    dic[nxt] = i

    nxt = (nxt ** 2) % M


v = N - loop_st
q, r = divmod(v, loop_ed - loop_st + 1)

pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])

Submission status: Runtime Error

Solution code:
N,X,M=list(map(int,input().split()))
C=[]
C.append(X)
for i in range(N):
    t=(C[i]**2)%M
    if t not in C:
        C.append(t)
    else:
        k=C.index(t)
        L=i-k+1
        break

Cinitial=C[0:k]
Crepeat=C[k:]
sumCrepeat=sum(Crepeat)
sumCinitial=sum(Cinitial)
S=(N-k)//L
print(sumCinitial+sumCrepeat*S+sum(Crepeat[i] for i in range((N-k)%L)))

Submission status: Runtime Error

Solution code:
N,X,M=list(map(int,input().split()))
C=[]
C.append(X)
for i in range(M+3):
    t=(C[i]**2)%M
    if t not in C:
        C.append(t)
    else:
        k=C.index(t)
        L=i-k+1
        break

Cinitial=C[0:k]
Crepeat=C[k:]
sumCrepeat=sum(C[i] for i in range(k:))
sumCinitial=sum(Cinitial)
S=(N-k)//L
print(sumCinitial+sumCrepeat*S+sum(Crepeat[i] for i in range((N-k)%L)))

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
ans=0
p=0
l=[x]
o=0
if x%m==0:
  print(x)
else:
  for i in range(1,n):
    s=(l[i-1]**2)%m
    if s==0:
      break
    if s in l:
      p=1
      o=list.index(s)
      break
    else:
      l.append(s)
  if p==1:
    
    t=sum(l[o:])
    k=(n-o)//(len(l)-1) #ループ何回回るか
    j=(n-o)%(len(l)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  else:
    print(sum(l))

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
ans=0
p=0
l=[x]
if x%m==0:
  print(x)
else:
  for i in range(1,n):
    s=(l[i-1]**2)%m
    if s==0:
      p=1
      break
    if s in l:
      p=2
      break
    else:
      l.append(s)
  if p==2:
    t=sum(l[1:])
    k=(n-1)//(len(l)-1) #ループ何回回るか
    j=(n-1)%(len(l)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  elif p==1:
    print(sum(l))
  else:
    print(sum(l))

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
a = [0] * (n+1)
sa = [0] * (n+1)

a[1] = x
sa[1] = x
for i in range(2, n+1):
    a[i] = a[i-1]**2 % m
    sa[i] = sa[i-1] + a[i]
print(sa[n])

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=x
for i in range(0,n):
  p=(a*a)%m
  w=w+p
  a=p
print(w)

Submission status: Runtime Error

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
loop_len = i - Xd[x]
# print(loop_len)
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    # print(S)
    #loop_num = (N - i) // loop_len
    # print(loop_num)
    #ans += loop_num * S
    #m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    #ans += C[Xd[x]+m] - C[Xd[x]]

# print(S)

print(ans)

Submission status: Runtime Error

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
loop_len = i - Xd[x]
# print(loop_len)
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    # print(S)
    loop_num = (N - i) // loop_len
    # print(loop_num)
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    #ans += C[Xd[x]+m] - C[Xd[x]]

# print(S)

print(ans)

Submission status: Runtime Error

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
loop_len = i - Xd[x]
# print(loop_len)
if loop_len > 0:
    #S = C[i] - C[Xd[x]]
    # print(S)
    loop_num = (N - i) // loop_len
    # print(loop_num)
    #ans += loop_num * S
    m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    ans += C[Xd[x]+m] - C[Xd[x]]

# print(S)

print(ans)

Submission status: Runtime Error

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
S = C[i] - C[Xd[x]]
# print(S)
loop_len = i - Xd[x]
# print(loop_len)
if loop_len > 0:
    loop_num = (N - i) // loop_len
    # print(loop_num)
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    ans += C[Xd[x]+m] - C[Xd[x]]

# print(S)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

if M == 0:
    print(X)
    exit()

ans = X
x = X

m = []
for i in range(0, M+1):
    m.append((i ** 2) % M)

C = [x]
Xd = defaultdict(lambda: -1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    
    x = m[x]

    if Xd[x] > -1:
        # print(i)
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
S = C[i-1] - C[Xd[x]-1]
loop_len = i - Xd[x]
if loop_len > 0:
    loop_num = (N - i) // loop_len
    # print(loop_num)
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    ans += C[Xd[x]+m-1] - C[Xd[x]-1]

# print(S)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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

ans = X
x = X

m = []
for i in range(0, M+1):
    m.append((i ** 2) % M)

C = [x]
Xd = defaultdict(lambda: -1)
Xd[x] = 0
Xl = [x]

for i in range(1, N):
    
    x = m[x]

    if Xd[x] > -1:
        # print(i)
        break
    Xd[x] = i
    Xl.append(x)
    ans += x
    C.append(ans)

# print(Xl)
# print(C)
# print(Xd[x], i)
S = C[i-1] - C[Xd[x]-1]
loop_len = i - Xd[x]
if loop_len > 0:
    loop_num = (N - i) // loop_len
    # print(loop_num)
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    # print(ans)
    # print(m)
    ans += C[Xd[x]+m-1] - C[Xd[x]-1]

# print(S)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# X%M + X^(2)%M + X^(4)%M + X^(8)%M ...
# 重要な性質X^(k)%M for k=[0,M-1]は循環する
# X^(k) = X^(c*M+k) (mod M)
# = X^(k%M)

# X(0%M)%M + X^(2%M)%M + X^(4%M)%M + X^(8%M)%M ...

# あまりの循環テーブルT
# T[0%M] + T[2%M] + T[4%M] ...
# T[2^(0)%M] + T[2^(1)%M] + T[2^(2)%M] ...(M)  ... (循環するので×だけ) (N%M) ...
# N//M回循環する
# 2のべき乗をMで割ったテーブル
# 正確には違ったね

# (X^2*k) = (X^2)^k
# (X^2)^kが循環する

N, X, M = ints()
A = [X]
for i in range(M):
    A.append(pow(A[-1], 2, M))  # 循環は単純ではないのか

# 早期終了
if N < M:
    exit(sum(A[:N]))

# 非ループ部分とそれ以外の検出
visited = set()
for i in range(M):
    if A[i] in visited:
        len_total = i
        break
    visited.add(A[i])
# i番目の要素が初めて出てくるところを改めて探す
s = A.index(A[len_total])
cut = A[:s]
loop = A[s:len_total]
# print(cut)
# print(loop)
# print(A) #ok
ans = sum(cut)
N -= len(cut)

ans += sum(loop) * (N // len(loop))
ans += sum(loop[:N % len(loop)])
print(ans)