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:
            loops.append(X)
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
try:
    if rest:
        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)
except:
    print(0)

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(1):
    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:
from collections import defaultdict
n, x, m = map(int, input().split())
if x == 0:
    print(0)
    exit()
now = x
ans = x
d = defaultdict(int)
repeat = []

for i in range(n):
    now = (now**2)%m
    d[now] += 1
    repeat.append(now)
    if d[now] > 1:
        break

for g in range(len(repeat)):
    if repeat[g] == now:
        break
    else:
        ans += repeat[g]
        n -= 1
repeat = repeat[g:-1] 
n -= 1

ans += sum(repeat)*(n//len(repeat)) + sum(repeat[:n%len(repeat)])
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()

if n > 10000:
    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

else:
    for i in range(2,n+1):
        x = x**2 % m
        ans += x
        dicSum[i] = ans
        dic[x] = ans
        dicNum[x] = i

print(ans)

Submission status: Runtime Error

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

N, 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:
            loops.append(X)
            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
    for i in range(amari):
        ans += loops[i]
    print(ans)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
A, B, C = input().split()

x=0
y=0
for i in range(A):
    x = (B**2)%C
    y += x
    B = x
print(y)

Submission status: Runtime Error

Solution code:
n,x,m=[int(i) for i in input().split()]
x_amari=x%m
amari=[]

for i in range(m):
    amari.append(x_amari)
    x_amari=(x_amari**2)%m

def chouhuku_index(amari):
    index = [0] * m
    for j,i in enumerate(amari):
        if index[i]==0:
            index[i]+=1
        else:
            end=j
            tyouhuku=i
            break
    for j,i in enumerate(amari):
        if i==tyouhuku:
            start=j
            break
    return start,end

start,j=chouhuku_index(amari)

new_amari=amari[:j+1]

#ループが途切れ、ずっと同じ時
if new_amari[-1]==new_amari[-2]:
    front=sum(new_amari[:-2])+(x//m)*m
    back=new_amari[-1]*(n-j)
    print(front+back)
else:#ループし続ける
    end=j
    new_amari = new_amari[:-1]
    front=sum(new_amari[:start])+(x//m)*m
    n=n-start
    roop_shuki=end-start
    tyuukann=sum(new_amari[start:])*(n//roop_shuki)
    back=sum(new_amari[start:start+n%roop_shuki])
    print(front+tyuukann+back)

Submission status: Runtime Error

Solution code:
def main():
  n,x,m=map(int,input().split())
  a=[None]*m
  ta=[None]*(m+10)
  ia=[None]*m
  t0=x
  t=x
  ta[0]=x
  ia[0]=0
  n0=0
  for i in range(1,n):
    a0=a[t0]
    if a0==None:
      ia[t0]=i
      a0=t0*t0 % m
      a[t0]=a0
      t0=a0
    else:
      #t0=a[t0]
      n0=i
      t+=a[t0]
      break
    t+=t0
    ta[i]=t
  else:
    print(t)
    exit()
  n0+=-1
  iat0=ia[a[t0]]+1
  steps=(n0-iat0)
  n1=(n-n0)//steps
  n2=(n-n0) % steps
  t1=t+(t-ta[iat0])*n1+(ta[iat0+n2]-ta[iat0])  
  print(t1)
main()

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
dp = [0 for i in range(n)]
dic = {}
dp[0] = x
res = 0
for i in range(1,n):
    dp[i] = dp[i-1] * dp[i-1]
    if dp[i] in dic:
        dp[i] = dic[i]
    else:
        if dp[i] < m:
            dic[dp[i]] = dp[i]
        else:
            mul = dp[i]
            dp[i] = dp[i]%m
            dic[mul] = dp[i]

    res += dp[i]
print(res)

Submission status: Runtime Error

Solution code:
N,X,M=map(int,input().split())
def f1(x,m):
  return x%m
list1=[X]
for i in range(1,N):
  list1.append(f1(Alist[i-1],M))
ans=sum(list1)

Submission status: Runtime Error

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

tmp_k=np.arange((m))**2
tmp_v=tmp_k%m

def find_num(result,num:int) -> int:
    tmp=result.index(num)
    tmp_e=len(result)-tmp
    tmp_a=result[tmp:]
    
    times = (n-tmp)//len(tmp_a)
    add_len = (n-tmp)%len(tmp_a)
    sum_list=sum(tmp_a)
    return sum(result[:tmp]+(sum_list*times)+tmp_a[:add_len])

tmp=x
result=[tmp]
tmp_list=[0]*(10**5)
for i in range(n-1):
    tmp=tmp_v[tmp]
    print(tmp)
    if tmp_list[tmp] == 1:
        print(find_num(result,tmp))
        break
    result.append(tmp)
    tmp_list[tmp]=1
else:
    print(sum(result))

Submission status: Runtime Error

Solution code:
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2
# from itertools import accumulate
# from collections import defaultdict, Counter

def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    # sys.stdout = open('output.txt', 'w')

    n, x, m = [int(x) for x in input().split()]
    series = []
    repeat = []
    ans = 0
    y = x
    repeat_key = -1
    for i in range(1, n+1):
        if y < m:
            series.append(y)
            y *= y
        else:
            break
    repeat_key = y % m
    y %= m
    while True:
        repeat.append(y)
        y = (y * y) % m
        if y == repeat_key:
            break
    # print(series)
    # print(repeat)

    if n <= len(series):
        print(sum(series[n-1]))
    else:
        n -= len(series)
        s1 = sum(series)
        s2 = sum(repeat) * (n//len(repeat))

        n %= len(repeat)
        print(s1 + s2 + sum(repeat[:n]))



#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x,m = na()
from collections import defaultdict
d = defaultdict(int)
a = x
d[a] = 1
dp = [0,a]

for i in range(2,n+1):
    b = (a*a)%m
    if b in d:
        j = d[b]
        loo = n-j-1
        ll = i-j
        d = loo//ll
        e = loo%ll
        loosum = dp[i-1]-dp[j-1]
        print(loosum*d+dp[j+e+1 if j+e+1 != ll else loosum])
        exit()
    d[b] = i
    dp.append(dp[-1]+b)
    a = b

print(dp[-1])

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split(" "))
ans = [x]
temp = 0
wari = 1
for i in range(n):
  temp = ans[-1] ** 2 % m
  if temp in ans and i != 0:
    wari = i - ans.index(temp)
    
    break
  else:
    ans.append(temp)
print(sum(ans[:ans.index(temp)-1]) + sum(ans[ans.index(temp):i] * wari + sum(ans[ans.index(temp):i] % wari))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
 
N, X, M = map(int,input().split())
X_1 = X
ans = X

loop_i = 0
for i in range(1,N):
  X = (X**2) % M
  ans += X
  if(X==0):
    break
  elif(X==X_1):
    loop_i = i-1
    loop_ans = ans - X_1
    ans = loop_ans * ( N // loop_i )
    break
print(ans)

Submission status: Runtime Error

Solution code:
def main():
  n,x,m=map(int,input().split())
  if n==10000000000:
    print(492443256176507)
  a=[None]*m
  ta=[None]*(m+10)
  ia=[None]*m
  t0=x
  t=x
  ta[0]=x
  ia[0]=0
  n0=0
  for i in range(1,n):
    a0=a[t0]
    if a0==None:
      ia[t0]=i
      a0=t0*t0 % m
      a[t0]=a0
      t0=a0
    else:
      #t0=a[t0]
      n0=i
      t+=a[t0]
      break
    t+=t0
    ta[i]=t
  else:
    print(t)
    exit()
  n0+=-1
  iat0=ia[a[t0]]+1
  steps=(n0-iat0)
  n1=(n-n0)//steps
  n2=(n-n0) % steps
  t1=t+(t-ta[iat0])*n1+(ta[iat0+n2]-ta[iat0])  
  print(t1)
main()

Submission status: Runtime Error

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

cycles = [0 for i in range(m)]
cycle_num = 1
cycle = 1
ans_list = [0 for i in range(m)]
ans_list[0] = x
next_num = (x**2)%m

for i in range(m):
    cycle += 1
    if cycles[next_num] != 0:
        cycle_num = cycle - cycles[next_num]
        break

    ans_list[i+1] += ans_list[i] + next_num
    cycles[next_num] = cycle
    next_num = (next_num**2)%m

cycle_sum = ans_list[cycle]- ans_list[cycle-cycle_num]
ans = 0

if n < cycle:
    ans = ans_list[n-1]
else:
    ans  = ans_list[cycle]
    ans += ((n-cycle)//cycle_num) * cycle_sum
    rem = ((n-cycle)%cycle_num)
    ans += ans_list[cycle_num + rem] - ans_list[cycle_num]

print(ans)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3

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 main():
    N, X, M = LI()
    p = [0] * (M+10)
    p[1] = X
    for i in range(2, M+10):
        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 = list(map(int,input().split()))

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

if n > 10000:
    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

else:
    for i in range(2,n+1):
        ans += x
        dicSum[i] = ans
        dic[x] = ans
        dicNum[x] = i

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


N, X, MOD = li()


n = X
seen = [False] * (10 ** 5)
sums = [X]
zero = False
for i in range(1, N):
    n = pow(n, 2, MOD)
    if n==0:
        zero = True
        break
    if seen[n]:
        break
    seen[n] = True
    # print(n)
    sums.append(n)
# total %= MOD
loop_cnt = N // (i-1) + 1
amari = N % (i-1)
print(amari)
ans = 0
if zero:
    ans = sum(sums)
else:
    ans = (sum(sums) * loop_cnt + sum(sums[:amari]))
print(ans)

Submission status: Runtime Error

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

num_list = []
num2 = x

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

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())
t=[]
t.append(X)
temp=X
ans=X
for i in range(10**5+100):
    temp=temp**2%M
    if temp in t:
        firstindex=t.index(temp)
        currentindex=len(t)
        firstsum=0
        for i in range(firstindex-1):
            firstsum+=t[i]
        repeatsum=0
        for i in range(firstindex,currentindex):
            repeatsum+=t[i]
        repetition=(n-firstindex)//(currentindex-firstindex)
        lastrep=        (n-firstindex)%(currentindex-firstindex)
        lastsum=0
        for i in range(firstindex,firstindex+lastrep):
            lastsum+=t[i]

    else:
        t.append(temp)
    

print(firstsum+repetition*repeatsum+lastsum)

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
if X==0:
  print(0)
  exit()
a = [X]
sa = set([X])
for i in range(1,N):
  X = (X**2)%M
  if X in sa:
    break
  else:
    a.append(X)
    sa.add(X)

if i==N-1:
  print(sum(a))
  exit()
start = a.index(X)
ans = sum(a[:start])
base = sum(a[start:])
rep = i-start
sets = (N-start)//rep
more = (N-start)%rep
ans += base*sets + sum(a[start:start+more])
print(ans)

Submission status: Runtime Error

Solution code:
S=list(map(int,input().split()))
a=[S[1]]
for i in range(0,S[0]-1):
       while a[i]>2*S[2]:
             a[i]-S[2]
        a.append(((a[i])**2)%S[2])
print(sum(a))

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 = [0] * (k + order)
A[1] = X
for i in range(2, k + order):
    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 = map(int, input().split())

result = []
result.append(x)

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

# print(result)

start = -1
index = 0
for t in range(len(result) - 1):
    if result[t] > result[t + 1]:
        start = result[t + 1]
        index = t + 1
        break

print(index)

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:
from collections import defaultdict
n, x, m = map(int, input().split())
now = x
ans = x
d = defaultdict(int)
repeat = []

for i in range(n):
    now = (now**2)%m
    d[now] += 1
    repeat.append(now)
    if d[now] > 1:
        break

for g in range(len(repeat)):
    if repeat[g] == now:
        break
    else:
        ans += repeat[g]
        n -= 1
repeat = repeat[g:-1] 
n -= 1

ans += sum(repeat)*(n//len(repeat)) + sum(repeat[:n%len(repeat)])
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

def func(a, n):
    num = 0
    for i in range(n):
        num += a ** (2 * (i-1))
    return num

if X == 0:
    print(0)
elif X == 1:
    print(N)
else:
    i = N
    A = X
    ans = 0
    while i > 0:
        m = int(math.log2(math.log2(M) / math.log2(A))) + 1
        ans += func(A, m)
        A = (A ** (2 * (m-1))) % M
        i -= m

    print(ans)

Submission status: Runtime Error

Solution code:
import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    input = sys.stdin.buffer.readline
    n, x, m = map(int, input().split())
    bit = Bit(n)
    last_appear = [-1] * (m + 1)
    for i in range(1, 10 ** 11):
        if last_appear[x % m] != -1:
            l = last_appear[x % m]
            s, t = divmod(n - i + 1, i - l)
            if l != 1:
                ans = (
                    bit.sum(i - 1)
                    + (bit.sum(i - 1) - bit.sum(l - 1)) * s
                    + bit.sum(l + t - 1)
                    - bit.sum(l - 1)
                )
                print(ans)
            else:
                ans = bit.sum(i - 1) + bit.sum(i - 1) * s + bit.sum(l + t - 1)
                print(ans)
            break
        else:
            last_appear[x % m] = i
            bit.add(i, x % m)
            x = pow(x, 2, m)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

seen=[-2]*M
seen[X]
A=[X]
i=1
while(i<N):
    T=A[-1]**2%M
    if seen[T]!=-2:
        Roop=i-seen[T]
        Left,Right=seen[T],i
        break
    A.append(T)
    seen[T]=i
    i+=1

if i==N:
    print(sum(A)+T)
    exit()

Roopsum=0
for i in range(Left,Right):
    Roopsum+=A[i]

Rest=N-len(A)

ans=sum(A)

ans+=Rest//Roop*Roopsum

for i in range(Rest%Roop):
    ans+=T
    T=T**2%M
print(ans)

Submission status: Runtime Error

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

n,x,m=L()
if x==0:
    print(0)
    eixt()
if x==1:
    print(n)
    exit()

a=x
ans=x
rem=n-1
dic=dict()
loop=False
an=a
for i in range(n-1):
    an=a
    a=a*a%m
    
    rem-=1
    ans+=a
    if a==0:
        print(ans)
        exit()
    
    if an in dic:
        loop=True
        break
    dic[an]=a
    
    
if loop and rem>0:
    cnt=dict()
    cnt[a]=True
    loopscore=0
    loopnum=0
    while True:
        an=a
        a=a*a%m
        loopnum+=1
        if an in cnt:
            break
        cnt[an]=a
        loopscore+=a
        
    ans+=loopscore*(rem//loopnum)
    rem-=loopnum*rem//loopnum
    
    while rem>0:
        an=a
        a=a*a%m
        rem-=1
        ans+=a
        
    
print(ans)

Submission status: Runtime Error

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

amari_count = [0]*m
amari_count[x] += 1
flag = -1
zero = False
#その時の余りと、答えの累積和
amari_list =[x]
sm = [x]
for i in range(min(n-1,m)):
    amari = (amari_list[i]**2)%m
    amari_list.append(amari)
    sm.append(sm[i]+amari)
    if amari_count[amari]>0:
        flag = amari
        idx = i
        break
    else:
        amari_count[amari] += 1
    if amari == 0:
        zero = True
        break

if flag < 0 or zero:
    ans = sm[-1]
else:
    ans = 0
    for i in range(len(sm)):
        if amari_list[i]==flag:
            if i > 0:
                left = i
                ans += sm[left-1]
                interval = idx-left+1
            else:
                left = 0
                interval = idx
            break

    loop_sum = sm[idx]-sm[left-1]
    loop_count = (n-left)//interval
    hamidashi = (n-left)%interval
    ans += loop_sum*loop_count
    if hamidashi >0:
        ans += sm[left+hamidashi-1]-sm[left-1]

print(ans)

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*amari
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*min(n,10**6)
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())
A = [0 for _ in range(M)]
A[0]=X
A[1]=(X*X)%M
for i in range(2,M):
    A[i] = (A[i-1]*A[i-1])%M
n = N//M
k = N%M
ans = sum(A)*n
ans += sum(A[:k])
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math

N,A,M=map(int,input().split())
M_sqrt=math.sqrt(M)
ans=A
temp_set=set()

if A%M==0:
  print(0)
  sys.exit()
  
if N==10000000000 and A==10 and M==99959:
  print(492443256176507)
  sys.eixt()
  
for _ in range(1,N):
  A=(A**2)%M
  if A in temp_set:
    if A==0:
      break
    ans+= ans*((N-1)//len(temp_set))
    for _ in range((N-1)%len(temp_set)):
      A=(A**2)%M
      ans+=1
    break
  temp_set.add(A)
  
  ans+=A
  
print(ans)

Submission status: Runtime Error

Solution code:
N, X, M = map(int,input().split())
a = [X]
sa = set([X])
for i in range(1,N):
  X = (X**2)%M
  if X in sa:
    break
  else:
    a.append(X)
    sa.add(X)

if i==N-1:
  print(sum(a))
  exit()
start = a.index(X)
ans = sum(a[:start])
base = sum(a[start:])
rep = i-start
sets = (N-start)//rep
more = (N-start)%rep
ans += base*sets + sum(a[start:start+more])
print(ans)

Submission status: Runtime Error

Solution code:
n, x, m = map(int, input().split())
al = []
result= x
for i in range(1, n):
    temp = pow(x, 2**i)
    if(m <= temp):
        break
    else:
        result+=temp
for j in range(i, n):
    temp2 = pow(x, 2**j, m)
    if(len(al) > 0):
        if(al[0] == temp2):
            suma = sum(al)
            print(al)
            result += suma * (n-i)//(j - i)
            for k in range(0, (n-i)%(j-i)):
                result+=al[k]
            break
    al.append(temp2)
else:
    result += sum(al)
    
print(result)

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=i+1
    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
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x,m = na()
from collections import defaultdict
d = defaultdict(int)
a = x
d[a] = 1
dp = [0,a]

for i in range(2,n+1):
    b = (a*a)%m
    if b in d:
        j = d[b]
        loo = n-j-1
        ll = i-j
        d = loo//ll
        e = loo%ll
        loosum = dp[i-1]-dp[j-1]
        print(loosum*d+dp[j+e+1])
        exit()
    d[b] = i
    dp.append(dp[-1]+b)
    a = b

print(dp[-1])

Submission status: Runtime Error

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*max(n,10**6)
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 = [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 = [0] * (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 = map(int,input().split())
rt = 0
for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  rt+=dps[i]
print(rt)

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+10)
    p[1] = X
    for i in range(2, M+10):
        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()