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:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, sX, mod = mapint()

X = sX
s = set()
s.add(X)
s_loop = set()
ans = X
loop = 0
loops = []
for i in range(min(10**5*2+10, N-1)):
    X = pow(X, 2, mod)
    if X in s:
        if X in s_loop:
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
if rest:
    if not len(s_loop):
        s_loop.append(X)
    ans += (rest//len(s_loop))*loop
    amari = rest%len(s_loop)+1
    for i in range(amari):
        ans += loops[i]
    print(ans)
else:
    print(ans)

Submission status: Runtime Error

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

k = 0
while M % 2 == 0:
    k += 1
    M = M // 2
L = M

order = 1
if L != 1:
    e = 2 % L
    while e != 1:
        order += 1
        e = (2 * e) % L

A = [None] * (k + order)
A[1] = X
for i in range(2, k + order + 1):
    A[i] = (A[i - 1] * A[i - 1]) % copy

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

print(ans)

Submission status: Runtime Error

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

ans = x % m
dic = dict()
dicNum = dict()
dicSum = dict()

for i in range(2,n+1):
    b = x
    x = x**2 % m
    if x in dicNum.keys():
        t = i - dicNum[x]
        zan = n - i + 1
        k = zan // t
        ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
        if zan% t != 0:
            zan = zan % t
            ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
        break
    else:
        ans += x
        dicSum[i] = ans
        dic[x] = ans
        dicNum[x] = i

print(ans)

Submission status: Runtime Error

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

ans = [X]
a = X

for to in range(1, N):
    a = (a**2) % M
    if a in ans:
        break
    else:
        ans.append(a)
for fr, tmp in enumerate(ans, 0):
    if fr == N-1 and a == tmp:
        fr += 1
    if a == tmp:
        break
   
ret = 0
if fr != 0:
    ret += sum(ans[:fr])
if fr != to:
    l = (N-fr)//(to-fr)
    if to - fr == 1:
        ret += ans[fr:to] * l
    else:
        ret += sum(ans[fr:to]) * l
    if N > fr + ((N-fr)//(to-fr))*(to-fr):
        m = N - (fr + ((N-fr)//(to-fr))*(to-fr))
        if to - fr == 1:
            ret += ans[fr]
        else:
            ret += sum(ans[fr:to][:m])
print(ret)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

def main():
    N, X, M = LI()
    p = [0] * M
    p[1] = X
    for i in range(2, M):
        p[i] = pow(X, pow(2, i-1, M-1), M)
    s = 0
    for v in p:
        s = (s + v) % M

    tmp = 0
    for i in range(N % M):
        tmp = (tmp + p[i]) % M

    print((N // M * s % M + tmp) % M)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
st = x
ans = 0
mod = m
num = []
for i in range(n):
    ch = st
    if st in num:
        break
    ans += ch
    st *= st
    st %= mod
    if i != 0 and i != 1:
        num.append(ch)
le = len(num)
if len(num) == 0:
    z = 0
else:
    z  = n//le
rest = (n-1)%le
if 0 in num:
    print(sum(num[:n]) + x + x**2%mod)
else:
    print(z*sum(num) + sum(num[:rest-1]) + x + x**2%mod)

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split( ))
rireki = [0 for _ in range(1,M)]
A = []
i = X
count = 1
while rireki[i] == 0 or count == N:
    rireki[i] = count
    A.append(i)
    i = (i**2)%M
    count += 1

one = sum(A)
two = sum(A[rireki[i]-1:])
amari = (N - len(A))%(len(A[rireki[i]-1:]))
sho = (N - len(A))//(len(A[rireki[i]-1:]))
three = sum(A[rireki[i]-1:rireki[i]+amari])
ans = one + sho*two + three
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*(n//100)
lis = [-1]*m
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        break
    l[i] = x
    lis[x] = i
    ans += x
for i in range(lis[x],lis[x]+b):
    ans += l[i]
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
dp=[0]*n
dp[0]=x
for i in range(n-1):
    dp[i+1]=(dp[i]**2)%m
print(sum(dp))

Submission status: Runtime Error

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

n,x,m = I()
dp = []
amari = []
dp.append(x)
b = 1
c = 0

for i in range(1,n):
  dpa = (dp[i-1]**2) % m
  p = dpa
  if p in amari:
    xxx = amari.index(p)+1
    a = i+1
    b = n//(a-xxx-1)
    c = n%(a-xxx)
    break
  else:
    amari.append(p)
  if p == 0:
    print(sum(dp))
    sys.exit()
  dp.append(dpa)

print(b*sum(dp[xxx:])+sum(dp[xxx:c+xxx+1])+sum(dp[:xxx]))

"""
n,k = I()
num = []
taka = []
aaaa = 998244353

for i in range(k):
  l,r = I()
  num.append(l)
  num.append(r)
  taka.append([l,r])

num = list(set(num))

"""

Submission status: Runtime Error

Solution code:
n, x, m=map(int, input().split())
A=[0]*(10**5)
A[1]=x
old=x
for i in range(2, n):
    new=(old**2)%m
    if new==A[1]:
        end=i
        break
    old=new

loop_sum=0

for k in range(1, end+1):
    loop_sum+=A[k]

ans=0

for s in range(1, n%end+1):
    ans+=A[s]

ans+=(n//end)*loop_sum

print(ans)

Submission status: Runtime Error

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

List = [X]

for i in range(N-1):
    X = X**2 % M
    if X in List:
        #配列の何番目か
        num = i + 1
        #同じ数字
        key = List.index(X)
        break
    List.append(X)

ans = sum(List)

loop = (N - len(List)) // (num - key)
add = (N - len(List)) % (num - key)

ans += loop * sum(List[key:num])
ans += sum(List[key:key+add])

print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
l=[-1]*m
s=[0]*m
t=p=0
while l[x]<0 and t<=10**6:
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  t+=1
T=t-l[x]
S=s[p]+x-s[x]
if n<l[x]:
  print(s[l.index((n-1)%m)])
else:
  print(S*((n-l[x])//T)+s[l.index((l[x]+(n-l[x])%T-1)%m)])

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split( ))
rireki = [0 for _ in range(1,M)]
A = []
i = X
count = 1
while rireki[i] == 0:
    rireki[i] = count
    A.append(i)
    i = (i**2)%M
    count += 1

one = sum(A)
two = sum(A[rireki[i]-1:])
amari = (N - len(A))%(len(A[rireki[i]-1:]))
sho = (N - len(A))//(len(A[rireki[i]-1:]))
three = sum(A[rireki[i]-1:rireki[i]+amari])
ans = one + sho*two + three
print(ans)

Submission status: Runtime Error

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

ans = x % m
dic = dict()
dicNum = dict()
dicSum = dict()

for i in range(2,n+1):
    b = x
    x = x**2 % m
    if x in dicNum.keys():
        t = i - dicNum[x]
        zan = n - i + 1
        k = zan // t
        ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
        zan = zan % t
        ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
        break
    else:
        ans += x
        dicSum[i] = ans
        dic[x] = ans
        dicNum[x] = i

print(ans)

Submission status: Runtime Error

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

num_list = []
num2 = x

for i in range(n) :
    num1 = num2 % m
    if num1 in num_list :
        num = num_list.index(num1)
        break
    else :
        num_list.append(num1)
    num2 = num1 ** 2

if num_list == [] :
    primt(0)
else :
    acc1 = sum(num_list[:num])
    acc2 = sum(num_list[num:])
    
    num3 = n // len(num_list[num:])
    num4 = n % len(num_list[num:])
    print(acc1 + acc2 * num3 + sum(num_list[num : num4]))

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*(n//10)
lis = [-1]*m
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        break
    l[i] = x
    lis[x] = i
    ans += x
for i in range(lis[x],lis[x]+b):
    ans += l[i]
print(ans)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
s_list=[]
current=x
index=0
count=0
for i in range(n) :
  s_list.append(current)
  current=current**2%m
  if current  in s_list :
    index=len(s_list)
    break
m=s_list.index(current)
first_sum=sum(s_list[:m])
syuuki=s_list[m:]
syuuki_sum=sum(s_list[m:])
if syuuki_sum==0 :
  print(first_sum)
else :

  syuuki1=index-m
  k=(n-m)//syuuki1
  
  count+=k*syuuki_sum
  count+=first_sum
  l=(n-m)%syuuki1-1
  
  if l!=-1 :
    count+=sum(syuuki[:l])
  print(count)

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, sX, mod = mapint()

X = sX
s = set()
s.add(X)
s_loop = set()
ans = X
loop = 0
loops = []
for i in range(min(10**5*2+10, N-1)):
    X = pow(X, 2, mod)
    if X in s:
        if X in s_loop:
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
if rest:
    ans += (rest//len(s_loop))*loop
    amari = rest%len(s_loop)+1
    try:
        for i in range(amari):
            ans += loops[i]
    except:
        loops.append(sX)
        ans += loops[0]
    print(ans)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
A = [0]*(M+1)
A[1] = X
ans = X
for i in range(2, N+1):
    A[i] = (A[i-1]*A[i-1])%M
    if A[i] == 0:
        break
    elif A[i] in A[1:i]:
        break
        
    ans += A[i]
    
b = A.index(A[i])
if i != b and A[i] != 0:
    ans += sum(A[b:i])*((N-b+1)//(i-b)-1) + sum(A[b:b+(N-(b-1+(i-b)*((N-b+1)//(i-b))))])

print(ans)

Submission status: Runtime Error

Solution code:

import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
##import operator
input=sys.stdin.readline
import random
##sys.setrecursionlimit(10**6)
##fo=open("output1.txt","w")
##fi=open("input1.txt","w")
mod=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())

    
for _ in range(10):
    n,x,m=cin();f=0
    if(x==0):
        ans=0
    else:
        nmod=x%m
        store=[nmod]
        d=dd(int);d[nmod]=1;x=nmod*nmod
        for i in range(1,n):
            if(x==0):
                f=1
                break
            elif(d[x]==0):
                nmod=x%m
                x=nmod*nmod
                d[nmod]=1
                store+=[nmod]
            else:
                f=2
                cont=store.index(x%m)
                rem=n-i
                break
        if(f<=1):
            print(sum(store))
        else:
    ##        print(store)
            
            nval=len(store)-cont
            remsum=sum(store[cont:])
            mul=rem//nval
            modu=rem%nval
    ##        print(rem,cont,nval,mul,modu,len(store))
            k=sum(store[cont:(cont+modu)])
            ans=sum(store)+mul*remsum+k
        print(ans)
        
        
        
        
            
    
    

    
    
        
        
      
    

##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

Submission status: Runtime Error

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

List = [X]

for i in range(N-1):
    X = X**2 % M
    if X in List:
        #配列の何番目か
        num = i + 1
        #同じ数字
        key = List.index(X)
        break
    List.append(X)

ans = sum(List)

loop = (N - len(List)) // (num - key)
add = (N - len(List)) % (num - key)

ans += loop * sum(List[key:num])
ans += sum(List[key:key+add])
print(loop,key,num)
print(ans)

Submission status: Runtime Error

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

ans = [X]
a = X

for to in range(1, N):
    a = (a**2) % M
    if a in ans:
        break
    else:
        ans.append(a)
for fr, tmp in enumerate(ans, 0):
    if fr == N-1 and a == tmp:
        fr += 1
    if a == tmp:
        break
   
ret = 0
if fr != 0:
    ret += sum(ans[:fr])
if fr != to:
    l = (N-fr)//(to-fr)
    ret += sum(ans[fr:to]) * l
    if N > fr + ((N-fr)//(to-fr))*(to-fr):
        m = N - (fr + ((N-fr)//(to-fr))*(to-fr))
        ret += sum(ans[fr:to][:m])
print(ret)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
a = [x]
for i in range(n-1):
    ad = (a[-1]**2) % m
    if ad in a:
        roop_s = a.index(ad)
        roop_e = len(a)
        break
    else:
        a.append(ad)
    if i == n-2:
        print(sum(a))
        exit()
roop_t = (n-roop_s) // (roop_e - roop_s)
left = n - roop_t*(roop_e - roop_s) - roop_s
ans = sum(a[:roop_s]) + roop_t*sum(a[roop_s : roop_e]) + sum(a[roop_s:roop_s+left])
print(ans)

Submission status: Runtime Error

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

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

data = [x]

while True:
    x = f(x**2,m)
    if(x in data):
        break
    data.append(x)

l = len(data)
k = n//l
s = n%l
if(k!=0):
    ans = sum(data)*k
    if(0 in data):
        print(sum(data))
        exit()
ans+=sum(data[:s])
print(ans)

Submission status: Runtime Error

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

result = []
result.append(x)

for i in range(1, 1000007):
    next_value = (result[-1] ** 2) % m
    result.append(next_value)

start = -1
index = 0
for x in result:
    if (x ** 2) >= m:
        start = (x ** 2) % m
        index += 1
        break
    index += 1

if m == 1:
    print(x)
elif x == 0:
    print(0)
elif x == 1:
    print(n)
else:
    length = 0

    for i in range(index + 1, 1000006):
        if result[i] == start:
            nownow = result[index:i]
            break

    remain = n - index
    length = len(nownow)

    cnt = remain // length
    summary = sum(nownow)

    rema = remain - (cnt * length)

    total = sum(result[:index]) + summary * cnt + sum(nownow[:rema])
    print(total)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=[]
a.append(x*x%m)
ind=0
s=0
for i in range(n-2):
    t=a[i]*a[i]%m
    if a.count(t)==0:
        a.append(t)
    else:
        ind=a.index(t)
        break
s=sum(a[ind:])
l=len(a)-ind
answer=(n-1-ind)//l*s
for i in range(n-((n-1-ind)//l)*l-2):
    answer+=a[i+ind]
print(answer+x+sum(a[:ind]))

Submission status: Runtime Error

Solution code:
def main():
    N,X,M = map(int,input().split())
    dict = {key:0 for key in range(M)}
    #print(dict)
    if N==1:
        return X
    dict[X] += 1
    cnt = 1
    A = [0]*M
    A[1] = X
    ans = X
    tmp = X
    for i in range(1,N,1):
        tmp = (tmp**2)%M
        if dict[tmp] != 0:
            break
        ans += tmp
        A[i+1] = A[i]+tmp
        cnt += 1
        dict[tmp] += cnt

    num = N - cnt#残り足す回数
    roop_num = cnt - dict[tmp] + 1
    syo = num//roop_num
    amari = num%roop_num
    ans += syo*(A[cnt]-A[dict[tmp]-1])
    ans += (A[dict[tmp]+amari-1]-A[dict[tmp]-1])
    return ans

print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 22:03:19 2020

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**5+1)
A[0] = X
for i in range(1,N):
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

j = mod_lis.index(tmp)
T = i - j
ans = 0
if T != 0:  
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:i])
    ans += T_sum * (N-j)//T
    T_lis = mod_lis[j:i]    
    ans += sum(T_lis[:(N-j)%T])
else:
    ans = sum(mod_lis)
#print(T_lis)
print(ans)
#print(T_sum)
#print(sum(T_lis))

Submission status: Runtime Error

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

ans = [X]
a = X

for to in range(1, N):
    a = (a**2) % M
    if a in ans:
        break
    else:
        ans.append(a)
for fr, tmp in enumerate(ans, 0):
    if fr == N-1 and a == tmp:
        fr += 1
    if a == tmp:
        break
   
ret = 0

ret += sum(ans[:fr])
if fr != to:
    l = (N-fr)//(to-fr)
    ret += sum(ans[fr:to]) * l
    if N > fr + ((N-fr)//(to-fr))*(to-fr):
        m = N - (fr + ((N-fr)//(to-fr))*(to-fr))
        if m == 1:
            ret += ans[fr]
        else:
            ret += sum(ans[fr:to][:m])
print(ret)

Submission status: Runtime Error

Solution code:
n,X,m=map(int,input().split())
x=[0]*m
y=[0]*m
y[0]=X
z=[0]*(m+1)
z[X]+=1
for i in range(1,m):
    x[i]=(i**2)%m
for i in range(1,m):
    y[i]=x[y[i-1]]
    z[y[i]]+=1
    if z[y[i]]==2:
        e=i
        q=y[i]
        break
for i in range(len(y)):
    if y[i]==q:
        b=i
        break
l=y[b:e]
L=len(l)
s=sum(l)
#print(x)
#print(y)
#print(z)
#print(b,e)
#print(l)
#print(sum(y[:b]))
#print(((n-b)//L)*s)
#print(sum(l[:(n-b)%L]))
if n>=b:
    ans=sum(y[:b])+((n-b)//L)*s+sum(l[:(n-b)%L])
else:
    ans=sum(y[:n])
if m!=1:
    print(ans)
else:
    print(0)

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
l=[-1]*m
s=[0]*m
t=p=0
while l[x]<0:
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
  t+=1
T=t-l[x]
S=s[p]+x-s[x]
if n<l[x]:
  print(s[l.index((n-1)%m)])
else:
  print(S*((n-l[x])//T)+s[l.index((l[x]+(n-l[x])%T-1)%m)])

Submission status: Runtime Error

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

result = []
result.append(x)

for i in range(1, 100007):
    next_value = (result[-1] ** 2) % m
    result.append(next_value)

start = -1
index = 0
for x in result:
    if (x ** 2) >= m:
        start = (x ** 2) % m
        index += 1
        break
    index += 1

if m == 1:
    print(x)
elif x == 0:
    print(0)
elif x == 1:
    print(n)
else:
    length = 0

    for i in range(index + 1, 100006):
        if result[i] == start:
            nownow = result[index:i]
            break

    remain = n - index
    length = len(nownow)

    cnt = remain // length
    summary = sum(nownow)

    rema = remain - (cnt * length)

    total = sum(result[:index]) + summary * cnt + sum(nownow[:rema])
    print(total)

Submission status: Runtime Error

Solution code:
n,x,m = map(int,input().split())
st = x
ans = 0
mod = m
num = []
for i in range(n):
    ch = st
    if st in num:
        break
    ans += ch
    st *= st
    st %= mod
    if i != 0 and i != 1:
        num.append(ch)
le = len(num)
z  = n//le
rest = (n-1)%le
if 0 in num:
    print(sum(num[:n]) + x + x**2%mod)
else:
    print(z*sum(num) + sum(num[:rest-1]) + x + x**2%mod)

Submission status: Runtime Error

Solution code:
n, x, mod = map(int, input().split())
lst = [0, x]
num_set = set([x])
num_lst = [0, x]
flag = False

for i in range(mod - 1):
  x = (x * x) % mod
  s = x + lst[-1]
  if x == 0:
    lst.append(s)
    break
  if x in num_set:
    flag = True
    break
  lst.append(s)
  num_set.add(x)
  num_lst.append(x)
  if i + 2 == n:
    break

#print(lst)
if flag:
  for i, ele in enumerate(num_lst):
    if x == ele:
      loop_s = i
      break

l = len(lst)
if lst[l - 1] == lst[l - 2]:
  print(lst[l - 1])
else:
  if not flag:
    print(lst[-1])
  else:
    loop = len(lst) - loop_s
    n -= loop_s - 1
    c = n // loop
    r = n % loop
    ans = 0
    if c == 0:
      ans += lst[n + loop_s + 1]
    else:
      ans += lst[l - 1] + (c - 1) * (lst[l - 1] - lst[loop_s - 1]) + lst[loop_s + r - 1] - lst[loop_s - 1]
    print(ans)

Submission status: Runtime Error

Solution code:

import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
import itertools
##import operator
input=sys.stdin.readline
import random
##sys.setrecursionlimit(10**6)
##fo=open("output1.txt","w")
##fi=open("input1.txt","w")
mod=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())

    
for _ in range(10):
    n,x,m=cin();f=0
    nmod=x%m
    store=[nmod]
    d=dd(int);d[nmod]=1;x=nmod*nmod
    for i in range(1,n):
        if(x==0):
            f=1
            break
        elif(d[x]==0):
            nmod=x%m
            x=nmod*nmod
            d[nmod]=1
            store+=[nmod]
        else:
            f=2
            cont=store.index(x%m)
            rem=n-i
            break
    if(f<=1):
        print(sum(store))
    else:
##        print(store)
        
        nval=len(store)-cont
        remsum=sum(store[cont:])
        mul=rem//nval
        modu=rem%nval
##        print(rem,cont,nval,mul,modu,len(store))
        k=sum(store[cont:(cont+modu)])
        ans=sum(store)+mul*remsum+k
        print(ans)
        
        
        
        
            
    
    

    
    
        
        
      
    

##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far

Submission status: Runtime Error

Solution code:
n,x,m=[int(i) for i in input().split()]
tot=x
pres=x
for i in range(n-1):
    pres=(pres**2)%m
    tot+=pres
    if pres=0:
        break
print(tot)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
s = 0
limit = 0
A = [X]
rec = []
start = 0

for i in range(1, N + 1):
    X = (X * X) % M
    if X not in A:
        A.append(X)
    else:
        start = A.index(X)
        rec = A[start:]
        limit = i
        break
l = len(rec)

print(sum(A[:limit]) + (N - limit) // l * sum(rec) + sum(rec[:(N - limit) % l]))

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
i=int(2)
a=[x]
while (i <= n):
	x=(x**2)%m
	if x in a:
		goto .abc
	else:
		a.append(x)
label .abc
if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Submission status: Runtime Error

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

ans = [X]
a = X

for to in range(1, N):
    a = (a**2) % M
    if a in ans:
        break
    else:
        ans.append(a)
for fr, tmp in enumerate(ans, 0):
    if fr == N-1 and a == tmp:
        fr += 1
    if a == tmp:
        break
   
ret = 0
ret += sum(ans[:fr])
if fr != to:
    l = (N-fr)//(to-fr)
    ret += sum(ans[fr:to]) * l
    if N > fr + ((N-fr)//(to-fr))*(to-fr):
        m = N - (fr + ((N-fr)//(to-fr))*(to-fr))
        ret += sum(ans[fr:to][:m])
print(ret)

Submission status: Runtime Error

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

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

li = [-1] * (m+1)
v = [False] * (m+1)
v2 = [False] * (m+1)
v[x] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = (i ** 2) % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li[:cnt]

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[-1])
else:
    n -= len(ans_li)
    if len(loop_li) == 0:
        print(ans_li[-1])
    else:
        if n % len(loop_li) == 0:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
        else:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])

Submission status: Runtime Error

Solution code:
N,X,M = map(int,input().split())
er = [0]*N
er[0] = X
MOD = 10**9+7
for i in range(1,N):
  er[i] = (er[i-1]**2%M)%MOD
  if er[i] == 0:
    break
print(sum(er)%MOD)

Submission status: Runtime Error

Solution code:
N, X, M = map(int, input().split())
a = X
i = 0
cnt = 0
li = [-1]*M
x = 0

for i in range(min(N, M)):
    if li[a] != -1:
        break
    else:
        li[a] = i
        cnt += a
        a = pow(a, 2, M)
        x += 1
# print(cnt)
# print(x, li[a])
if x-li[a] > 1:
    s = 0
    for i in range(li[a], x):
        s += li[i]
    cnt += (N-x)//(x-li[a]-1)*s
    for i in range((N-x) % (x-li[a]-1)+1):
        cnt += li.index(i+1)
print(cnt)

Submission status: Runtime Error

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

A = [X]
d = {}
loopflag = 0
d[X] = 1
for i in range(N):
  p = (A[i]**2) % M
  A.append(p)
  if(p in d):
    loopflag = 1
    break
  else:
    d[p] = 1

ans = 0

if(loopflag == 1):
  lastkey = next(iter(reversed(d)))
  keylist = list(d.keys())
  for i in range(len(keylist)):
    if(keylist[i]**2 >= M):
      looplist = keylist[i:]
      loopflag = 1
      break
  if(looplist[-1]==0):
    looplist.pop(0)
  looplength = len(looplist)
  #print("looplength =",looplength)
  onekeylen = len(keylist) - looplength
  #print(len(keylist))

  loopnum = (N - 1 - onekeylen) // looplength
  remain = (N - 1 - onekeylen) % looplength
  #print("onekeylen =",onekeylen)
  #print("loopnum =",loopnum)
  #print("remain =",remain)
  #print("lastkey =",lastkey)

  #d[looplist[0]] -= 1
  for i in range(looplength):
    d[looplist[i]] += loopnum - 1
  for i in range(remain+1):
    d[looplist[i]] += 1

  for i in range(len(keylist)):
    ans += keylist[i] * d[keylist[i]]
  print(ans)
  #print("keylist =",keylist)
  #print("looplist =",looplist)
  #print(d)
else:
  keylist = list(d.keys())
  print(sum(keylist))

Submission status: Runtime Error

Solution code:
n,x,m=map(int,input().split())
a=x
an=-1
bn=-1
cnt=0
cnt2=0
wa=x
wa2=x
num=[0 for i in range(m+3)]
flag=False
for i in range(m):
  cnt+=1
  an=(a**2)%m
  wa+=an
  a=an
  num[an]+=1
  if num[an]==2:
    flag=True
    break
a=x
for i in range(m):
  cnt2+=1
  bn=(a**2)%m
  wa2+=bn
  a=bn
  if bn==an:
    break
ans=wa2+(wa-wa2)*((n-cnt2-1)//(cnt-cnt2))
#print(ans)
k=(n-cnt2-1)%(cnt--cnt2)
a=bn
for i in range(k):
  ans+=bn
  bn=(a**2)%m
  a=bn
print(ans)

Submission status: Runtime Error

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

#l = list(map(int, input().split()))
#import numpy as np
#arr = np.array([int(i) for i in input().split()])
'''
a,b=[],[]
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

import sys
input = sys.stdin.readline

#l = list(map(int, input().split()))
#import numpy as np
#arr = np.array([int(i) for i in input().split()])
'''
a,b=[],[]
for i in range(n):
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

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

def premf(n):
    #前処理
    #minfactor:複数の素因数分解を高速(O(Q*logA_max))に行う,indexはその整数
    #return resで素数リスト(eratosthenes),MinFactorで前処理用リスト返す
    IsPrime=[False]+[False]+[True]*(n-1)
    MinFactor=[0]+[1]+[-1]*(n-1)

    res=[]
    
    for i in range(2,n+1):
        if IsPrime[i]:
            MinFactor[i]=i
    
            res.append(i)
    
            for j in range(i*2,n+1,i):
                IsPrime[j]=False
                if MinFactor[j]==-1: MinFactor[j]=i
                
    return MinFactor
def mf(n,MinFactor):
    #minfactor:nに対し[[素因数,個数],...]を返す
    res=[]
    while n!=1:
        prime=MinFactor[n]
        exp=0
        while MinFactor[n]==prime:
            exp+=1
            n//=prime
        res.append([prime,exp])
    return res
"""
mff=premf(x)
now=x
cnt=0
while now<m:
    cnt+=1
    r=mf(now,mff)
"""
ans=x
c=1
zz=[x]
while c<n:
    x**=2
    x%=m
    if x not in zz:
        zz.append(x)
    else:
        index=zz.index(x)
        break
    #print(zz)
    ans+=x
    c+=1
    #print(x,ans)

#print(index,(n-c)%len(zz),n,c,len(zz),sum(zz[index:]))
ans+=sum(zz[index:])*((n-c)//len(zz[index:]))
for i in range((n-c)%len(zz[index:])):
    ans+=zz[index:][i]
    #print(zz[index:][i])
print(ans)