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:
n, x, m = map(int,input().split())


def fxm(n, x, m):
    ans = [x]
    for i in range(1, n):
        ans.append(pow(ans[i - 1], 2, m))
    
    return ans

print(sum(fxm(n, x, m)))

Submission status: Time Limit Exceeded

Solution code:
def kai(N, X, M):
    A_n = [X]
    for i in range(1, N):
        A_i = (A_n[i-1] **2) % M
        A_n.append(A_i)
    return sum(A_n)

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n,x,m = map(int,input().split())
    ans = x
    y = [x]
    for i in range(n-1):
        x = (x**2)%m
        if x not in y:
            y.append(x)
        else:
            break
    b = y.index(x)
    N = len(y[b:])
    c = sum(y[b:])
    ans = sum(y[:b]) + c*((n-b)//N)+sum(y[b:b+(n-b)%N])
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, X, M = map(int, input().split())
    A = [X % M]
    setA = set(A)

    while True:
        a = (A[-1] ** 2) % M
        if a in setA:
            break
        A.append(a)
        setA.add(a)

    pre = A.index(a)
    ans = 0
    loop = A[pre:]
    length = len(loop)
    for i in range(1,N+1):
        if i-1 < pre:
            _ans = A[i-1]
        else:
            _ans = loop[(i-1 - pre) % length]
        ans += _ans
        _ans

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline

n, x, mod = map(int, input().split())
ans = 0
temp = x
num = 1
while temp < mod:
    temp *= x
    num += 1


A = [0] * (mod + 1)

if temp == mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, num + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
    print(ans)
    exit()

kouho = {}
if n < mod:
    A[1] = x % mod
    ans += A[1]
    for i in range(2, n + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        ans += A[i]
        # print(ans)
else:
    A[1] = x
    ans += A[1]
    kouho[A[1]] = 1
    for i in range(2, mod + 1):
        A[i] = A[i - 1] * A[i - 1] % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
    saisho = 0
    hidari = kouho[A[i]]
    for i in range(1, hidari):
        saisho += A[i]

    cycle_val = 0
    for i in range(hidari, migi):
        cycle_val += A[i]

    cycle = migi - hidari
    kaisu = n // cycle
    amari = n % cycle - (hidari - 1)
    amari %= cycle
    kaisu = (n - (amari + hidari - 1)) // cycle
    amari_val = 0
    for i in range(hidari, hidari + amari):
        amari_val += A[i]
    ans = saisho + cycle_val * kaisu + amari_val
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
roop_init = -1
roop_sum = 0
roop_len = 0
x = X
ans += x
flug = False    # 周期を数えるフラグ
for i in range(2, N+1):
    old_x = x
    x = old_x**2 % M
    if x == 0:
        print(ans)
        break
    if old_x**2 >= M and not flug:
        # print(old_x, x)
        flug = True
        roop_init = x
        roop_sum = x
        roop_len = 1
    elif x == roop_init and flug:
        # print(i)
        ans += (N - (i-1)) // roop_len * roop_sum
        for j in range((N - (i-1)) % roop_len):
            if j != 0:
                old_x = x
                x = old_x**2 % M
            ans += x
        print(ans)
        break
    elif flug:
        roop_len += 1
        roop_sum += x
    ans += x
else:
    print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int,input().split())
ans = 0
a = []
y = []
a.append(x)
ans += x
y.append(x%m)
flg = 0
for _ in range(n-1):
    a.append(y[-1]**2%m)
    ans += y[-1]**2%m
    y.append(a[-1]%m)
    if y[-1] in y[:-1]:
        ans -= a[-1]
        i = y[:-1].index(y[-1])
        h=len(y)-1

        one_loop = h-i
        loop_list = a[i:-1]
        flg= 1
        break

if flg ==1:
    
    ato= n-_-1
    ans+=(ato//one_loop)*sum(loop_list)
    ans += sum(loop_list[:(ato%one_loop)])
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
i = list(map(int, input().split()))
a = i[1]
count = i[1]
for j in range(i[0]-1):
    a = a * a % i[2]
    count += a
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
S = [0] * 1
S[0] = X
for i in range(1, N):
    temp = S[i-1]**2 % M
    S.append(temp)
summ = sum(S)
print(summ)

Submission status: Time Limit Exceeded

Solution code:
import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict,deque
import math
def main():
    n,x,m=map(int,input().split())
    su=x
    t=x
    i=1
    while i<n:
        a=pow(t,2,m)
        su+=a
        if a==0:
            break
        t=a
        i+=1
    print(su)
# region fastio
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

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


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        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: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
ans =x
before =x
for _ in range(n-1):
    new = (before**2)%m
    ans += new
    before= new
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
A = [x]
ans = x

for i in range(1,n):
    buf = A[i-1]*A[i-1] % m
    if buf in A:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        ans += sum(A[idx:idx+last])
        break
    else:
        A.append(buf)
        ans += buf

print(ans)

Submission status: Time Limit Exceeded

Solution code:
d=list(map(int,input().split()))


A=[]
A.append(d[1])

for i in range(d[0]):
  if i==d[0]-1:
    break
  A.append(A[i]**2%d[2])

print(sum(A))

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
ans = x
i = 1
for i in range(n-1):
    an_1 = x**2 % m
    ans += an_1
    x = an_1
    i += 1
print(str(ans))

Submission status: Time Limit Exceeded

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


n,x,m = map(int, readline().split())
a = x
ans = x
res = n-1
path = [x]
for _ in range(n-1):
    a = (a*a) % m
    if a in path:
        index = path.index(a)
        loop_list = path[index:]
        sho = res // len(loop_list)
        amari = res % len(loop_list)
        ans += sum(loop_list)*sho + sum(loop_list[:amari])
        break
    else:
        path.append(a)
        ans += a
        res -= 1
print(ans)

Submission status: Time Limit Exceeded

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

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

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

if len(A)==N:
    ans=sum(A)
else:
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

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


print(ans)

Submission status: Time Limit Exceeded

Solution code:
a=list(map(int, input().split()))
x=a[1]
re=x
x=a[1]%a[2]
for i in range(a[0]-1):
  x=x*x%a[2]
  re+=x
print(re)

Submission status: Time Limit Exceeded

Solution code:
d=list(map(int,input().split()))

X=d[1]%d[2]

A=[]
A.append(d[1])
B=0

cnt=0

# def war(a,b):
#   B=a**2%b
#   A.append(a**2%b)
#   cnt+=2

#   if cnt==d[0]:
#     return A

#   war(B,b)

for i in range(d[0]):
  if i==d[0]-1:
    break
  A.append(A[i]**2%d[2])

print(sum(A))


# print(war(d[1],d[2]))
# print(d)

Submission status: Time Limit Exceeded

Solution code:
line = input().split()
line = [int(a) for a in line]

ans = line[1]
num = line[1]
for i in range(line[0]-1):
  num = (num**2)%line[2]
  ans+=num
print(ans)

Submission status: Time Limit Exceeded

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

first_A = [X]
mod_M = [False for i in range(M)]

is_break = False
for i in range(min(N-1,M+1)):
    A_n1 = pow(first_A[-1],2)%M
    if A_n1 in first_A+[1,0]:
        is_break = True
        last_num = A_n1
        break
    else:
        first_A.append(A_n1)

if is_break:
    if last_num == 0:
        print(sum(first_A))
    elif last_num == 1:
        nokori = N-len(first_A)
        print(sum(first_A)+nokori)
    else: # roop
        loop_idx = first_A.index(last_num)
        first_A, second_A = first_A[:loop_idx], first_A[loop_idx:]
        roop = int((N-len(first_A))/len(second_A))
        nokori_kaisuu = (N-len(first_A)) - (roop*len(second_A))
        if nokori_kaisuu == 0:
            print(sum(first_A)+(sum(second_A)*roop))
        else:
            print(sum(first_A)+(sum(second_A)*roop)+sum(second_A[:nokori_kaisuu]))
else:
    print(sum(first_A))

Submission status: Time Limit Exceeded

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

ans = X
rem = X
for i in range(1, N):
    X = rem ** 2
    rem = X % M
    ans += rem

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
ans = x
i = 1
while i <= n-1:
    an_1 = x**2 % m
    ans += an_1
    x = an_1
    i += 1
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    st=set()
    N,X,M=list(map(int,sys.stdin.readline().split()))
    L=[]
    a=-1
    for i in range(N):
        a=pow(X,2<<(i-1) if i else 1,M)
        if a in st:
            break
        else:
            st.add(a)
            L.append(a)

    n=N
    if a+1:
        idx=L.index(a)
        res=sum(L[:idx])
        n-=idx

        s=sum(L[idx:])
        length=len(L)-idx
        res+=s*(n//length)
        res+=(sum(L[idx:idx+n%length]))
        print(res)
    else:
        print(sum(N))



main()

Submission status: Time Limit Exceeded

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

n, x, m = map(int, input().split())
A = [x]
ans = x

for i in range(1,n):
    buf = f(A[i-1]**2, m)
    if buf in A:
        idx = A.index(buf)
        back = len(A) - idx
        nokori = n-len(A)
        sumKurikaeshi = sum(A[idx:])
        ans += int(nokori/back)*sumKurikaeshi
        last = nokori%back
        for j in range(last):
            ans += A[idx+j]
        break
        
    else:
        A.append(buf)
        ans += buf

print(ans)

Submission status: Time Limit Exceeded

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

ans = []
flag = False
for i in range(n):
    if x in ans:
        v = x
        flag = True
        break
    ans.append(x)
    x = x**2 % m
if flag:
    p = ans.index(v)
    l = len(ans) - p
    d, e = divmod(n-p, l)
    print(sum(ans[:p]) + d*sum(ans[p:]) + sum(ans[p:p+e]))
else:
    print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
ind = 0
l = [X]
while True:
  t = l[-1] ** 2 % M
  if t not in l:
    l.append(t)
  else:
    ind = l.index(t)
    break
S = sum(l[ind:])
L = len(l)
ans = 0
if N <= L:
  ans = sum(l[:N])
else:
  ans = sum(l)
  N -= L
  ans += S * (N // (L - ind))
  ans += sum(l[ind:ind+(N % (L - ind))])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#絶対TLEだけど
N,X,M = map(int,input().split())
A = X
ans = A
for i in range(N-1):
    A = (A**2) % M
    ans = ans + A
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
an = x
ans = an
i = 1
while i <= n-1:
    an_1 = an**2 % m
    ans += an_1
    an = an_1
    i += 1
    
print(str(ans))

Submission status: Time Limit Exceeded

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

sum = 0
A1 = X
Ap = A1

sum = sum + Ap

for i in range(1, N):
    Anext = (Ap*Ap)%M
    sum = sum + Anext
    Ap = Anext

print(sum)

Submission status: Time Limit Exceeded

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

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

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

if len(A)==N:
    ans=sum(A)
else:
    ans=0
    l=len(A)-s

    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    ans+=sum(A[s:(s+K)])
    


print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
print(x + sum((x := pow(x, 2, m) for i in range(n-1))))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(n):
    ans += x
    x = x**2 % m
    if x == 0:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
N = a[0]
X = a[1]
M = a[2]
def main():
  total = X
  am = X
  for t in range(1,N):
    am = am**2%M
    total += am
  print(total)
main()

Submission status: Time Limit Exceeded

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

A.append(X)
if N > 1:
  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
    else:
      A.append(a)
      s += A[-1]
  
print(s)

Submission status: Time Limit Exceeded

Solution code:
#絶対TLEだけど
N,X,M = map(int,input().split())
A = X
ans = A
for i in range(N-1):
    A = (A**2) % M
    ans = ans + A
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
a = x
ans = x
res = n-1
path = [x]
for _ in range(n-1):
    a = (a*a) % m
    if a in path:
        index = path.index(a)
        loop_list = path[index:]
        sho = res//len(loop_list)
        amari = res % len(loop_list)
        ans += sum(loop_list)*sho + sum(loop_list[:amari])
        break
    else:
        path.append(a)
        ans += a
        res -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def func(A, M):
    return A * A % M


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

total = X
A = X
for _ in range(1, N):
    A = func(A, M)
    total += A

print(total)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,X,M=map(int, input().split())
A=[X]
for i in range(1,M+1):
  d=pow(A[i-1],2,M)
  if d in A:
    break
  A.append(d)
c=A.index(d)
e=len(A)
cy=e-c
ans=0
if N<=e:
  for i in range(N):
    ans+=A[i]
  print(ans)
else:
  m=sum(A[:c])
  n=sum(A[c:e])
  #print(m,n)
  f=(N-c)//cy
  ans=m+n*f+sum(A[c:c+((N-c)%cy)])
  print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

l = [x]
p = x
f = 0
for i in range(2, n+1):
	if p * p < m:
		if p*p not in l:
			l.append(p*p)
			p = p*p
		else:
			f = 1
			s = l.index(p*p)
			b = i - s - 1
			t = (n - i + 1) // b
			a = (n - i + 1) % b
			w = sum(l[s:s+b])
			l.append(w*t)
			l.append(sum(l[s:s+a]))
			break  
	else:
		if (p*p) % m not in l:
			l.append((p*p) % m)
			p = (p*p) % m
		else:
			f = 1
			s = l.index((p*p) % m)
			b = i - s - 1
			t = (n - i + 1) // b
			a = (n - i + 1) % b
			w = sum(l[s:s+b])
			l.append(w*t)
			l.append(sum(l[s:s+a]))
			break  
print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
get = lambda  : int(input())
getlist = lambda : list(map(int, input().split(" ")))

n,x,m = getlist()

ans = x
ele = x
for i in range(n-1):
    ele = ele*ele % m
    ans += ele

print(ans)

Submission status: Time Limit Exceeded

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

def solve():
    n,x,m=map(int,input().split())
    ans = x
    dp = [-1]*(int(1e5)+1)
    for i in range(n-1):
        if dp[x]==-1:
            val = pow(x,2,m)
            dp[x]=val
        else:
            val = dp[x]
        ans+=val
        x = val
        if x==0:
            break
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
N = a[0]
X = a[1]
M = a[2]
sum = X

for i in range(N-1):
    X = (X**2)%M
    sum = sum + X
print(sum)

Submission status: Time Limit Exceeded

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

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

a=x
result=a
for i in range(2,n+1):
    a=f(a**2,m)
    result+=a
print(result)

Submission status: Time Limit Exceeded

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

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

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

if len(A)==N:
    ans=sum(A)
else:
    ans=0
    l=len(A)-s

    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    for i in range(K):
        ans+=A[i+s]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m= list(map(int, input().strip().split()))
a=[0]*(m)
for i in range(m):
    a[i]=i*i%m
a=list(set(a))
t=0
b=[]
b.append(x)
for i in range(m+1):
        b.append(b[-1]**2%m)
        if len(b)>len(list(set(b))):
            break
l=len(b)
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class Doubling():
    def __init__(self, a0, M):
        """
        a0 is an array-like object which contains ai, 0 <= i < N.
        ai is the next value of i.
        """
        N = len(a0)
        self.N = N
        self.nt = [[None] * N for i in range(M.bit_length()+1)]
        for i, a in enumerate(a0):
            self.nt[0][i] = a

        for i in range(1, len(self.nt)):
            for j in range(N):
                if self.nt[i-1][j] is None:
                    self.nt[i][j] = None
                else:
                    self.nt[i][j] = self.nt[i-1][self.nt[i-1][j]]

    def apply(self, i, n):
        """
        Apply n times from i
        """
        j = i
        for k in range(n.bit_length()):
            m = 1 << k
            if m & n:
                j = self.nt[k][j]
            if j is None:
                break
        return j


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M
    if math.gcd(X, M) != 1:
        for _ in range(N):
            ans += x
            x *= x
            x %= M
            if x == 0:
                break
        return ans
    else:
        x = X
        s = [X]
        u = set()
        while True:
            x *= x
            x %= M
            s.append(x)
            if x in u:
                break
            u.add(x)

        i = s.index(s[-1])
        if i + 1 >= N:
            return sum(s[:N]) % M

        N -= i
        ans += sum(s[:i])

        s = s[i:]
        s.pop()
        ss = sum(s)
        ans += (N // len(s)) * ss
        ans += sum(s[:N%len(s)])
        return ans


def main():
    N, X, M = read_int_n()
    print(slv(N, X, M))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        n,x,m = map(int,input().split())
        #print(n,x,m)
        prev = x
        ans = x
        for i in range(1,n):
            ans += (prev**2)%m
            prev = (prev**2)%m
        
        print(ans)
    except:
        break

Submission status: Time Limit Exceeded

Solution code:
y = input().split(" ")
n = int(y[0])
x = int(y[1])
m = int(y[2])
z = int(y[1])

for i in range(n-1):
  x = x**2%m
  z += x
print(z)

Submission status: Time Limit Exceeded

Solution code:
n,x,m= list(map(int, input().strip().split()))
a=[0]*(m)
for i in range(m):
    a[i]=i*i%m
a=list(set(a))
t=0
b=[]
b.append(x)
for i in range(m+1):
        b.append(b[-1]**2%m)
        if len(b)>len(list(set(b))):
            break
l=len(b)
for i in range(l-1):
    if b[i]==b[l-1]:
        q=i
w=l-2-q+1
s=0
for i in range(q):
    s+=b[i]
t=0
for i in range(q,l-1):
    t+=b[i]
u=(n-q)//w
v=(n-q)%w
ans=0
for i in range(q,q+v):
    ans+=b[i]
ans+=s+u*t

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc_dynamic(n, x, m):
    # 結果を保持する辞書
    cal_result = {}

    # 初期値の設定
    cal_result[1] = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result[i+1] = cal_result[i] ** 2 % m

    #return cal_result[n]
    return sum(cal_result.values())

def calc_dynamic2(n, x, m):
    cal_result_0 = 0
    cal_result_1 = 0

    # 初期値の設定
    cal_result_0 = x
    total = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1

    return total

def calc_dynamic3(n, x, m):
    # 結果を保持する辞書
    cal_result = {}
    cal_result_0 = 0
    cal_result_1 = 0
    loop_range = (0,0)

    # 初期値の設定
    cal_result_0 = x
    total = x

    if n == 1:
        return x

    for i in range(1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1
        if cal_result_1 in cal_result:
            loop_range = (cal_result[cal_result_1], i, cal_result_0, cal_result_1)
            break
        else:
            cal_result[cal_result_1] = (i, total)

    if i == n-1:
        return total

    hoge = i
    r = i - loop_range[0][0]
    v = total - loop_range[0][1]
    hoge += r
    while hoge < n:
        total += v
        hoge += r

    cal_result_0 = loop_range[2]
    cal_result_1 = loop_range[3]
    for i in range(hoge-r+1, n):
        cal_result_1 = cal_result_0 * cal_result_0 % m
        cal_result_0 = cal_result_1
        total += cal_result_1

    return total

[n, x, m] = map(lambda x: int(x), input().split(" "))
print(calc_dynamic3(n, x, m))

Submission status: Time Limit Exceeded

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

ans = X
for i in range(N-1):
  X = X**2 % M
  ans += X

print(ans)

Submission status: Time Limit Exceeded

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

amari = [x]
cnt = 0
p = 0

for i in range(n-1):
	a = amari[-1]**2 % m
	if a in amari:
		p = amari.index(a)
		cnt = i+1-p
		break
	else:
		amari.append(a)

if cnt == 0:
	print(sum(amari))
	
else:
	n -= len(amari)
	a = n // cnt
	b = n % cnt
	print(sum(amari)+a*sum(amari[p:])+sum(amari[p:(p+b)]))

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
N = a[0]
X = a[1]
M = a[2]
total = X
am = X
for t in range(1,N):
  am = am**2%M
  total += am
print(total)

Submission status: Time Limit Exceeded

Solution code:
N,X,M=map(int,input().split())
sum=0
for i in range(N):
  sum+=X
  X=(X**2)%M
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n=list(map(int,input().split()))
result = n[1]
next_in = n[1]**2
b = n[2]
a = 0
while a < n[0]:
    if next_in < b:
        result += next_in
        next_in = pow(next_in,2)
        continue
    elif next_in > b:
        c = next_in % b
        result += c
        next_in = pow(c,2)
        continue
    else:
        next_in = pow(next_in,2)
        continue
    a+=1
print(result)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
ans = X
ALL = []
rou = False
for i in range(N-1):
    X = pow(X, 2, M)
    if X in ALL:
        num = ALL.index(X)
        now = i
        rou = True
        break
    ALL.append(X)
    ans += X
if rou :
    roupe = now - num 
    nokori = N - now -2
    print(sum(ALL[num:])*(nokori//roupe) + ans + sum(ALL[num:num + nokori%roupe + 1]))
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
def am(a, b):
    return (a * a) % b
l = [x]
u = []
now = x
for i in range(n):
    s = am(now, m)
    if(s in l):
        break
    l.append(s)
    now = s
c = l.index(s)
k = 0
if(0 in l):
    print(sum(l))
else:
    for i in range(c):
        u.append(l.pop(0))
    a = (n-len(u)) // len(l)
    b = (n-len(u)) % len(l)
    print(sum(u) + a * sum(l) + sum(l[:b]))

Submission status: Time Limit Exceeded

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

print(sum(A))

Submission status: Time Limit Exceeded

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

Visited = [0]*(M+1)
Mods = [0]*(M+1)
count = 0

for i in range (0, M):
	if (i**2)%M == i:
		Mods[i]=1
        
latest = 0
        
for i in range (0, N):
	if X in Mods:
		count+=((N-i)*X)
		for j in range (0, M+1):
			count+=(j*Visited[j])
		print(count)
		exit()
	if Visited[X] > 0:
		latest = X
		break
	Visited[X]+= 1
	X = (X**2)%M

P = sum(Visited)

for j in range (0, M+1):
	count+=(j*Visited[j])

Visited = [0]*(M+1)

if P == N:
	print(count)
	exit()

crouch = [0]
looper = 0
debu = 0 

for i in range (0, N-P):
	if Visited[X] > 0:
		looper = i
		debu = 1
		break
	else:
		crouch.append(X+crouch[-1])
	Visited[X]+= 1
	X = (X**2)%M
    
if debu == 0:
	for j in range (0, M+1):
		count+=(j*Visited[j])
	print(count)
	exit()
else:
	loops = 0
	for j in range (0, M+1):
		loops+=(j*Visited[j])
	count+=(loops*((N-P)//looper))
	count+=crouch[(N-P)%looper]
print(count)

Submission status: Time Limit Exceeded

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

n = int(n)
x = int(x)
m = int(m)

total = x
prev_a = x

for i in range(1, n):
  a = prev_a ** 2 % m
  if a == 0:
    break
  total += a
  prev_a = a

print(total)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
pre = x
ans = x
for i in range(1,n):
	t = (pre*pre)%m
	if t == 0:
		break
	ans += t
	pre = t
	#print(i)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
mod_list = [-1 for i in range(m)]
value = x
i = 0
head = 0
while i < n:
    if value not in mod_list:
        mod_list[i] = value
        i += 1
        value = (value**2)%m
    else:
        head = mod_list.index(value)
        break
if i == n:
    print(sum(mod_list[:n]))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print(sum(mod_list[:head]) + sum(mod_list[head:i])*block_num + sum(mod_list[head:head+(n-head)%block_size]))

Submission status: Time Limit Exceeded

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

print(sum(A))