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

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

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

if len(A)==n:
    print(su)

else:



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

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

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

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

    print(e+h+f)

Submission status: Runtime Error

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

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

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

if len(A)==N:
    print(su)

else:



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

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

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

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

    print(e+h+f)

Submission status: Runtime Error

Solution code:
#周期m以下

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

used = [0]*(m+1)
used_list=[]
pre=x

flag0=False
s=-1;t=-1
for i in range(m+1):
    if pre==0:
        flag0=True
        break
    now=(pre*pre)%m
    if used[pre]:
        s=used[pre]
        break
    used[pre]=i
    used_list.append(pre)
    pre=now
    
l=len(used_list[s:])
ans=sum(used_list[:s])+sum(used_list[s:])*((n-s)//l)+sum(used_list[s:s+(n-s)%l])
if not flag0:
    print(ans)
else:
    print(sum(used_list))

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
B = [0 for i in range(M+1)]
C = [0 for i in range(M)]
ans = 0
f = 0
for i in range(1, N+1):
  B[i] = B[i-1] + X
  if C[X] != 0:
    ans += ((N-C[X]+1) // (i-C[X])) * (B[i-1] - B[C[X]-1])
    ans += B[C[X] + (N-C[X]+1) % (i-C[X]) - 1]
    f = 1
    break
  else:
    C[X] = i
  X = (X * X) % M
if f == 1:
  print(ans)
else:
  print(B[N])

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
B = [0 for i in range(M+1)]
C = [0 for i in range(M)]
ans = 0
f = 0
for i in range(1, N+1):
  B[i] = B[i-1] + X
  if C[X] != 0:
    ans += ((N-C[X]+1) // (i-C[X])) * (B[i-1] - B[C[X]-1])
    ans += B[C[X]+(N-C[X]+1)%(i-C[X])-1]
    f = 1
    break
  else:
    C[X] = i
  X = X * X % M
if f == 1:
  print(ans)
else:
  print(B[N])

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin
import copy

def main():
    input = stdin.readline
    n, x, m = map(int, input().split())
    a = np.array([x], dtype=np.int64)
    h = {}
    h[x] = 0
    t = 0
    for i in range(n - 1):
        t = a[i] * a[i] % m
        if t in h:
            break
        h[t] = 0
        a = np.append(a, t)
    b = copy.deepcopy(a)
    a = a[:np.where(a == t)[0][0]]
    b = np.setdiff1d(b, a)
    ans = sum(a)
    if len(b) > 0:
        ans += sum(b) * ((n - len(a)) // len(b))
        ans += sum(b[0: (n - len(a)) % len(b)])
    print(int(ans))
main()

Submission status: Runtime Error

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from collections import OrderedDict
def solve(N,X,M):
    A=X
    ans=A
    seen=set()
    order_seen=[]
    for i in range(2,N+1):
        A=f(A,M)
        if i!=2:
            if A not in seen:
                seen.add(A)
                order_seen.append(A)
            else:  # If A has already been seen we are just going to repeat so break out of the loop.
                i-= 1 # Correcting factor for fact that when we break out of the loop we go one above with i
                break
        if A==0:   # If A=0 it will repeat forever.
            return ans
        ans+=A
    n=len(order_seen)
    N-=i
    mult_factor=N//n
    total_sum_seen=sum(order_seen)
    ans+=(total_sum_seen*mult_factor)
    number_remaining=N%n
    for i in range(number_remaining):
        ans+=order_seen[i]
    return ans

# The function for the recurrence relation.  A_n+1=A_n^2%M
def f(A,M):
    return A**2%M

N,X,M=readMap()
print(solve(N,X,M))

Submission status: Runtime Error

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from collections import OrderedDict
def solve(N,X,M):
    A=X
    ans=A
    seen=set()
    order_seen=[]
    for i in range(2,N+1):
        A=f(A,M)
        if i!=2:
            if A not in seen:
                seen.add(A)
                order_seen.append(A)
            else:  # If A has already been seen we are just going to repeat so break out of the loop.
                break
        if A==0:   # If A=0 it will repeat forever.
            return ans
        ans+=A
    n=len(order_seen)
    i-=1 # Correcting factor for fact that when we break out of the loop we go one above with i
    N-=i
    mult_factor=N//n
    total_sum_seen=sum(order_seen)
    ans+=(total_sum_seen*mult_factor)
    number_remaining=N%n
    for i in range(number_remaining):
        ans+=order_seen[i]
    return ans

# The function for the recurrence relation.  A_n+1=A_n^2%M
def f(A,M):
    return A**2%M

N,X,M=readMap()
print(solve(N,X,M))

Submission status: Runtime Error

Solution code:
n,x,m=list(map(int,input().split()))
if m==1:
    print(x)
else:
    d=[-1]*(m-1)
    j=1
    s=x
    a=[]
    a.append(x)
    while j<n:
        x=x**2
        x%=m
        if d[x]!=-1:
            break
        else:
            d[x]=j
        s+=x
        a.append(s)
        j+=1
    ##print(d[x],j,s,a[d[x]-1])    
    if j!=d[x] and n>j:
    
        s+=(n-j)//(j-d[x])*(s-a[d[x]-1])
    #print(s)
        if (n-j)%(j-d[x])!=0:
        #print((n-d[x]),(j-d[x]))
            s+=a[d[x]-1+(n-j)%(j-d[x])]-a[d[x]-1]
    print(s)

Submission status: Runtime Error

Solution code:
n,x,m=list(map(int,input().split()))
if m==1:
    print(x)
else:
    d=[-1]*(m-1)
    j=1
    s=x
    a=[]
    a.append(x)
    while j<n:
        x=x**2
        x%=m
        if d[x]!=-1:
            break
        else:
            d[x]=j
        s+=x
        a.append(s)
        j+=1
    ##print(d[x],j,s,a[d[x]-1])    
    if j!=d[x] and n>=j:
    
        s+=(n-j)//(j-d[x])*(s-a[d[x]-1])
    #print(s)
        if (n-j)%(j-d[x])!=0:
        #print((n-d[x]),(j-d[x]))
            s+=a[d[x]-1+(n-j)%(j-d[x])]-a[d[x]-1]
    print(s)

Submission status: Runtime Error

Solution code:
n,x,m=list(map(int,input().split()))
if m==1:
    print(x)
else:
    d=[-1]*(m-1)
    j=1
    s=x
    a=[]
    a.append(x)
    while j<n:
        x=x**2
        x%=m
        if d[x]!=-1:
            break
        else:
            d[x]=j
        s+=x
        a.append(s)
        j+=1
    ##print(d[x],j,s,a[d[x]-1])    
    if j!=d[x]:
    
        s+=(n-j)//(j-d[x])*(s-a[d[x]-1])
    #print(s)
        if (n-j)%(j-d[x])!=0:
        #print((n-d[x]),(j-d[x]))
            s+=a[d[x]-1+(n-j)%(j-d[x])]-a[d[x]-1]
    print(s)

Submission status: Runtime Error

Solution code:
n,x,m=list(map(int,input().split()))
d=[-1]*(m-1)
j=1
s=x
a=[]
a.append(x)
while j<n:
    x=x**2
    x%=m
    if d[x]!=-1:
        break
    else:
        d[x]=j
    s+=x
    a.append(s)
    j+=1
##print(d[x],j,s,a[d[x]-1])    
if j!=d[x]:

    s+=(n-j)//(j-d[x])*(s-a[d[x]-1])
#print(s)
    if (n-j)%(j-d[x])!=0:
    #print((n-d[x]),(j-d[x]))
        s+=a[d[x]-1+(n-j)%(j-d[x])]-a[d[x]-1]
print(s)

Submission status: Runtime Error

Solution code:
n,x,m=list(map(int,input().split()))
d=[-1]*(m-1)
j=1
s=x
a=[]
a.append(x)
while j<n:
    x=x**2
    x%=m
    if d[x]!=-1:
        break
    else:
        d[x]=j
    s+=x
    a.append(s)
    j+=1
##print(d[x],j,s,a[d[x]-1])    
s+=(n-j)//(j-d[x])*(s-a[d[x]-1])
#print(s)
if (n-j)%(j-d[x])!=0:
    #print((n-d[x]),(j-d[x]))
    s+=a[d[x]-1+(n-j)%(j-d[x])]-a[d[x]-1]
print(s)

Submission status: Runtime Error

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

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


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


def find_index(a, x, count):
    for i in range(count):
        ai = a[i]
        if ai == x:
            return i
    return -1


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


n, x, m = input_int_array()
a = [-2] * (m)

answer(n, x, m)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, X, M = inpl()

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

dp = [0] * (M + 100)
ls = [0] * (M + 100)
wa = [0] * (M + 100)
dp[X] = 1
ls[1] = X
wa[1] = X

left, right = 0, 0

for i in range(2, N + 1):
    ls[i] = (ls[i-1] ** 2) % M
    wa[i] = wa[i-1] + ls[i]
    if i == N or ls[i] == 0:
        print(wa[i])
        sys.exit()
    
    if dp[ls[i]] == 0:
        dp[ls[i]] = i
    else:
        left, right = dp[ls[i]], i
        break

len = right - left
num = wa[right] - wa[left]

ans = 0
N = N - left
A = N // len
B = N % len
print(A * num + wa[left + B])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, X, M = inpl()

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

dp = [0] * (M + 100)
ls = [0] * (M + 100)
wa = [0] * (M + 100)
dp[X] = 1
ls[1] = X
wa[1] = X

left, right = 0, 0

for i in range(2, N + 1):
    ls[i] = (ls[i-1] ** 2) % M
    wa[i] = wa[i-1] + ls[i]
    if i == N or ls[i] == 0:
        print(wa[i])
        sys.exit()
    
    if dp[ls[i]] == 0:
        dp[ls[i]] = i
    else:
        left, right = dp[ls[i]], i
        break

len = right - left
num = wa[right-1] - wa[left-1]

ans = 0
N = N - left
A = N // len
B = N % len
print(A * num + wa[left + B])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, X, M = inpl()

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

dp = [0] * (M + 1)
ls = [0] * (M + 1)
wa = [0] * (M + 1)
dp[X] = 1
ls[1] = X
wa[1] = X

left, right = 0, 0

for i in range(2, N + 1):
    ls[i] = (ls[i-1] ** 2) % M
    wa[i] = wa[i-1] + ls[i]
    if i == N or ls[i] == 0:
        print(wa[i])
        sys.exit()
    
    if dp[ls[i]] == 0:
        dp[ls[i]] = i
    else:
        left, right = dp[ls[i]], i
        break

len = right - left
num = wa[right-1] - wa[left-1]

ans = 0
N = N - left
A = N // len
B = N % len
print(A * num + wa[left + B])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, X, M = inpl()

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

dp = [0] * (M + 1)
ls = [0] * (M + 1)
wa = [0] * (M + 1)
dp[X] = 1
ls[1] = X
wa[1] = X

left, right = 0, 0

for i in range(2, N + 1):
    ls[i] = (ls[i-1] ** 2) % M
    wa[i] = wa[i-1] + ls[i]
    if i == N or ls[i] == 0:
        print(wa[i])
        exit(0)
    
    if dp[ls[i]] == 0:
        dp[ls[i]] = i
    else:
        left, right = dp[ls[i]], i
        break

len = right - left
num = wa[right-1] - wa[left-1]

ans = 0
N = N - left
A = N // len
B = N % len
print(A * num + wa[left + B])

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
# import decimal
# from decimal import Decimal
# decimal.getcontext().prec = 10

# from heapq import heappush, heappop, heapify
# import math
# from math import gcd
# import itertools as it
# import collections
# from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, X, M = inpl()

dp = [0] * (M + 1)
ls = [0] * (M + 1)
wa = [0] * (M + 1)
dp[X] = 1
ls[1] = X
wa[1] = X

left, right = 0, 0

for i in range(2, N + 1):
    ls[i] = (ls[i-1] ** 2) % M
    wa[i] = wa[i-1] + ls[i]
    if i == N or ls[i] == 0:
        print(wa[i])
        exit(0)
    
    if dp[ls[i]] == 0:
        dp[ls[i]] = i
    else:
        left, right = dp[ls[i]], i
        break

ren = right - left
num = wa[right-1] - wa[left-1]

ans = 0
N = N - left
A = N // ren
B = N % ren
print(A * num + wa[left + B])

Submission status: Runtime Error

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

from math import log, ceil

ans=0

ini=[0]*M
mod=[0]*M
ini[0]=sum(list(range(1,M)))
Counter=[0]*M
Counter[0]=M-1

for i in range(1,M):
    now=i+1
    temp=now
    count=1
    while now**2<M:
        now=now**2
        temp+=now
        count+=1
    m=now**2%M
    ini[i]=temp
    mod[i]=m
    Counter[i]=count
#print(ini[:5])
#print("ok")
#print(Counter[:100])
ans=0
count=0
now=X
done=[-1]*M
ok=False
while True:
    if count+Counter[now-1]>N:
        break
    if done[now-1]==-1 or ok==True:
        done[now-1]=(ans, count)
        ans+=ini[now-1]
        #print(ini[now-1])
        count+=Counter[now-1]
        now=mod[now-1]
    else:
        pans, pcount=done[now-1]
        #print(count, pcount)
        #print("break")
        ans+=(ans-pans)*((N-count)//(count-pcount))
        count+=(count-pcount)*((N-count)//(count-pcount))
        #print(count)
        ok=True





    


while True:
    if count==N:
        break
    ans+=now
    now=now**2
    count+=1

    

print(ans)






#print(ini)
#print(mod)
#print(Counter)

Submission status: Runtime Error

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

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

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

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

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

print(ans)

Submission status: Runtime Error

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

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

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

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

print(ans)

Submission status: Runtime Error

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

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

Submission status: 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):
     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())
A = [X]

for i in range(M-1):
    z = A[i]**2 % M
    if z not in A:
        A.append(z)
    else:
        break

idx = A.index(z)

before = A[:idx]
cy_sum = sum(A[idx:])
cy_len = len(A[idx:])
cy_cnt = (N-len(before)) // cy_len
mod = A[idx:idx + N - len(before)-cy_len*cy_cnt]

if cy_cnt == 0:
    print(sum(A)+mod)
else:
    print(sum(before) + cy_sum*cy_cnt + sum(mod))

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import math

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

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

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

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

Submission status: Runtime Error

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

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

A=[0]*M
A[0]=X
D=[0]*M

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

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


print(ans)

Submission status: Runtime Error

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

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

A=[0]*M
A[0]=X
D=[0]*M

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

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


print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

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

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

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

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

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



print(s)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
loop_start, n = 0, 0
A = [X]
for i in range(1, N):
    tmp = A[-1]**2 % M
    if tmp in A:
        loop_start = A.index(tmp)
        n = i - A.index(tmp)
        break
    else:
        A.append(tmp)

start, loop = A[:loop_start], A[loop_start:]
sum_start = sum(start)
sum_loop = sum(loop)
div, mod = divmod(N - loop_start, n)
end = loop[:mod]
sum_end = sum(end)
ans = sum_start + sum_loop * div + sum_end
print(ans)

Submission status: Runtime Error

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

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

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

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

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



print(s)

Submission status: Runtime Error

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

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

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


#最後にA[i]が出現したのは？
A_repeat = A[mydict[A[i_stop]]:i_stop]

if len(A_repeat)!=0:
    s+=((N-1)-(i_stop-1))//len(A_repeat)*sum(A_repeat)

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



print(s)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理


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


A = {X}
loop_start_index = 0
while True:
    A_next = f(A[-1], M)
    if A_next in A:
        loop_start_index = A.index(A_next)
        break
    else:
        A.add(A_next)

loop_length = len(A) - loop_start_index
loop_cnt = (N - loop_start_index) // loop_length
loop_res = (N - loop_start_index) % loop_length
ans = sum(A[:loop_start_index]) + \
    loop_cnt * sum(A[loop_start_index:]) + \
    sum(A[loop_start_index: loop_start_index + loop_res])

# 結果出力
print(ans)

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

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

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

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

#最後にA[i]が出現したのは？
A_repeat = A[mydict[A[i_stop]]:i_stop]

s+=((N-1)-(i_stop-1))//len(A_repeat)*sum(A_repeat)

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

print(s)

Submission status: Runtime Error

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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, X, M = NMI()
    A = []
    A_ID = {}
    break_flag = False
    for i in range(M):
        if i == 0:
            A.append(X)
            A_ID[X] = 0
        else:
            x = A[-1]**2 % M
            if x not in A_ID:
                A.append(x)
                A_ID[x] = i
            else:
                A.append(x)
                start = A_ID[x]
                end = i
                break_flag = True
            if break_flag:
                break

    if N < start+1:
        print(sum(A[:N]))
        exit()

    ans = sum(A[:start])
    lp = sum(A[start:end])
    gap = end - start
    lp_n = (N - start) // gap
    rem = (N - start) % gap
    ans += lp * lp_n + sum(A[start: start + rem])
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
#全体ループを見る配列
t_loop = [X]
#初回ループを見る配列
f_loop = [X]
#出現回数を見る辞書
memo = {X:1}
#2回目以降のループを見る配列
s_loop = []
while True:
    new_val = t_loop[-1]**2%M
    t_loop.append(new_val)
    if new_val not in f_memo:
        memo[new_val] = 1
        f_loop.append(new_val)
    else:
        memo[new_val] += 1
        if memo[new_val] == 3:
            break
        else:
            s_loop.append(new_val)

ans = 0
if N <= len(f_loop):
    ans += sum(f_loop[:N])
else:
    ans += sum(f_loop)
    shou = (N-len(f_loop))//len(s_loop)
    amari = (N-len(f_loop))%len(s_loop)
    ans += shou*sum(s_loop)
    ans += sum(s_loop[:amari])
    
print(ans)