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())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(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) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

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.append(X)
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(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) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

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.append(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:
# -*- coding: utf-8 -*-

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

ans = x

i = 1
a_list = [x]
a = x
flag = 0
while(i<n):
    a = (a*a) % m
    if a in a_list:
        flag = 1
        break
    a_list.append(a)
    ans += a
    i+=1
    
if flag == 1:
    b = a_list.index(a)
    tmp_sum = 0
    for j in range(b,len(a_list)):
        tmp_sum += a_list[j]
    blen = len(a_list)-b
    ans += tmp_sum*((n-i)//blen)
    for k in range((n-i) % blen):
        ans += a_list[i+k-blen]

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
	x = (x*x)%m
	if x in l:
		break
	l.append(x)

if x == 0:
	print(sum(l))
else:
	p = l[0]
	k = 1
	Su = 0
	while p != x and k < len(l):
		Su += p
		p = l[k]
		k += 1
	l = l[k-1:]

	Su2 = 0
	for r in range((n-k)%len(l) + 1):
		Su2 += l[r]
	print(Su + ((n-k)//len(l))*sum(l) + Su2)

Submission status: Time Limit Exceeded

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

ans = X
A = X
TF = True
srt = 1000000
retu = [X]
loop = X
for i in range(N-1):
    if TF:
        A = A**2 % M
        for j in range(len(retu)):
            if A == retu[j]:
                srt = j
                goal = i
                TF = False
                break   
        if TF:
          retu.append(A)
          loop += A
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    saisyo = sum(retu[:srt])
    loop -= saisyo
    print(saisyo + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Time Limit Exceeded

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

ans = X
A = X
TF = True
srt = 1000000
retu = [X]
loop = X
for i in range(N-1):
    if TF:
        A = A**2 % M
        for j in range(len(retu)):
            if A == retu[j]:
                srt = j
                goal = i
                TF = False
                break   
        if TF:
          retu.append(A)
          loop += A
    else:
      break
      
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    loop -= sum(retu[:srt])
    print(sum(retu[:srt]) + loop*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

Submission status: Time Limit Exceeded

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

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力を取得
    N, X, M = list(map(int, input().split()))

    return N, X, M


def f(x: int, m: int) -> int:
    """
    xをmで割った余りを返す.

    Args:\n
        x (int): 整数
        m (int): 整数

    Returns:\n
        int: xをmで割った余り
    """
    return x % m


def main(N: int, X: int, M: int) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 整数(1 <= N <= 10^{10})
        X (int): 整数(0 <= X <= M <= 10^5)
        M (int): 整数(0 <= X <= M <= 10^5)
    """
    # 求解処理
    A = [X]
    i = 0
    while True:
        A_next = f(A[-1]**2, M)
        if A_next in set(A):
            i = A.index(A_next)
            break
        else:
            A.append(A_next)

    loop_length = len(A) - i
    loop_cnt = (N - i) // loop_length
    loop_res = (N - i) % loop_length
    ans = sum(A[:i]) + loop_cnt * sum(A[i:]) + sum(A[i: i + loop_res])

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, X, M = get_input()

    # メイン処理
    main(N, X, M)

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)
from numba import njit,i8


@njit(i8[:](i8,i8[:],i8[:],i8,i8,i8))
def SerchLoop(M,A,cnt,start,end,temp):
    for i in range(1,M*2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i
    return np.append(np.append(A,start),end)


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

    A = [-1 for i in range(M*2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    C = SerchLoop(M,A,cnt,start,end,0)
    A = C[:-2]
    start = C[-2]
    end = C[-1]

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        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 = X
A = X
TF = True
srt = 1000000
retu = [X]
for i in range(N-1):
    if TF:
        A = A**2 % M
        for j in range(len(retu)):
            if A == retu[j]:
                srt = j
                goal = i
                TF = False
                break   
        if TF:
          retu.append(A)
if N-1 > srt:
    n = (N-srt)//(goal-srt+1)
    print(sum(retu[:srt]) + sum(retu[srt:])*n + sum(retu[srt:N-n*(goal-srt+1)]))
    
else:
    print(sum(retu[:N]))

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)
from numba import njit


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


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

    A = [-1 for i in range(M*2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    A,start,end = SerchLoop(M,A,cnt,start,end,0)

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, X, M = list(map(int, input().split()))

# 求解処理


def f(x: int, m: int) -> int:
    return x**2 % m


A = [X]
loop_start_index = 0
while True:
    A_next = f(A[-1], M)
    if A_next in A:
        loop_start_index = A.index(A_next)
        break
    else:
        A.append(A_next)

loop_length = len(A) - loop_start_index
loop_cnt = (N - loop_start_index) // loop_length
loop_res = (N - loop_start_index) % loop_length
ans = sum(A[:loop_start_index]) + loop_cnt * sum(A[loop_start_index:]
                                                 ) + sum(A[loop_start_index: loop_start_index + loop_res])

# 結果出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = list(map(int, input().split()))
a = n[1]
l = [n[1]]
sum = 0
cout1 = 0
cout2 = 0
for i in range(n[2]):
  a=a**2 % n[2]
  l.append(a)
  for j in range(len(l)-1):
    if l[j]==a:
      cout1 = i+1
      cout2 = j
      break
  else:
    continue
  break
rangesum =0
for i in range(cout2,cout1):
  rangesum += l[i]
rangesum= rangesum*((n[0]-cout2)//(cout1-cout2))
for i in range(cout2,cout2+(n[0]-cout2)%(cout1-cout2)):
  sum += l[i]
for i in range(cout2):
  sum += l[i]
print(sum+rangesum)

Submission status: Time Limit Exceeded

Solution code:
N, X, M = map(int, input().split())
loop_start = 0
n = 0
A = [X]
for i in range(1, N):
    tmp = A[-1]**2 % M
    if tmp not in A:
        A.append(tmp)
    else:
        loop_start = A.index(tmp)
        n = i - A.index(tmp)
        break
if n == 0:
    print(sum(A))
else:
    start, loop = A[:loop_start], A[loop_start:]
    sum_start = sum(start)
    sum_loop = sum(loop)
    div, mod = divmod(N - loop_start, n)
    end = loop[:mod]
    sum_end = sum(end)
    ans = sum_start + sum_loop * div + sum_end
    print(ans)

Submission status: Time Limit Exceeded

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

dic = []
tmp = x % m
cnt = x #合計用
dic.append(tmp)

for i in range(n-1):
  tmp = tmp ** 2 % m
  if tmp in dic:
    index = dic.index(tmp)
    loop_cnt = i - index + 1
    loop_sum = sum(dic[index:i+1])
    cnt += (n - i - 1) // loop_cnt * loop_sum
    cnt += sum(dic[index:(index + (n - i - 1) % loop_cnt)])
    break
  cnt += tmp
  dic.append(tmp)
print(cnt)

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*2)]
    A[0] = X

    start = -1
    end = -1

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

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

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        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())
loop_start = 0
n = 0
A = [X]
for i in range(1, N):
    tmp = A[-1]**2 % M
    if tmp not in A:
        A.append(tmp)
    else:
        loop_start = A.index(tmp)
        n = i - A.index(tmp)
        break
if n == 0:
    print(sum(A))
else:
    div, mod = divmod(N - loop_start, n)
    loop = A[loop_start:loop_start + n]
    ans = sum(A[:loop_start]) + sum(loop) * div + sum(loop[:mod])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
#table=list(range(M))
#for i in range(M):
 #   table[i]=((table[i]%M)**2)%M
#print(table[471])
start=X%M
rireki=list()
rireki.append(start)
ss=0
for j in range(1,N):
    start=(start**2)%M
    if start in rireki:
        ss=rireki.index(start)
        break
    else:
        rireki.append(start)
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
table=list(range(M))
for i in range(M):
    table[i]=((table[i]%M)**2)%M
#print(table[471])
start=X%M
rireki=list()
rireki.append(start)
ss=0
for j in range(1,N):
    if table[start] in rireki:
        ss=rireki.index(table[start])
        break
    else:
        rireki.append(table[start])
        start=table[start]
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
a = x
mod = [a]
loop = []
cnt = 0
while cnt < n:
    a = a**2 % m
    if a in mod:
        i = mod.index(a)
        before = mod[:i]
        loop = mod[i:]
        break
    mod.append(a)
    cnt += 1

length = len(loop)
if length == 0:
    print(sum(mod[:n]))
else:
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
l = [x]
a = x
loopsum = 0
loopnum = 0


for i in range(n - 1):
    a = a**2%m
    if a not in l:
        l.append(a)
    else:
        pos = l.index(a)
        loopnum = len(l[pos:])
        loopsum = sum(l[pos:])
        break

if loopnum > 0:
    rest = (n - len(l))%loopnum
    times = (n - len(l))//loopnum
    ans = sum(l) + loopsum*times
    for i in range(rest):
        ans += l[pos + i]
else:
    ans = sum(l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x,m = map(int,input().split())
set_a = set()
a = []
while len(a)<n:
    if x in a:break
    set_a.add(x)
    a.append(x)
    x = x**2%m

ans = sum(a[:min(n,len(a))])
n -= len(a)
if n<1:
    print(ans)
    exit()

i = a.index(x)
l = len(a)-i
ans += sum(a[i:]) * (n//l)
n %= l
ans += sum(a[i:i+n])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
l = [x]
loop = []
a = x

for i in range(n - 1):
    a = a**2%m
    if a not in l:
        l.append(a)
    else:
        if a not in loop:
            loop.append(a)
        else:
            break

if len(loop) > 0:
    rest = (n - len(l))%len(loop)
    times = (n - len(l))//len(loop)
    ans = sum(l) + sum(loop)*times
    for i in range(rest):
        ans += loop[i]
else:
    ans = sum(l)

print(ans)

Submission status: Time Limit Exceeded

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

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, M):
        A = (A * A) % M if M > 0 else 0
        if A in l:
            i = l.index(A)
            break
        else:
            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:
""" 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 if M > 0 else 0
        if A in l:
            i = l.index(A)
            break
        else:
            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:
""" 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 if M > 0 else 0
        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())
A = [[0] * (10**5+1) for _ in range(34)]
B = [[0] * (10**5+1) for _ in range(34)]

for i in range(10**5+1):
    A[0][i] = B[0][i] = i**2 % M
for i in range(33):
    for j in range(10**5+1):
        A[i+1][j] = A[i][A[i][j]]
        B[i+1][j] += B[i][j] + B[i][A[i][j]]
now = X
ans = X
i = 0
N -= 1
while N > 0:
    if N & 1:
        ans += B[i][now] 
        now = A[i][now]
    N >>= 1
    i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n,x,m= map(int,input().split())
da =[x]

for i in range(1,n):
  da.append(da[i-1]**2%m)

print(sum(da))

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+1):
  a = a ** 2 % M
  if a in A:
    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())

l = []
ans = 0
for i in range(n):
    if x in l:
        d = l.index(x)
        ans += sum(l[:d])
        le = len(l)-d
        count = sum(l[d:])
        n -= d
        ans += count*(n//le)
        n %= le
        for k in range(d,d+n):
            ans += l[k]
        print(ans)
        exit()
    l.append(x)
    x = (x**2)%m

print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
count = 1
S = X
A = [X]

for i in range(2,N+1):
  A_i = (A[-1]*A[-1])%M
  A.append(A_i)
  S += A_i
  if len(A) != len(set(A)):
    S -= A_i
    del A[-1]
    B = A[A.index(A_i):]
    S += ((N-len(A))//len(B))*sum(B) + sum(B[:((N-len(A))%len(B))])
    break

print(S)

Submission status: Time Limit Exceeded

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))


count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if an in his:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    count = count + an
    pre_an = an

print(count)

Submission status: Time Limit Exceeded

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

tablef = []
for mi in range(m + 1):
    # tablef.append(table2jou[mi] % m)
    tablef.append(pow(mi, 2, m))


count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    an = tablef[pre_an]
    if an in his:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    count = count + an
    pre_an = an

print(count)

Submission status: Time Limit Exceeded

Solution code:
def seqSum(n, x, m):
    count = x
    prev = x
    for i in range(1, n):
        now = prev % m * prev % m
        prev = now % m
        count += prev 
    return count

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

Submission status: Time Limit Exceeded

Solution code:
N,X,M = map(int,input().split())
ls = [X]
for i in range(M):
    Ai = ls[-1]**2 % M
    if Ai in ls:
        loop = ls[ls.index(Ai):]
        lenloop = len(loop)
        sumloop = sum(loop)
        startls = ls[:ls.index(Ai)]
        break
    ls.append(Ai)
if N <= len(startls):
    ans = sum(startls[:N])
else:
    ans = sum(startls) + ((N-len(startls))//lenloop)*sumloop + sum(loop[:(N-len(startls))%lenloop])
print(ans)

Submission status: Time Limit Exceeded

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

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

if pattern_start_id == N:
    ans = sum(A)
else:
    before_pattern = A[:pattern_start_id]
    before_pattern_len = len(before_pattern)
    pattern = A[pattern_start_id:]
    pattern_len = len(pattern)
    ans = sum(before_pattern) + sum(pattern) * ((N - before_pattern_len) // pattern_len) + sum(pattern[:(N - before_pattern_len) % pattern_len])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
amr = []
for i in range(n):
    if i == 0:
        x %= m
        amr.append(x)
        continue
    x = pow(x, 2, m)

    if x in amr:
        break
    if x == 0:
        break
    amr.append(x)

if x == 0:
    print(sum(amr[:n]))
else:
    idx = amr.index(x)

    loop = sum(amr[idx:])
    l = len(amr[idx:])

    if n >= idx:
        cnt = (n-idx)//l
        print(cnt*loop + sum(amr[:idx]) + sum(amr[idx:idx+n-idx-cnt*l:]))
    else:
        print(sum(amr[:n]))

Submission status: Time Limit Exceeded

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

s=[x]
A=x
for i in range(m) :
    a=A**2%m
    if a in s :
        y=s.index(a)
        count=len(s)
        bount=count-y
        cnt=(n-count)//bount
        tnt=(n-count)%bount
        ans=sum(s)+sum(s[y:])*cnt+sum(s[y:y+tnt])
        print(ans)
        exit()
    else :
        s.append(a)
        A=a


print(sum(s))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

#標準出力からの読み込み
n, x, m = input().split(" ")
n = int(n)
x = int(x)
m = int(m)

A = [x]
p = 0

for i in range(n-1):
    try:
        p = A.index(A[-1]**2%m)
        break
    except:
        A.append(A[-1]**2%m)
    
#判定ロジック
result_1 = 0
result_2 = 0
result_3 = 0

try:
    t = len(A) - p
    u = ((n-len(A))//t)

    result_1 = sum(A)
    result_2 = u * sum(A[p:])
    result_3 = sum(A[p:n-u*t-len(A[p:])])
    print(result_1 + result_2 + result_3)
except:
    print(sum(A))

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+1):
  a = a ** 2 % M
  if A.count(a) >= 1:
    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 = [int(x) for x in input().split()]
A = [x]
while len(A) < n:
    a = (A[-1] * A[-1]) % m
    if a not in A:
        A.append(a)
    else:
        i = A.index(a)
        loop_len = len(A) - i
        print(sum(A[:i]) + sum(A[i:]) * ((n - i) // loop_len) + sum(A[i:i + ((n - i) % loop_len)]))
        break
else:
    print(sum(A))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

A = [X]
for i in range(1, N):
    X = (X ** 2) % M
    # print(X)
    if X in A:
        pattern_start_id = A.index(X)
        break
    else:
        A.append(X)
else:
    ans = sum(A)
    print(ans)
    sys.exit()

before_pattern = A[:pattern_start_id]
before_pattern_len = len(before_pattern)
pattern = A[pattern_start_id:]
pattern_len = len(pattern)

ans = sum(before_pattern) + sum(pattern) * ((N - before_pattern_len) // pattern_len) + sum(pattern[:(N - before_pattern_len) % pattern_len])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X, M = MAP()
ans = 0
flag = False
L = []
dic = dict()
for i in range(1, N+1):
    if X % M not in L:
        L.append(X % M)
    else:
        flag = True
        tmp = X % M
        l = len(L)
        break
    X = (X % M) ** 2
if flag == True:
    index = L.index(tmp)
    nR = L[:index]
    R = L[index:]
    amari = (N - len(nR)) % len(R)
    ans = sum(nR) + (N - len(nR)) // len(R) * sum(R) + sum(R[:amari])
    print(ans)    
else:
    ans = sum(L)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

#標準出力からの読み込み
n, x, m = input().split(" ")
n = int(n)
x = int(x)
m = int(m)

A = [x]
p = 0

for i in range(n-1):
    try:
        p = A.index(A[-1]**2%m)
        break
    except:
        A.append(A[-1]**2%m)
    
#判定ロジック
result_1 = 0
result_2 = 0
result_3 = 0

try:
    t = len(A) - p
    u = ((n-len(A))//t)

    result_1 = sum(A)
    result_2 = u * sum(A[p:])
    result_3 = sum(A[p:n-u*t-len(A[p:])])
except:
    pass

print(result_1 + result_2 + result_3)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

A = [X]
for i in range(1, N):
    X = (X ** 2) % M
    # print(X)
    if X in A:
        pattern_start_id = A.index(X)
        break
    else:
        A.append(X)
else:
    ans = sum(A)
    print(ans)
    sys.exit()

before_pattern = A[:pattern_start_id]
pattern = A[pattern_start_id:]

ans = sum(before_pattern) + sum(pattern) * ((N - len(before_pattern)) // len(pattern)) + sum(pattern[:(N - len(before_pattern)) % len(pattern)])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, x, m = map(int, input().split())
a = x
s = 0
h = []
h.append(a)
i = 0
fl = 0
while i < n:
    s += a
    a = (a*a) % m
    if a == 0:
      break
    i += 1
    if fl == 0 and a in h:
      fl = 1
      po = h.index(a)
      ss = 0
      for j in range(po):
        ss += h[j]
      s2 = s - ss
      f = (n - po) // (i - po)
      s2 *= f
      s = s2 + ss
      i2 = i - po
      i2 *= f
      i = i2 + po
    else:
      h.append(a)
print(s)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

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

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

d = [X]
for _ in range(1, N+1):
    X = f(X, M)
    if X in d:
        break
    d.append(X)

idx = d.index(X)
ans = sum(d[:idx])
N -= idx
d = d[idx:]

sumd = sum(d)
ans += N//len(d) * sumd

ans += sum(d[:N%len(d)])

print(ans)