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
arr=[]
now=X
def mondai(A):
    return A%M
for i in range(N):
    ans+=mondai(now)
    if mondai(now) in arr:
        break
    arr.append(mondai(now))
    now=mondai(now**2)
amari=len(arr[2:])
kari=arr[2:]
kaisu=int((N-len(arr))/amari)
hasu=(N-len(arr))%amari
if kaisu>0:
    ans+=kaisu*sum(kari)
if hasu>0:
    ans+=kari[hasu-1]

print(ans)

#print(arr)

Submission status: Runtime Error

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

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, X, M = map(int, input().split())

def mod(x):
    return x % M

a = X

i = 0

ans = 0
last = -1

dic = []

while a != 0 and i < N:
    ans += a
    a = mod(a * a)
    i += 1    

    if a in dic:
        last = dic.index(a)
        break

    dic.append(a)


if i != N and dic[last] != 0:
    tdic = dic[last:]
    if N - i >= len(tdic):
        sdic = sum(tdic)
        ans += sdic * ((N - i) // len(tdic))

    for j in range((N - i) % len(tdic)):
        ans += tdic[j]

print(ans)

Submission status: Runtime Error

Solution code:

if __name__ == '__main__':
    n, k,x = map(int, input().split())
    mod = 998244353
    ans = 0
    index=0
    a= k %x
    dict={}
    for i in range(n):
        if a not in dict.values():
            ans += a
            index += 1
            dict[i]=a
            a = a*a % x
        else:
            break

    key = [k for k, v in dict.items() if v == a][0]
    count=len(dict) -key
    n2 = n- len(dict)
    n3 = n2 // count
    n4 = n2 % count
    count2=0
    if key <= n//2:
        for i in range(key):
            count2+=dict[i]
        ans+=n3*(ans-count2)
    else:
        for i in range(count-key):
            count2+=dict[count-i]
        ans+=n3*(ans-count2)


    for i in range(n4):
        ans+=dict[key+i]

    print(ans)

Submission status: Runtime Error

Solution code:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Submission status: Runtime Error

Solution code:

if __name__ == '__main__':
    n, k,x = map(int, input().split())
    mod = 998244353
    ans = 0
    index=0
    a= k %x
    dict={}
    for i in range(n):
        if a not in dict.values():
            ans += a
            index += 1
            dict[i]=a
            a = a*a % x
        else:
            break

    key = [k for k, v in dict.items() if v == a][0]
    count=len(dict) -key
    n2 = n- len(dict)
    n3 = n2 // count
    n4 = n2 % count
    count2=0
    if key <= n//2:
        for i in range(key):
            count2+=dict[i]
        ans+=n3*(ans-count2)
    else:
        for i in range(n-key):
            count2+=dict[n-i]
        ans+=n3*(ans-count2)


    for i in range(n4):
        ans+=dict[key+i]

    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n,x,m = map(int,input().split())
    if m == 0:
        print(0)
        return
    t = [x]
    k = -1
    for _ in range(n):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    s = t.index(k)
    if s == -1:
        print(sum(t))
        return
    else:
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def f(a):
    return a * a % M


a = X

map = {}
ary = [a]
map[a] = 1

sub = [0, a]
last_sub = a

def naive(a):
    total = a
    ary = [a]
    for i in range(1, N):
        a = f(a)
        ary.append(a)
    return ary
    
#n_ary = naive(X)
#print(n_ary)
#print(sum(n_ary))

count = 1
for i in range(1, N):
    a = f(a)
    if a == 0:
        break
    if a in map:
        break
    else:
        map[a] = i
    count += 1
    last_sub += a
    sub.append(last_sub)

if a == 0:
    print(sub[-1])
    exit()

j = map[a]

#print(sub)
#print(j)
unit = sub[-1] - sub[j]
#print(unit)

l = count
i = (N - j) % (l - j)
d = (N - j) // (l - j)

#i = N % l
#d = N // l

#print(len(sub), i, j)
print(unit * d + sub[i + j])

#print(sub[-1] * (d + 1) * d // 2 + sub[i])

Submission status: Runtime Error

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

A = [x]
where = {x: 0}
for i in range(1, n):
    a = A[-1]**2 % m
    if a in where:
        break
    where[a] = i
    A.append(a)

perstart = where[a]
res = sum(A)
rem = n - len(A)
per = len(A) - perstart
res += rem//per*sum(A[perstart:perstart+per])
res += sum(A[perstart:perstart + (rem%per)])

print(res)

Submission status: Runtime Error

Solution code:
N,X,M=map(int,input().split())
ans=0
arr=[]
now=X
def mondai(A):
    return A%M
for i in range(N):
    ans+=mondai(now)
    if mondai(now) in arr:
        break
    arr.append(mondai(now))
    now=mondai(now**2)
amari=len(arr[2:])
kari=arr[2:]
kaisu=int(N/amari)
hasu=N%amari
if kaisu>0:
    ans+=kaisu*sum(kari)
if hasu>0:
    ans+=kari[hasu-1]

print(ans)

#print(arr)

Submission status: Runtime Error

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

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

ls = []
s = set([])

a = X
s.add(a)
ls.append(a)

while True:
    a = pow(a, 2, M)

    if a in s:
        ind = ls.index(a)
        break
    elif len(ls) == N:
        break
    else:
        s.add(a)
        ls.append(a)

new_ls = ls[ind:len(ls)]

ans = sum(ls)

if len(new_ls) != 0:
    ans += sum(new_ls) * (max(0, (N - len(ls))) // len(new_ls))

    tmp = max(0, (N - len(ls))) % len(new_ls)

    if tmp != 0:
        for i in range(tmp):
            ans += new_ls[i % len(new_ls)]

print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
tmp=x
L=[]
Flag=False
for i in range(n):
    tmp=tmp**2%m
    if tmp==0:
        Flag=True
        break
    elif tmp not in L:
        L.append(tmp)
    else:
        break
if Flag:
    ans=x+sum(L)
else:
    times=(n-len(L))//len(L)
    loss=(n-len(L))%len(L)
    ans=x+sum(L[cnt:])*times
    for i in range(loss):
          ans+=L[cnt:][i]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N, X, M = map(int, input().split())
A = [X]
ans = X
if N>1:
    temp = 1
    dic[X]=temp
    for i in range(2, N+1):
        a = A[-1]*A[-1]%M
        if dic[a]>0:

            fir = dic[a]
            break
        A.append(a)
        ans+=a
        temp+=1
        dic[a]=temp
    T = temp-fir+1#周期
    Tsum = 0 #周期の和
    TempSum = 0 #後半あまりの和
    M=N-fir+1 # 先頭のぞく 
    amari = M%T # 後半あまり
    for k in dic:
        if dic[k]>=fir and dic[k]<=temp:
            Tsum+=k
        if dic[k]>=fir and dic[k]<fir+amari:
            TempSum += k
    ans+=TempSum
    ans+=Tsum*(M//T-1)
    print(ans)
else:
    print(ans)

Submission status: Runtime Error

Solution code:

if __name__ == '__main__':
    n, k,x = map(int, input().split())
    mod = 998244353
    ans = 0
    index=0
    a= k %x
    dict={}
    for i in range(n):
        if a not in dict.values():
            ans += a
            index += 1
            dict[i]=a
            a = a*a % x
        else:
            break

    key = [k for k, v in dict.items() if v == a][0]
    count=len(dict) -key
    n2 = n- len(dict)
    n3 = n2 // count
    n4 = n2 % count
    count2=0
    for i in range(key):
        count2+=dict[i]
    ans+=n3*(ans-count2)

    for i in range(n4):
        ans+=dict[key+i]

    print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
A = [X]
for i in range(N):
    An = A[-1]**2 % M
    if An in A:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
A = [100001]*(2*(10**5)+100)
A[1] = X
S = {X}
ans = X
for i in range(2,min(2*M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  #print(i)
#[print(A[i]) for i in range(6)]
  
if i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  if i == j:
    print(ans)
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  #print(j,k,l)
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)

Submission status: Runtime Error

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

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

ls = []
s = set([])

a = X
s.add(a)
ls.append(a)

while True:
    a = pow(a, 2, M)

    if a in s:
        ind = ls.index(a)
        break
    elif len(ls) == N:
        break
    else:
        s.add(a)
        ls.append(a)

new_ls = ls[ind:len(ls)]

ans = sum(new_ls) * (max(0, (N - len(ls))) // len(new_ls)) + sum(ls)

tmp = max(0, (N - len(ls))) % len(new_ls)

if tmp != 0:
    for i in range(tmp):
        ans += new_ls[i % len(new_ls)]

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N, X, M = map(int, input().split())
A = [X]
ans = X

temp = 1
dic[X]=temp
for i in range(2, N+1):
    a = A[-1]*A[-1]%M
    if dic[a]>0:
        
        fir = dic[a]
        break
    A.append(a)
    ans+=a
    temp+=1
    dic[a]=temp
T = temp-fir+1#周期
Tsum = 0 #周期の和
TempSum = 0 #後半あまりの和
M=N-fir+1 # 先頭のぞく 
amari = M%T # 後半あまり
for k in dic:
    if dic[k]>=fir and dic[k]<=temp:
        Tsum+=k
    if dic[k]>=fir and dic[k]<fir+amari:
        TempSum += k
ans+=TempSum
ans+=Tsum*(M//T-1)
print(ans)

Submission status: Runtime Error

Solution code:
N,x,MOD = map(int, input().split())
s = x
t_s = 0
for i in range(2,MOD + 1):
  if N == 1:
    break
  x = (x*x)%MOD
  s += x
  if i == N:
    break
res = N - i
init = x
t_s = x
cnt = 1
for i in range(MOD):
  if N == 1:
    break
  x = (x*x)%MOD
  if x == init:
    break
  cnt += 1
  t_s += x
if not N == 1:
  bai = res // cnt
  res = res %  cnt
  s += t_s * bai
if res > 0:
  for i in range(res):
    x = (x*x)%MOD
    s += x
print(s)

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:
      break
    else:
      l.append(s)
  if p==0:
    t=sum(l[1:])
    k=n//(len(l)-1)
    j=n%(len(1)-1)
    ans=x+t*k+sum(l[1:j+1])
    print(ans)
  else:
    print(sum(l))

Submission status: Runtime Error

Solution code:
def main():
    n,x,m = map(int,input().split())
    t = [x]
    k = -1
    for _ in range(n):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    s = t.index(k)
    if s == -1:
        print(sum(t))
        return
    else:
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
# 一定回数を経ると循環するので最後にかければよい
loop=list()
app = [0]*m
last = -1
a_i = x
while 1:
  a_i = (a_i**2)%m
  if a_i in (0,1) or app[a_i]:
    # あまりが0か1になったらそのあとはずっと一緒
    # もしくはloopの端にきたらloop開始
    last = a_i
    break
  else:
    app[a_i] = len(loop)
    loop.append(a_i)
    if len(loop) > n:
      break
# 答の計算
ans=x
if last < 1:
  ans += sum(loop) + last * (n - len(loop) - 1)
else:
  # ループの端までは普通に足す
  ans += sum(loop[:app[last]])
  #print(ans)
  # ループの中を累計で足す
  ans += sum(loop[app[last]:]) * ((n-1) // (len(loop)-app[last]))
  #print(ans)
  # 余りを足す
  ans += sum(loop[app[last]:((n-1) % (len(loop)-app[last]))])
print(ans)
#print(*loop)

Submission status: Runtime Error

Solution code:
def main():
    n,x,m=map(int,input().split())
    visited=[0]*m
    visit_sum=[0]*m
    i=1
    sm=x
    visited[x]=1
    visit_sum[x]=x
    work=x
    while i < n:
        work**=2
        work%=m
        sm+=work
        i+=1
#        print(sm,work)
        if not visited[work]:
            visited[work]=i
            visit_sum[work]=sm
        else :
            break
    else :
        print(sm)
        exit()
    loop_sum=sm-visit_sum[work]
    loop_num=i-visited[work]
    initial_sum=visit_sum[visited.index(visited[work]-1)]

    out=initial_sum
#    print(out)
    out+=(n-visited[work]+1)//loop_num*loop_sum
#    print(out)
    work_num=(n-visited[work]+1)%loop_num
    if work_num>0:
        out+=visit_sum[visited.index(visited[work]-1+work_num)]-initial_sum
    print(out)

main()

Submission status: Runtime Error

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

seen = {}
ans = p%m
seen[p%m]=1
T = {}
T[1] = ans
last_p = p%m

r = 0

if n==1:
  print(p%m)
else:
  for i in range(2,m+1000):
    p = p ** 2
    p = p % m
    
    if p not in seen:
      seen[p]=i
    else:
      r = i-seen[p]
     # print(r, i, seen[p], p)
      last_p = p
      break
    
    ans += p
    T[i] = ans
    
    #last_p = p
    
    if i==n:
      print(ans)
      exit()
    
    
temp = T[seen[p]-1]
#print(temp)
ans -= temp
n -= seen[p]
#print(492443256176507)
#print(p, 'p')
    
k = n//r
ans *= k
ans += temp

n = n % r
if n==0:
  print(ans+last_p)
  exit()

for i in range(1,m+1000):
  p = p ** 2
  p = p % m
  ans += p
  if i==n:
    print(ans+last_p)
    exit()

Submission status: Runtime Error

Solution code:

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

ans_list = [X]

for i in range(1,N):
    ans = ans_list[-1]**2%M
    if ans in ans_list:
        break
    else:
        ans_list.append(ans)

st_index = ans_list.index(ans)

if st_index == N-1:
    print(sum(ans_list))
else:
    total = sum(ans_list[:st_index])
    N -= st_index
    syo = N//(i-st_index)
    mod = N%(i-st_index)

    total += sum(ans_list[st_index:])*syo
    total += sum(ans_list[st_index:st_index+mod])
    print(total)

Submission status: Runtime Error

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

a_i = X
seq = [0] * N
seq[0] = X

memo = {a_i: 0}
for i in range(1, N):
    a_i = (a_i ** 2) % M
    seq[i] = a_i

    if a_i in memo:
        j = memo[a_i]
        interval = i - j
        base_sum = sum(seq[:j])
        mod = (N - i) % interval
        if mod == 0:
            repeated_sum = sum(seq[j:i]) * ((N - i) // interval)
        else:
            repeated_sum = sum(seq[j:i]) * ((N - i) // interval) + sum(seq[j:j + mod])
        print(base_sum + repeated_sum)
        exit()
    else:
        memo[a_i] = i

print(sum(seq))

Submission status: Runtime Error

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X
idx == -1
idx1 = -1
for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx == -1 and idx1 == -1):
    print(sum(rec))
elif(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, X, M = map(int, input().split())
    NN = N
    li = []
    while X not in li:
        if N != 0:
            li = li + [X]
            X = X ** 2 % M
            N -= 1
        else:
            print(sum(x for x in li))
            break

    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li[i] for i in range(s)) + sum(li[i] for i in range(s, len(li))) * q + sum(li[i] for i in range(s, s + r)))


main()

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
A = [100001]*(10**5+1)
A[1] = X
S = {X}
ans = X
for i in range(2,min(2*M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  #print(i)
#[print(A[i]) for i in range(6)]
  
if i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  if i == j:
    print(ans)
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  #print(j,k,l)
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
rem = [0] * m
chk = [0] * (m + 1)
rem[0] = x
for i in range(1,m):
  rem[i] = (rem[i - 1] ** 2) % m
  if chk[rem[i - 1] ** 2 % m] > 1:
    temp1 = (rem[i - 1] ** 2) % m
    temp2 = i
  else:
    temp1 = (rem[i - 1] ** 2) % m
    temp2 = i

for i in range(m):
  if rem[i] == temp1:
    temp3 = i
    break

if temp2 != temp3:
  num = (n - temp3) // (temp2 - temp3)
  S = sum(rem[:temp3]) + sum(rem[temp3:temp2]) * num + sum(rem[temp3:n - (num * (temp2 - temp3))])
  print(S)
else:
  print(sum(rem))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def main():
    n,x,m = map(int,input().split())
    d = defaultdict(bool)
    t = [x]
    k = -1
    for _ in range(n):
        x = x**2 % m
        if d[x]:
            k = x
            break
        else:
            d[x] = True
        t.append(x)
    s = t.index(k)
    if s == -1:
        print(sum(t))
        return
    else:
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * m
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)
ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Submission status: Runtime Error

Solution code:
N,X,M=map(int,input().split())
dist=[0 for i in range(M)]
A=X
loopin=-1
loopout=-1
ans=[0]
for i in range(N+1):
    if dist[A]!=0:
        loopin=dist[A]
        loopout=i
        ans.append(ans[-1]+A)
        break
    else:
        dist[A]=i
        ans.append(ans[-1]+A)
        A=(A*A)%M
if loopin==-1:
    print(ans[N])
#print(roopin,roopout)
#print(ans)
A=X
loop=loopout-loopin
def solve(l,r):
    assert 0<=l and l<=r
    if r<=loopout:
        return ans[r]-ans[l]
    if l<loopin:
        return ans[loopin]-ans[l]+solve(loopin,r)
    x=(l-loopin)//loop
    y=(r-loopin)//loop
    #x*loop+loopin<=l<(x+1)*loop+loopin
    #y*loop+loopin<=r<(y+1)*loop+loopin
    if x==y:
        return ans[r-y*loop]-ans[l-x*loop]
    #以降はx<y
    tmp1=ans[l-x*loop]-ans[loopin]
    tmp2=(ans[loopout]-ans[loopin])*(y-x)
    tmp3=ans[r-y*loop]-ans[loopin]
    #print(l,r,x,y,tmp1,tmp2,tmp3)
    return tmp1+tmp2+tmp3
print(solve(0,N))

Submission status: Runtime Error

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

table=[-1]*(M**2+1)

ans=0
for i in range(N):
    ans += X
    X = X**2
    if table[X] != -1:
        X = table[X]
    else:
        old_x=X
        X %= M
        table[old_x]=X
print(ans)

Submission status: Runtime Error

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    A = [-1 for i in range(M)]
    A[0] = X

    for i in range(1,M):
        temp = A[i-1] ** 2
        temp %= M
        if temp in A:
            start = A.index(temp)
            end = i - 1
            break
        A[i] = temp

    L = end - start + 1
    straight = [0 for i in range(start)]
    loop = [0 for i in range(L)]

    for i in range(start):
        straight[i] = straight[i-1] + A[i]

    for i in range(L):
        loop[i] = loop[i-1] + A[start+i]

    res = 0

    if N >= start:
        res += straight[-1]
        N -= start
    else:
        res += straight[N-1]
        N = 0

    res += (N // L) * loop[-1]

    if N % L != 0:
        res += loop[N % L - 1]

    print(res)



main()

Submission status: Runtime Error

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X

for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
x=int(input())
m=int(input())
a=x
sum=x
for i in range(2,n+1):
  a=a*a%m
  sum=sum+a
 print(sum)

Submission status: Runtime Error

Solution code:
n=list(map(int,input().split()))
import numpy as np
b = n[1]
z = n[2]
a = 0
result = b
next_in = b**2
while a<n[0]:
    if next_in < z:
        result += next_in
        next_in = next_in**2
    elif next_in > z:
        next_in = np.mod(next_in,z)
        result += next_in
        next_in = next_in**2
    else:
        next_in = next_in**2
    a += 1
print(result)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
tmp=x
L=[x]
for i in range(n):
    tmp=tmp**2%m
    if tmp not in L:
        L.append(tmp)
    else:
        cnt=L.index(tmp)
        break
times=(n-len(L[:cnt]))//len(L[cnt:])
loss=(n-len(L[:cnt]))%len(L[cnt:])
ans=sum(L[:cnt])+sum(L[cnt:])*times
for i in range(loss):
      ans+=L[cnt:][i]
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

data = [-1]*(m)

ans = x
data[x] = 0
count = 0
num = x

flag = 0
while(count < n-1):
    count += 1
    num = (num**2) % m
    if data[num] == -1 or flag == 1:
        data[num] = (count, ans)
        ans += num
    else:
        diff = ans-data[num][1]
        kaisuu = count - data[num][0]

        x = (n-(count)-1)//kaisuu

        count += kaisuu*x
        ans += diff*x
        flag = 1

# print(count, n)
# print(flag, ans)
print(ans)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
A = [100001]*(10**5+1)
A[1] = X
S = {X}
ans = X
for i in range(2,min(M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  #print(i)
#[print(A[i]) for i in range(6)]
  
if i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  #print(j,k,l)
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)

Submission status: Runtime Error

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

dp = [-1]*(10**5+2)
nums = [-1]*(10**5+2)
nums[x] = 1

dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    x = num[bef]
    print(r[min(len(r), n)])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )

Submission status: Runtime Error

Solution code:
import sys

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

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X

for i in range(N):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

Submission status: Runtime Error

Solution code:
N,x,MOD = map(int, input().split())
s = x
t_s = 0
for i in range(2,MOD + 1):
  x = (x*x)%MOD
  s += x
  if i == N:
    break
res = N - i
init = x
t_s = x
cnt = 1
for i in range(MOD):
  x = (x*x)%MOD
  if x == init:
    break
  cnt += 1
  t_s += x
bai = res // cnt
res = res %  cnt
s += t_s * bai
if res > 0:
  for i in range(res):
    x = (x*x)%MOD
    s += x
print(s)

Submission status: Runtime Error

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

dp = [-1]*(10**5+2)
nums = [-1]*(10**5+2)
nums[x] = 1
dp[0] = 0
dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    x = num[bef]
    if x >= n:
        print(r[n])
    else:
        print(r[-1])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )

Submission status: Runtime Error

Solution code:
n=list(map(int,input().split()))
import numpy as np
b = n[1]
z = n[2]
result = b
next_in = pow(b,2)
for i in range(b-1):
    if next_in < z:
        result += next_in
        next_in = pow(next_in,2)
        continue
    elif next_in > z:
        next_in = np.mod(next_in,z)
        result += next_in
        next_in = pow(next_in,2)
        continue
    else:
        next_in = pow(next_in,2)
        continue
print(result)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x,m = list(map(int, input().split()))
v = x
seen = [0]*m
c = 0
val = 0
count = 0
tmp = 0
if n>m:
    for i in range(m):
        if seen[v]==2:
            break
        if seen[v]==1:
            count += 1
            tmp += v
        else:
            val += v
            c += 1
        seen[v] += 1
        v = (v**2)%m
    ans = val + ((n-c)//count) * tmp
    for i in range((n-c)%(count)):
        ans += v
        v = (v**2)%m
else:
    ans = 0
    v = x
    for i in range(n):
        ans += v
        v = (v**2)%m
print(ans)

Submission status: Runtime Error

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

dp = [-1]*(10**5+2)
nums = [-1]*(10**5+2)
nums[x] = 1
dp[0] = 0
dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    x = num[nex]
    if x >= n:
        print(r[n])
    else:
        print(r[-1])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
A = [X]
for i in range(1,N):
    A += [((A[i-1])**2)%m]

print(sum(A))

Submission status: Runtime Error

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

dp = [-1]*(10**5+2)
nums = [-1]*(10**5+2)
nums[x] = 1
dp[0] = 0
dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    x = num[nex]
    if x >= n:
        print(r[-1])
    else:
        print(r[n])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex])
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
exist = [0] * (m+1)
ans = 0
imamade = []
cnt = 0
for i in range(1,n+1):
    if exist[x] == 1:
        break
    else:
        ans += x
        exist[x] = 1
        imamade.append(x)
        x *= x
        x %= m
        cnt += 1
    if i == n-1:
        print(ans)
        exit()
num = imamade.index(x)
print(sum(imamade[:num]) + sum(imamade[num:]) * ((n-num) // (cnt-num)) + sum(imamade[num:num+((n-num) % (cnt-num))]))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
lis = [0]*M
lis[0] = X
check = [-1]*M
check[X] = 0
for i in range(1,M):
  lis[i] = pow(lis[i-1],2,M)
  if check[lis[i]]>=0:
    cyc = i-check[lis[i]]
    start = check[lis[i]]
    break
  check[lis[i]] = i
from itertools import groupby, accumulate, product, permutations, combinations
cum = list(accumulate(lis))
cyc_cum = cum[-1]-cum[start]
if N-1<=start+cyc:
  ans = cum[N-1]
else:
  ans = cyc_cum*((N-1-start)//cyc)+cum[(N-1-start)%cyc+start]
print(ans)

Submission status: Runtime Error

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X

for i in range(N):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

Submission status: Runtime Error

Solution code:
N,x,MOD = map(int, input().split())
s = x
t_s = 0
for i in range(2,MOD + 1):
  x = (x*x)%MOD
  s += x
  if i == N:
    break
res = N - i
init = x
t_s = x
cnt = 1
for i in range(0,MOD):
  x = (x*x)%MOD
  if x == init:
    break
  cnt += 1
  t_s += x
bai = res // cnt
res = res %  cnt
s += t_s * bai
if res > 0:
  for i in range(res):
    x = (x*x)%MOD
    s += x
else:
  pass
print(s)

Submission status: Runtime Error

Solution code:
def main():
	N, X, M = [int(a) for a in input().split(" ")]
	used_r = [0] * (M - 1)
	r = [-1, X]
	used_r[X] = 1
	loop_start_elm = -1
	loop_start_n_2 = -1
	for i in range(M):
		A = r[-1]
		B = (A * A) % M
		if used_r[B] == 0:
			r.append(B)
			used_r[B] = 1
		else:
			loop_start_elm = B
			loop_start_n_2 = i + 2
			break
	loop_start_n = r.index(B)

	s1 = sum(r[:loop_start_n]) + 1
	s2 = sum(r[loop_start_n:loop_start_n_2])
	loop_len = loop_start_n_2 - loop_start_n
	loop_n = int((N - loop_start_n + 1) / loop_len)
	rest_n = (N - loop_start_n + 1) % loop_len
	s3 = sum(r[loop_start_n:(loop_start_n + rest_n)])
	print(s1 + s2 * loop_n + s3)

main()