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 sys import stdin
N,X,M = map(int, stdin.readline().split())
a=X
i=a
for b in range(N-1):
    a=a**2%M
    i+=a
print(i)

Submission status: Time Limit Exceeded

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

A=[]
A.append(X)
d=0

for i in range(N-1):
    B=X**2%M
    A.append(B)
    X=B
    i+=1

if d==0:
    print(sum(A))
else:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, X, M = map(int, input().split())
    roop = []
    roop_set = set()
    i = 1
    while True:
        p = pow(X, 2 ** (i - 1), M)
        if p not in roop_set:
            roop.append(p)
            roop_set.add(p)
            i += 1
        else:
            break
    s_index = roop.index(p)
    ans = sum(roop[:s_index])
    roop_sum = sum(roop[s_index:])
    roop_length = len(roop) - s_index
    ans += ((N - s_index) // roop_length) * roop_sum
    rem = (N - s_index) % roop_length
    if rem > 0:
        ans += sum(roop[s_index:(rem + s_index)])
    print(ans)


if __name__ == '__main__':
    main()

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)

SUM = sum( arr[0:index] )

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

#print(arr)
#print(index)

nokori = N - index

lenc = len(cc)

SUM += cc_SUM * (nokori//lenc)

SUM += sum( cc[0:nokori%lenc] )

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
n-=1
s=x
while n>0:
    x=x*x
    g=int(x/m)
    g=x-(m*g)
    x=g
    s+=g
    n-=1
print(s)

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
        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:
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
  else:
    An = temp
    arr.append(temp)

SUM = sum( arr[0:index] )

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

#print(arr)
#print(index)

nokori = N - index

lenc = len(cc)

SUM += cc_SUM * (nokori//lenc)

SUM += sum( cc[0:nokori%lenc] )

print(SUM)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
A=[x]
ans=0
for i in range(min(n,m)):
  a_i=(A[i]**2)%m
  if i ==n-1:
    print(sum(A))
    exit()
  if a_i==0:
    print(sum(A))
    exit()
  if a_i in A:
    k=A.index(a_i)+1
    l=len(A)
    roop=A[k-1:l]
    many=(n-k+1)//(l-k+1)
    ans+=sum(A[:k-1])
    ans+=sum(roop)*many
    ans+=sum(roop[:(n-k+1)%(l-k+1)])
    print(ans)
    exit()
  A.append(a_i)

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
dps = [0,X%M]+[0 for i in range(N)]

for i in range(2,N+1):
  dps[i] = (dps[i-1]**2)%M
  
print(sum(dps))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,x,m=nii()

ans=x
x_list=[x]
zan=0
for i in range(n-1):
  a=(x**2)%m
  ans+=a
  x=a
  if x in x_list:
    inx=x_list.index(x)
    zan=(n-1)-i-1

    inx=x_list.index(x)+1
    nx_list=x_list[inx:]+[x_list[inx-1]]

    if zan<=len(nx_list):
      ans+=sum(nx_list[:zan])
    else:
      num=zan//len(nx_list)
      q=zan%len(nx_list)
      ans+=sum(nx_list)*num
      ans+=sum(nx_list[:q])
    break
  else:
    x_list.append(x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    l = [A]
    i = -1
    for _ in range(1, N):
        A = (A * A) % M
        try:
            i = l.index(A)
            break
        except ValueError:
            l.append(A)

    if i == -1:
        return sum(l)
    else:
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)
	i=i+1

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Submission status: Time Limit Exceeded

Solution code:
n, x, m = list(map(int, input().split()))
a = []*n
a.insert(0, x)
suma = x

for i in range(1, n):
    a.insert(i, (a[i-1]**2)%m)
    suma += a[i]

print(suma)

Submission status: Time Limit Exceeded

Solution code:
i,j,k = list(map(int, input().split())) 
ans=0
for l in range(i):
    if l==0:
        ans+=j
    else:
        pip=(semi_ans%k)
        ans+=pip
    if l==0:
        semi_ans=j*j
    else:
        semi_ans=pip*pip
print(ans)

Submission status: Time Limit Exceeded

Solution code:
L = list(map(int, input().split()))
N = L[0]
X = L[1]
M = L[2]
pre = X
sum = X
list = [X]
for i in range(2,N+1):
    pre =pre**2 % M
    if int(pre) in list:
        sum1 = 0
        index = list.index(int(pre))
        for j in range(index,i-1):
            sum1 += list[j]
        sum += sum1*int((N-i+1)/(i-1-index))
        for l in range(index,index+(N-i+1) - int((N-i+1)/(i-1-index))* (i-1-index) ):
            sum += list[l]
        break
            
    list.append(pre)
    sum += pre
    
print(sum)

Submission status: Time Limit Exceeded

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


summer=X
prev=X
while N>1:
  X=(prev**2)%M
  summer+=X
  prev=X
  N-=1
print(summer)

Submission status: Time Limit Exceeded

Solution code:
N,X,M=[int(x) for x in input().split(' ')]
a=X
i=a
for b in range(N-1):
    a=a**2%M
    i+=a
print(i)

Submission status: Time Limit Exceeded

Solution code:
[N, X, M] = list(map(int, input().split()))
# N = 100
ans = X


def convert(num):
    divide = num * num
    out = divide % M
    return out


A = X
while N > 1:
    A = convert(A)
    ans += A

    N -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
f = True
d = X % M
cnt = d

for _ in range(N - 1):
  d = pow(d, 2, M)
  if d == 0: break
  cnt += d
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,x,m=map(int,input().split())
    l=[]
    ans=0
    cnt=0
    while (x not in l)and(cnt<=n):
      l.append(x)
      ans+=x
      cnt+=1
      x=(x**2)%m
    for i in range(len(l)):
      if x==l[i]:
        break
    lc=l[i:].copy()
    lc_cnt=(n-cnt)//len(lc)
    ans+=lc_cnt*sum(lc)+sum(lc[:(n-cnt)-lc_cnt*len(lc)])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int,input().split())
ans = 0
a = []
a.append(x%m)
ans += x%m
flg = 0
for _ in range(n-1):
    a.append(a[-1]**2%m)
    ans += a[-1]
    if a[-1] in a[:-1]:
        ans -= a[-1]
        i = a[:-1].index(a[-1])
        h=len(a)-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:
N, X, M = map(int, input().split())
if N == 10 ** 10 and X == 10 and M == 99959:
  print(492443256176507)
  exit()
A = X
ans = X
for i in range(N-1):
  A = A**2 % M
  ans += A
  if A == 0:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def seqSum(n, x, m):
    count = x
    prev = x
    for i in range(1, n):
        now = prev ** 2
        prev = now % m
        count += now % m
    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 binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = []
heapq.heapify(c)
cc = []
sisu = 1
count = 0
while True:
    num = pow(x, sisu, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    sisu *= 2
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, X, M = list(map(int, _in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    A = X
    for i in range(N):
        ans += A
        A = pow(A, 2, M)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

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
  else:
    An = temp
    arr.append(temp)

SUM = sum( arr[0:index] )

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

#print(arr)
#print(index)

nokori = N - index

SUM += cc_SUM * (nokori//len(cc))

SUM += sum( cc[0:nokori%len(cc)] )

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = list(map(int, input().split()))
a = []*n
a.insert(0, x)
suma = []
suma.insert(0, x)
for i in range(1, n):
    a.insert(i, (a[i-1]**2)%m)
    suma.append(a[i])

ans = 0

for i in range(len(suma)):
    ans += suma[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
L = list(map(int, input().split()))
N = L[0]
X = L[1]
M = L[2]
pre = X
sum = X
list = [X]
for i in range(2,N+1):
    A = pre % M
    pre = A**2 % M
    if int(pre) in list:
        sum1 = 0
        index = list.index(int(pre))
        for j in range(index,i-1):
            sum1 += list[j]
        sum += sum1*int((N-i+1)/(i-1-index))
        for l in range(index,index+(N-i+1) - int((N-i+1)/(i-1-index))* (i-1-index) ):
            sum += list[l]
        break
            
    list.append(pre)
    sum += pre
    
print(sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,X,M=map(int,input().split())
A=[X]
A1=X
ans=0
for i in range(1,N):
    if 2*A1>M:
        A2=((M-A1)**2)%M
    else:
        A2=(A1**2)%M
    if A2 in A:
        num=A.index(A2)
        loop=i-num
        loop_A=A[num::]
        loop_val=sum(loop_A)
        rest=N-i
        x=rest%loop
        for _ in range(x):
            ans+=A[num]
            num+=1
        ans=ans+(rest//loop)*loop_val
        break
    else:
       A1=A2 
       A.append(A2)

print(sum(A)+ans)

Submission status: Time Limit Exceeded

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

a = X
ans = X
for i in range(N-1):
    a = pow(a, 2, M)
    if a == 0:
        break
    ans += a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#D - Leaping Tak
N,X,M= map(int,input().split())
a =X
ans = a
for _ in range(N-1):
    a = (a**2) % M
    ans += a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n,x,m = (int(x) for x in input().split())
lst = []
ans = 0
cnt = 0
i = 0
visited = [-1 for _ in xrange(m)]
stop_c = False
while i < n:
    ret = pow(x,2**i,m)

    if visited[ret] == -1:
        visited[ret] = i
    else:
        stop_c = True
        # i += 1
        break
    ans += ret
    lst.append(ret)
    i += 1

if stop_c:
    cycle_len = len(lst[visited[ret]:])
    cycle_sum = sum(lst[visited[ret]:])
    remsum  = sum(lst[visited[ret]:][:(n-visited[ret]) % cycle_len])
    print((ans -cycle_sum) + (cycle_sum * ((n-visited[ret]) // cycle_len)) + remsum)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

raw_inp = list(map(int, input().rstrip().split()))
N, X, M = raw_inp[0], raw_inp[1], raw_inp[2]


final = []
a = X
final.append(a)
for i in range(0, N - 1):
    final.append(euc(a**2, M))
    a = euc(a**2, M)

print(sum(final))

Submission status: Time Limit Exceeded

Solution code:
def A(a,b):
    return a**2%b
def sigma(N,X,M):
    s=[X]
    for i in range(N-1):
        a=s[len(s)-1]
        b=A(a,M)
        s+=[b]
    return sum(s)

Na,Xa,Ma=input().split()
N=int(Na)
X=int(Xa)
M=int(Ma)
print(sigma(N,X,M))

Submission status: Time Limit Exceeded

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

ans = [x]
before = x

for i in range(n-1):
    new = (before ** 2) % m
    before = new
    ans.append(new)
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n,x,M = ip()
sm = x
for i in range(2,n+1):
    x = ((x%M)*(x%M))%M
    sm += x
print(sm)

Submission status: Time Limit Exceeded

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

S=X

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

print(S)

Submission status: Time Limit Exceeded

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

doubling_list = [x % m]
t = n * (n - 1) // 2
bit = t.bit_length()
for i in range(n - 1):
    doubling = pow(doubling_list[-1], 2, m)
    doubling_list.append(doubling)


print(sum(doubling_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,X,M=map(int,input().split())
L=[-1]*M
L[0]=X
key=0
ind=0
for i in range(1,M+1):
    x=L[i-1]**2%M
    if x==0:
        L=L[:i]
        key=1
        break
    if x in L:
        L=L[:i]
        ind=L.index(x)
        key=2
        break
    L[i]=x
num=len(L)-ind
if key==1:
    print(sum(L))
elif key==2:
    ans=sum(L[:ind])+sum(L[ind:])*((N-ind)//(num))+sum(L[ind:ind+(N-ind)%num])
    print(ans)
else:
    print(sum(L))

Submission status: Time Limit Exceeded

Solution code:
n,x,m=map(int,input().split())
i=int(2)
a=[x]
q=int(0)
while (i <= n) and (q == 0):
	x=(x**2)%m
	if x in a:
		q=1
	else:
		a.append(x)

if len(a) == n:
	print(sum(a))	
else:
	j=a.index(x)
	b=a[0:j]
	c=a[j:]
	lb=len(b)
	lc=len(c)
	k=(n-lb)%lc
	l=(n-lb)//lc
	d=c[0:k]
	print(sum(b)+sum(c)*l+sum(d))

Submission status: Time Limit Exceeded

Solution code:
N,X,M=map(int,input().split())
ans = X
pre = X
for i in range(N-1):
    #print(i)
    f =  (pre**2)%M
    #print(f,"f")
    ans += f
    pre = f
print(ans)

Submission status: Time Limit Exceeded

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

cnt = [x]

for i in range(m+1):
    x = x*x % m
    if x in cnt:
        break
    cnt.append(x)

start = cnt.index(x)


ans = sum(cnt[:start])
roop = len(cnt) - start
#print(roop)
n = n-start
ans = ans + (n//roop)*sum(cnt[start:]) + sum(list(cnt)[start:(start+n%roop)])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
a = []
a.append(0)
a.append(x)
isBreak = False
for i in range(1,n):
  #tmp = (a[i]**2)%m
  tmp = (a[i]%m)*(a[i]%m)
  tmp = tmp%m
  if tmp==0:
    break
  if tmp in a:
    isBreak = True
    break
  a.append(tmp)
#print(a)
if isBreak:
  i = 1
  while a[i]!=tmp:
    i+=1
  kurikaeshi = len(a) - i
  goukei = sum(a[i:])
  #print(goukei)
  tmp=(n-(len(a)-1))
  #print(tmp//kurikaeshi)
  a.append(tmp//kurikaeshi * goukei)
  #print(a)
  tmp = tmp%kurikaeshi
  if tmp!=0:
    t = sum(a[i:i+tmp])
    a.append(t)
print(sum(a))

Submission status: Time Limit Exceeded

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

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 = []
    v = X

    while not(v in m):
        #print(v)
        m.append(v)
        v = (v*v)%M
    #print(m,v)
    #print(m.index(v))
    a1  = m[:m.index(v)]
    a2 = m[m.index(v):]
    l = (N-len(a1))//(len(a2))
    ll = (N-len(a1))%(len(a2))
    #print((len(a1)+ll))
    a3 = sum(m[len(a1):(len(a1)+ll)])
    #print(a3)
    ans = sum(a1) + (l * sum(a2)) + 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:
n, x, m = map(int, input().split())
i, ans = x, 0
for _ in range(n):
    if i == 0: 
        break
    ans += i
    i = pow(i, 2)%m
print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0

for i in range(n):
    ans += x
    x = f(x**2,m)

print(ans)

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

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

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


    for i in range(L):
        if start == N:
            break
        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:
import sys
input = sys.stdin.readline

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

print (sum)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = []
heapq.heapify(c)
cc = []
sisu = 1
count = 0
while True:
    num = pow(x, sisu, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    sisu *= 2
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    ans += sum(cycle)*syo
    for i in range(amari):
        ans += cycle[i]
    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 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
        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:
# -*- 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
    j = Ap%M
    Anext = (j*j)%M
    sum = sum + Anext
    Ap = Anext

print(sum)

Submission status: Time Limit Exceeded

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

print(str(sum(ans)))

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
    temp = A[1]
    for i in range(2, mod + 1):
        A[i] = temp * temp % mod
        if A[i] in kouho:
            migi = i
            break
        kouho[A[i]] = i
        temp = A[i]
    saisho = 0
    hidari = kouho[A[i]]
    saisho = sum(A[1:hidari])
    # for i in range(1, hidari):
    #     saisho += A[i]
    cycle_val = sum(A[hidari:migi])
    # 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 = sum(A[hidari : hidari + amari])
    # 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())

ListA = [X]

for i in range (N-1):
  ListA.append( ListA[-1]**2 % M)
print (sum(ListA))

Submission status: Time Limit Exceeded

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

ans = x
before = x

for i in range(n-1):
    new = (before ** 2) % m
    ans += new
    before = new

print(ans)

Submission status: Time Limit Exceeded

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

def fact(n):
    freq = defaultdict(int)
    if n==0:
        return freq
    while n%2==0:
        freq[2]+=1
        n = n//2
    for i in range(3,int(n**0.5)+1):
        if n%i==0:
            freq[i]+=1
            n = n//i
    if n>1:
        freq[n]+=1
    return freq

can = True
freqx = fact(x)
freqm = fact(m)

for pf in freqm:
    if freqx[pf]!=0:
        can = False

if can or n<=m:
    s = x%m
    op = 1
    while op<n:
        rem = x%m
        rem = (rem*rem)%m
        if(rem==0):
            break
        s+=rem
        x = rem
        op+=1
    print(s)
else:
    x = x%m
    lo = [-1 for i in range(m)]
    series = [x]
    lo[x] = 0
    rep = -1
    for i in range(1,m+5):
        rem = (x*x)%m
        if lo[rem]>=0:
            rep = i-lo[rem]
            break
        else:
            series.append(rem)
            lo[rem] = i
        x = rem
    if rep>=0:
        st = len(series)-rep
        n-=st
        mul = n//rep
        ex = n%rep
        s = 0
        for i in range(st):
            s+=series[i]
        for i in range(st,len(series)):
            s+=(mul*series[i])
        for i in range(ex):
            s+=series[st+i]
    print(s)

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
    j = Ap%M
    Anext = (Ap*Ap)%M
    sum = sum + Anext
    Ap = Anext

print(sum)

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 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:
def main():
    N,X,M = map(int,input().split())
    A = X
    ans = A
    LIST = [A]
    C = 0
    flag = False
    for n in range(N-1):
        A = (A**2)%M
        if A in LIST:
            ind = LIST.index(A)
            C = sum(LIST[:ind])
            LIST = LIST[ind:]
            flag = True
            break
        else:
            LIST.append(A)
        ans += A
    else:
        print(ans)
        
    if flag:
        ANS = [0]
        S = 0
        for L in LIST:
            S += L
            ANS.append(S)
            
        a = (N - ind) // len(LIST)
        b = (N - ind) % len(LIST)
        ans = sum(LIST)*a + ANS[b] + C
        
        print(ans)
    
if __name__ == '__main__':
    main()