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: Time Limit Exceeded

Solution code:

from __future__ import division, print_function
# import threading
# threading.stack_size(2**27)
# import sys
# sys.setrecursionlimit(10**7)
import sys
from sys import stdin, stdout
import bisect            #c++ upperbound
import math
import heapq
from collections import defaultdict as dd
##import numpy as np
##i_m=9223372036854775807
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
def msb(n):         #log2 for n <= 10**10
    n|=n>>1
    n|=n>>2
    n|=n>>4
    n|=n>>8
    n|=n>>16
    return n-(n>>1)
def GCD(x, y): 
    x=abs(x)
    y=abs(y)
    if(min(x,y)==0):
        return max(x,y)
    while(y): 
        x, y = y, x % y 
    return x
def pref(a,n):             #preSum array
    pre=[0]*n
    pre[0]=a[0]
    for i in range(1,n):
        pre[i]=a[i]+pre[i-1]
    return pre
##def Divisors(n) : #list of divisors
##    l = []  
##    for i in range(1, int(math.sqrt(n) + 1)) :
##        if (n % i == 0) : 
##            if (n // i == i) : 
##                l.append(i) 
##            else : 
##                l.append(i)
##                l.append(n//i)
##    return l
prime1=[]
def SieveOfEratosthenes(n): #list of primes upto n
    global prime1
    prime1 = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime1[p] == True): 
            for i in range(p * p, n+1, p): 
                prime1[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime1[p]: 
            f.append(p)
    return f
prime=[]
def Sieve(bo):
    global prime
    prime = [1 for i in range(bo)] 
    p = 2
    while (p<bo): 
        if (prime[p] == 1): 
            for i in range(p,bo, p): 
                prime[i] = p
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]==1: 
            f.append(p)
    return f
vi=[0]*(200005)
adj=[[] for i in range(200005)]
def dfs(node,ans):
    vi[node]=1
    ans+=[node+1]
    for j in adj[node]:
        if(vi[j]==0):
            dfs(j,ans)
    return ans

# https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py
def bootstrap(f, stack=[]):   #write @bootstrap before recursive func
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
 
    return wrappedfunc
def Divisors(n) : #list of divisors
    c=0 
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                c+=1
            else :
                c+=2
    return c
"""*******************************************************"""
def main():
    n,x,m=cin();f=0
    if(x==0):
        ans=0
    else:
        nmod=x%m
        store=[nmod];su=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]=i+1
                store+=[nmod]
                su+=nmod
            else:
                f=2
                cont=d[x%m]-1
                rem=n-i
                break
        if(f<=1):
            ans=su
        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=su+mul*remsum+k
    print(ans)
##    dp = np.full(10**5+1, 10**18, dtype=np.int64)
    
######## Python 2 and 3 footer by Pajenegod and c1729
 
# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.
 
# So on cf, use PyPy2 for best string performance.

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')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'
 
# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'R' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'R' [0]:
        A.append(sign*numb)
    return A
 
# threading.Thread(target=main).start()
if __name__== "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def seqSum(n, x, m):
    count = x
    prev = x
    temp = dict()   
    for i in range(1, n):
        now = prev % m * prev % m
        if temp.get(now) is None:                       
            prev = now % m
            count += now % m
            temp[now] = prev
        else:            
            prev = temp[now]
            count += temp[now]
            
    return count

i = list(map(int, input().rstrip().split()))
print(seqSum(i[0], i[1], i[2]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, x, m = map(int, input().split())
    a, buf = x, [x]
    for _ in range(n+1):
        a = a ** 2 % m
        if a not in buf:
            buf.append(a)
        else:
            nloop = buf[:buf.index(a)]
            loop = buf[buf.index(a):]
            break
    q = (n - len(nloop)) // len(loop)
    r = (n - len(nloop)) % len(loop)
    print(q * sum(loop) + sum(loop[:r]) + sum(nloop))
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, X: int, M: int):
    m = [-1] * M
    v = X

    cnt = 0
    while not(v in m):
        #print(v)
        #m.append(v)
        m[cnt] = v
        v = (v*v)%M
        cnt += 1
    #print(m,v)
    #print(m.index(v))
    a1  = m[:m.index(v)]
    a2 = m[m.index(v):cnt]
    l = (N-len(a1))//(len(a2))
    ll = (N-len(a1))%(len(a2))
    #print((len(a1)+ll))
    a3 = m[len(a1):(len(a1)+ll)]
    #print(a3)
    ans = sum(a1) + (l * sum(a2)) + sum(a3)
    print(ans)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, X, M)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

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

    start = N
    end = N

    cnt = [0 for i in range(M)]

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

    # print(A)

    # print(start,end)
    # print(A[start],temp)

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

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

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

    # print(straight)
    # print(loop)

    res = 0

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


    if start != N:
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
ans = 0
loopList = [0] * 10 ** 7
startcnt = 0
loopcnt = 0
loopval = 0
val = x
while True:
    if startcnt >= n or val >= m: break
    ans += val
    startcnt += 1
    val **= 2
if startcnt >= n: print(ans)
else:
    while True:
        val %= m
        if val == loopList[0]: break
        if loopcnt >= n - startcnt: 
            loopcnt = 0
            ans += loopval
            break
        loopcnt += 1
        loopList[loopcnt-1] = val
        loopval += val
        val **= 2
    if loopcnt == 0:
        print(ans)
    else:
        z = n - startcnt
        loop = z // loopcnt
        finish = z % loopcnt
        ans += loopval * loop
        ans += sum(loopList[0:finish])
        print(ans)

Submission status: Time Limit Exceeded

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];su=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]=i+1
                store+=[nmod]
                su+=nmod
            else:
                f=2
                cont=d[x%m]-1
                rem=n-i
                break
        if(f<=1):
            ans=su
        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=su+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: Time Limit Exceeded

Solution code:
li = list(map(int,input().split()))
n = li[0]
x = li[1]
m = li[2]
li2 = list()
li2.append(x)
z = x
tmp = -1
if(n==1):
    print(x)
    exit()

if(m==1):
    print(x)
    exit()

for i in range(n):
    z = (z*z)%m
    if(z == 0):
        break
    if(z in li2):
        tmp = li2.index(z)
        break
    else:
        li2.append(z)

if(tmp == -1):
    print(sum(li2))
else:
    nagasa = len(li2[tmp:])
    kekka = sum(li2)
    n = n - len(li2)
    q , mod = divmod(n,nagasa)
    kekka = kekka + sum(li2[tmp:])*q
    if(mod!=0):
        end = tmp+mod
        kekka = kekka + sum(li2[tmp:end])
    print(kekka)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
def ama(a,b):
  c=a%b
  return c
zen=[]
zen.append(x)
sum=0
sum+=x
num=-1
for i in range(n-1):
  x=ama(x**2,m)
  sum+=x
  if x==0:
    break
  if x in zen:
    num=zen.index(x)
    break
  zen.append(x)
def wa(x):
  w=0
  for i in range(len(x)):
    w+=x[i]
  return(w)
if num == -1:
  print(sum)
else:
  mae=zen[0:num]
  m=wa(mae)
  loop=zen[num:]
  l=wa(loop)
  naga=len(zen)-num
  sumsum=m+(int((n-num)/naga))*l+wa(zen[num:num+(int((n-num)%naga))])
  print(sumsum)

Submission status: Time Limit Exceeded

Solution code:
import math
N,X,M = map(int,input().split())
A = [M,X]
reccur = []
for i in range(2,N+1):
    xi = (A[i-1]**2)%M
    A.append(xi)
    try:
        ind = A[:-1].index(xi)
        reccur = A[ind:-1]
        break
    except:
        continue
if reccur:
    result = sum(A[1:-1]) + math.floor((N - len(A)+2)/len(reccur)) * sum(reccur) + sum(reccur[0:(N - len(A)+2)%len(reccur)])
else:
    result = sum(A[1:])
print(result)

Submission status: Time Limit Exceeded

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((list1[i-1])**2,M))
ans=sum(list1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, x, m = map(int, args[0].split())

    a = x
    ret = 0
    D = [0]*(m+1)
    for i in range(n):
        if 0 < D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, x, m = input().split()
N=int(n)
X=int(x)
M=int(m)

ans = X
A = X
l = []
l.append(A)

for i in range(1,N):
  if A == 0:
    break
  A = A*A % M
  if A in l:
    index = l.index(A)
    ko = len(l)-index
    rest = N-i-1
    wako = 0
    wa = 0
    for k in range(index,len(l)):
      wako += l[k]
    for z in range(index,index+(rest%ko)+1):
      wa += l[z]
    ans += wako*(rest//ko) + wa
    break
  l.append(A)
  ans += A
  

  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
[N, X, M] = [int(i) for i in input().split()]
a = X
ans = a
s = {}
for i in range(N-1):
    t = (a**2)%M
    ans += t
    a = t
print(ans)

Submission status: Time Limit Exceeded

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

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

data = [x]
i = None

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

l = len(data[i:])
if(n<i):
    print(sum(data[:n+1]))
    exit()
ans=sum(data[:i])
n-=i
k=n//l
s=n%l
ans+= sum(data[i:])*k
ans+=sum(data[i:s+i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

    _l = tuple([i**2 % M for i in range(M)])

    _a = X
    ans_l = [0] * M
    ans_l[0] = _a
    seq = [_a]
    s = g = 0
    for i in range(1, M):
        _a = _l[_a]
        ans_l[i] = _a + ans_l[i-1]
        if _a in seq:
            s = seq.index(_a)
            g = len(seq)-1
            break
        seq.append(_a)
    _tmp = N - s
    loop = _tmp // (g - s + 1)
    zan = _tmp % (g - s + 1)
    ans = ans_l[s-1] + (ans_l[g] - ans_l[s-1]) * loop + \
        (ans_l[s+zan-1] - ans_l[s-1])
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int,input().split())
a = [x]
ans = x
for i in range(n-1):
  b = a[i]*a[i] % m
  ans += b
  a.append(b)
print(ans)

Submission status: Time Limit Exceeded

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):
            ans=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: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
A = [X]
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(M):
  a = a ** 2 % M
  if A.count(a) >= 1:
    if a == 0:
      s = sum(A)
      break
    else:
      r0 = A.index(a)
      l = len(A[r0:])
      r = (N - i - 1) // l
      amari = (N - i - 1) % l
      s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
      break
  A.append(a)
  s += A[-1]

print(s)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

@njit
def solve(N, X, M):
    ans = 0
    a = X
    a0 = X
    for i in range(N):
        ans += a
        a = (a ** 2) % M
        if a == 1:
            ans += (N - i - 1)
            break
        if a == a0:
            w = i + 1
            k = N // w
            m = N % w
            ans *= k
            for i in range(m):
                ans += a
                a = (a ** 2) % M
            break
    return ans

N, X, M = [int(x) for x in input().split()]
ans = solve(N, X, M)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col

N,X,M = int_map()

L = [X]
now = X

num = 0

for i in range(0,N):
    now = (now**2)%M
    if now in L:
        break
    L.append(now)
    num += 1

start = 0

for i,l in enumerate(L):
    if l == now:
        start = i
        break

sub1 = sum(L[0:start])
sub2 = sum(L[start:num+1])

if len(L) == N:
    print(sum(L))
else:
    print(sub1 + sub2*((N-start)//(num+1-start)) + sum(L[start:start+(N-start)%(num+1-start)]))

Submission status: Time Limit Exceeded

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

res = X
remainder_list = set([X % M])
remainder_loop = []

a_part = []

flg = False

a = X

for i in range(N - 1):
    a = a ** 2 % M
    if a in remainder_list:
        res_loop = 0
        rem_trig = a
        cnt = 0
        a_part.append(a)
        a_tmp = a
        while True:
            remainder_loop.append(a)
            res_loop += a
            a = a ** 2 % M
            a_part.append(a_part[-1] + a)
            cnt += 1
            if a == rem_trig or cnt + i >= N:
                break
        if (N - i) % cnt - 2 == -1:
            res += ((N - i) // cnt) * res_loop
        elif (N - i) % cnt - 2 == -2:
            flg = True
        else:
            res += ((N - i) // cnt) * res_loop + a_part[(N - i) % cnt - 2]
        break
    else:
        remainder_list.add(a)
        res += a

if not flg:
    print(res)
else:
    a = X
    res = X
    for i in range(N - 1):
        a = a ** 2 % M
        res += a
    
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
a = [x]
if n == 1:
    print(x)
    exit()
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: Time Limit Exceeded

Solution code:
N, X, M = map(int,input().split())
ans = 0
ls = [X%M] + [-1]*(M+1)
for i in range(N):
    a = ls[i]
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls[i+1] in ls[:i]:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
A = [X]
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(N-1):
  a = a ** 2 % M
  if A.count(a) >= 1:
    if a == 0:
      s = sum(A)
      break
    else:
      r0 = A.index(a)
      l = len(A[r0:])
      r = (N - i - 1) // l
      amari = (N - i - 1) % l
      s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
      break
  A.append(a)
  s += A[-1]

print(s)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
A = X
T = [A]
ans = A

for n in range(1, N):
  tmp = A ** 2 % M
    
  if tmp == 0:
    break
    
  if tmp in T:    
    pre_tmp_idx = T.index(tmp)
    syuki = T[pre_tmp_idx:]
    
    len_syuki = len(syuki)
    
    nokori_syuki = (N - n) // len_syuki    
    syuki_amari = (N - n) % len_syuki
    
    ans += sum(syuki) * nokori_syuki + sum(syuki[:syuki_amari])
    break

  ans += tmp
  A = tmp
  T.append(tmp)
    
print(ans)

Submission status: Time Limit Exceeded

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


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


result = [x]
for i in range(n-1):
    a = x
    x = func(a, m)
    result.append(x)
print(sum(result))

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())  # 数列の項数N, 数列の第一項X, modM
MOD = M
A = [X]
# 1~N+1のN項
for _ in range(N-1):
    A.append(A[-1]**2%MOD)
print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

@njit
def solve(N, X, M):
    ans = 0
    a = X
    a0 = X
    for i in range(N):
        ans += a
        a = (a ** 2) % M
        if a == 1:
            ans += (N - i - 1)
            break
        if a == a0:
            w = i + 1
            k = N // w
            m = N % w
            ans *= k
            for i in range(m):
                ans += a
                a = (a ** 2) % M
    return ans

N, X, M = [int(x) for x in input().split()]
ans = solve(N, X, M)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

B = S = X
for n in range(2, N+1):
  A = f(B**2, M)
  S += A
  B = A

print(S)

Submission status: Time Limit Exceeded

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)
"""
import bisect
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)
if c==n:
    print(ans)
    sys.exit()

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

Submission status: Time Limit Exceeded

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


def func(x, n, m):
    list = [x]
    for i in range(1, n):
        list.append(f(list[i - 1] ** 2, m))
    return list


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

arr = [X]

An = X

while True:
  temp = An**2 % M
  
  if temp in arr:
    index = arr.index(temp)
    break
  
  An = temp
  arr.append(temp)

cc = arr[index:len(arr)]
cc_SUM = sum(cc)

#print(arr)
#print(index)

nokori = N - index

lenc = len(cc)

SUM = sum( arr[0:index] ) + cc_SUM * (nokori//lenc) + sum( cc[0:nokori%lenc] )

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int,input().split())
import sys
ans = 0
ls = [X%M] + [-1]*(M+1)
for i in range(N):
    a = ls[i]
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls[i+1] in ls[:i]:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    sys.exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)