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: Wrong Answer

Solution code:
n, x, m = map(int,input().split())
li = [0]*(m+1)

cnt1 = 0
cnt2 = 0
ans1 = x
ans2 = 0
a = x
flag = 0

for i in range(1,n):
    a = (a**2)%m
    li[a] += 1
    if li[a] == 2:
        cnt2 += 1
        ans2 += a
        flag = 1

    elif li[a] == 3:
        flag = 2
        break

    else:
        ans1 += a
        cnt1 += 1

# print(flag)
# # print(li)

if flag == 0:
    print(ans1)

elif flag ==1:
    print(ans1+ans2)

else:
    print(ans1+ans2*(n-cnt1)//cnt2+((n-cnt1)%cnt2))

Submission status: Wrong Answer

Solution code:
N,X,M=map(int,input().split())
A = [X,]
setA = {X,}
alast=X
flag=False
for i in range(min(N-1,M)):
    P=alast**2%M
    if P in setA:
        flag=True
        d = A.index(P)
        C=A[d:]
        alast=P
        break
    else:
        A.append(P)
        setA.add(P)
        alast=P
if alast==0:
    print(sum(C))
elif (flag==False) and (alast!=0):
    print(sum(A))
else:
    suma=sum(C)
    res = (N-d)%len(C)
    print(sum(A[:d])+((N-d)//len(C))*suma + sum(C[:res]))

Submission status: Wrong Answer

Solution code:
def solve(N, X, M):
    x = X
    table = [-1] * M
    a = []
    length = 0
    # ループするまで配列に値を入れていく
    while table[x] == -1:
        a.append(x)
        table[x] = length
        length += 1
        x = x**2 % M

    # ループの開始位置とループの合計値を求める
    start = table[x]
    loop_total = 0
    for i in range(table[x], length):
        loop_total += a[i]

    # 答えの計算
    ans = 0
    if N <= length:
        for i in range(N):
            ans += a[i]
    else:
        # フルで何周するかを計算
        count = N - start
        count //= (length-start)
        ans += count * loop_total
        count = N % (length-start)
        for i in range(count):
            ans += a[i]

    return ans


if __name__ == "__main__":
    N, X, M = map(int, input().split())
    print(solve(N, X, M))

Submission status: Wrong Answer

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]
    s = {X}
    i = 0
    while True:
        A_next = f(A[-1], M)
        if A_next in s:
            i = A.index(A_next)
            break
        else:
            A.append(A_next)
            s.add(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: Wrong Answer

Solution code:
def cycle_getter(N, start):
    """
    :param N: 移動回数
    :param start:　初期条件
    :return front: cycleまでの要素のリスト
            cycle: cycle内の要素のリスト
            end: cycle後の余った部分の要素のリスト
            cnt: cycle回数
    """
    p = start
    front, cycle, end = [p], [], []
    cnt = 0
    visit = {p:0}
    L, R = N-1, -1
    for i in range(1,N):
        p = lift(p)
        if p in visit:
            """
            (L, R) = (サイクルに到達する直前のindex, サイクルの終端のindex)
            [6,2,3,4,0,1,2] ⇒ (L, R) = (0, 5)
            """
            L, R = visit[p]-1, i-1
            period = R-L
            break
        visit[p] = i
    p = start
    for i in range(L):
        p = lift(p)
        front.append(p)
    if L != N-1:
        for i in range(L,R):
            p = lift(p)
            cycle.append(p)
        for i in range(N-(N-(L+1))%period,N):
            p = lift(p)
            end.append(p)
        cnt = (N-(L+1))//period
    return front, cycle, end, cnt

def lift(x): return pow(x,2,M)

################################################################################
import sys
input = sys.stdin.readline

N, X, M = map(int, input().split())
front, cycle, end, cnt = cycle_getter(N,X)
print(sum(front)+sum(cycle)*cnt+sum(end))

Submission status: Wrong Answer

Solution code:
N,X,M=[int(s) for s in input().split()]
modls=[0 for _ in range(M+1)]
modls[0]=X
for i in range(1,M+1):
  k=(modls[i-1]**2)%M
  if k in modls:
    break
  modls[i]=k
loop_end=i
loop_start=modls.index(k)
loop_length=loop_end-loop_start
#print(loop_start,loop_length)

ans=0
ans+=sum(modls[:loop_start])
if k!=0:
  ans+=sum(modls[loop_start:])*(N-loop_start)//loop_length
  ans+=sum(modls[loop_start:loop_start  +  (N-loop_start)%loop_length])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 22:58:03 2020

@author: liang
"""

N,X,M=map(int,input().split())
a = X
hist = [a]
indices = [-1]*M
indices[a] = 0
flag=0
for i in range(1,min(10**6,N)):
  a = a**2 % M
  if indices[a] != -1:
    idx = indices[a]
    flag=1
    break
  hist.append(a)
  indices[a] = i
  
if flag==0:
  print(sum(hist))
  exit()
  
cycle = hist[idx:]
margin = hist[:idx]
q,r = divmod((N-len(margin)),len(cycle))
ans = 0
#ans += sum(margin)
#ans += sum(cycle)*q
#print(q,sum(cycle))
ans += sum(cycle[:r])
#print(r)
#print(cycle[:10])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 19 22:58:03 2020

@author: liang
"""

N,X,M=map(int,input().split())
a = X
hist = [a]
indices = [-1]*M
indices[a] = 0
flag=0
for i in range(1,min(10**6,N)):
  a = a**2 % M
  if indices[a] != -1:
    idx = indices[a]
    flag=1
    break
  hist.append(a)
  indices[a] = i
  
if flag==0:
  print(sum(hist))
  exit()
  
cycle = hist[idx:]
margin = hist[:idx]
q,r = divmod((N-len(margin)),len(cycle))
ans = 0
#ans += sum(margin)
#ans += sum(cycle)*q
#print(q,sum(cycle))
ans += sum(cycle[:r])
print(r)
print(cycle[:10])
print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = 0
  val_list = []

  base = M
  for i in range(N):
    if checked[val] != False:
      loop_start_index = checked[val]
      loop_vals = val_list[loop_start_index:]
      loop_val = sum(loop_vals)
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i) // loop_length) * loop_val

        for i in range(((N - i) % loop_length)):
          ans += loop_vals[i]
      break
    ans += val
    checked[val] = i
    val_list.append(val)

    val*=val
    if val >= base:
      val %= base


  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N, X, M = map(int, input().split())
A = [X]
visited = set()
visited.add(X)

idx = defaultdict()
idx[X] = 0

iii = -1

for i in range(1, M):
    tmp = (A[-1]**2) % M
    if tmp not in visited:
        A.append(tmp)
        visited.add(tmp)
        idx[tmp] = i
    else:
        iii = idx[tmp]

ans = 0

if iii == -1:
    ans = sum(A[:N])
    exit()
else:
    # ループの頭の直前まで
    ans += sum(A[:iii])
    N -= iii
    if N > 0:
        # ループの長さ
        l = len(A) - iii
        ans += (N // l) * sum(A[iii:])
        N -= N // l * l
    if N > 0:
        # ループに満たないN
        ans += sum(A[iii:iii + N])

    print(ans)

Submission status: Wrong Answer

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

cnt = 0
ruiseki = [x]
a = x
al = {}
al[x] = 0
loop_s = 0
loop_e = 0

for i in range(n - 1):
    na = (a ** 2) % m
    if na in al.keys():
        loop_s = al[na]
        loop_e = al[a]
        break
    else:
        al[na] = i + 1
        ruiseki.append(ruiseki[cnt] + na)
        cnt += 1
        a = na

if loop_e != 0:
    ans = ruiseki[max(0, loop_s - 1)]
    ans += (ruiseki[loop_e] - ruiseki[max(0, loop_s - 1)]) * ((n - loop_s + 1) // (loop_e - loop_s + 1))
    p = max(0, n - ((n - loop_s + 1) // (loop_e - loop_s + 1) * (loop_e - loop_s + 1)) - (loop_s - 1) - 1)
    ans += ruiseki[p + loop_s - 1] - ruiseki[max(0, loop_s - 1)]
else:
    ans = ruiseki[-1]

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(1, N):
    val*=val
    if val >= base:
      val %= base

    if checked[val] != False:
      loop_start_index = checked[val]
      loop_vals = val_list[loop_start_index:]
      loop_val = sum(loop_vals)
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i) // loop_length) * loop_val

        for i in range(((N - i) % loop_length)):
          ans += loop_vals[i]
      break
    ans += val
    checked[val] = i
    val_list.append(val)

  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(N):
    val*=val
    if val >= base:
      val %= base

    if checked[val] != False:
      loop_start_index = checked[val]
      loop_vals = val_list[loop_start_index:]
      loop_val = sum(loop_vals)
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i - 1) // loop_length) * loop_val

        for i in range(((N - i - 1) % loop_length)):
          ans += loop_vals[i]
      break
    ans += val
    checked[val] = i + 1
    val_list.append(val)

  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
n, x, m = map(int, input().split())
ans = 0
prev_set = set()
prev_list = list()
ans_hist = list()
r = x

for i in range(n):
    if i == 0:
        pass
    else:
        r = (r * r) % m
    
    if r == 0:
        break
    
    if r in prev_set:
        index = prev_list.index(r)
        period = i - index
        count = (n - index) // period
        rest = (n - index) % period

        # ans = sum(prev_list[:index])
        # ans += sum(prev_list[index:i]) * count
        if index == 0:
            ans *= (count - 1)
        else:
            ans += (ans - ans_hist[index - 1]) * (count - 1)

        ans += sum(prev_list[index:index+rest])
        # ans += (ans_hist[index + rest - 1] - ans_hist[index - 1])
        break
    else:
        ans += r
        prev_set.add(r)
        prev_list.append(r)
        ans_hist.append(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ans = 0

aa = x
ans += aa
aset = set([aa])
alist = [aa]

for i in range(1,n):
    aa = pow(aa,2,m)
    if aa in aset:
        ind = alist.index(aa)
        loop = alist[ind:i]
        nloop = (n-ind+1)//len(loop)
        ans += sum(loop)*(nloop-1)
        ans += sum(loop[0:(n-ind+1)%len(loop)-1])
        break
    else:
        ans += aa
        aset.add(aa)
        alist.append(aa)

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(N-1):
    val*=val
    if val >= base:
      val %= base

    if checked[val] != False:
      loop_start_index = checked[val]
      loop_vals = val_list[loop_start_index:]
      loop_val = sum(loop_vals)
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i - 1) // loop_length) * loop_val

        for i in range(((N - i - 1) % loop_length)):
          ans += loop_vals[i]
      break
    ans += val
    checked[val] = i + 1
    val_list.append(val)

  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ans = 0

aa = x
ans += aa
aset = set([aa])
alist = [aa]

for i in range(1,n):
    aa = pow(aa,2,m)
    if aa in aset:
        ind = alist.index(aa)
        loop = alist[ind:i]
        nloop = (n-ind+1)//len(loop)
        ans += sum(loop)*(nloop-1)
        ans += sum(loop[0:(n-ind+1)%len(loop)-1])
        break
    else:
        ans += aa
        aset.add(aa)
        alist.append(aa)

    if aa == 0:
        break

print(ans)

Submission status: Wrong Answer

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

for i in range(1,m+1):   
    if n <= i:
        break
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != 0:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

Submission status: Wrong Answer

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

for i in range(1,m+1):   
    if n <= i:
        break
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != 0:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(N-1):
    val*=val
    if val >= base:
      val %= base

    if checked[val] != False:
      loop_start_index = checked[val]
      loop_vals = val_list[loop_start_index:]
      loop_val = sum(loop_vals)
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i - 1) // loop_length) * loop_val

        for i in range(((N - i - 1) % loop_length)):
          ans += loop_vals[i]
      break
    ans += val
    checked[val] = i + 1
    val_list.append(val)

  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

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

for i in range(1,m+1):   
    if n <= i:
        break
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != 0:
    l2 = l[lp:]
    tmp = sum(l2)
    b=(n-len(l))//len(l2)
    c=n-len(l)-b*len(l2)
    ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

Submission status: Wrong Answer

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

cnt = 0
ruiseki = [x]
a = x
al = {}
al[x] = 0
loop_s = 0
loop_e = 0

for i in range(n - 1):
    na = (a ** 2) % m
    if na in al.keys():
        loop_s = al[na]
        loop_e = al[a]
        break
    else:
        al[na] = i + 1
        ruiseki.append(ruiseki[cnt] + na)
        cnt += 1
        a = na

if loop_e != 0:
    ans = ruiseki[loop_s - 1]
    ans += (ruiseki[loop_e] - ruiseki[loop_s - 1]) * ((n - loop_s + 1) // (loop_e - loop_s + 1))
    p = max(0, n - ((n - loop_s + 1) // (loop_e - loop_s + 1) * (loop_e - loop_s + 1)) - (loop_s - 1) - 1)
    ans += ruiseki[p + loop_s - 1] - ruiseki[loop_s - 1]
else:
    ans = ruiseki[-1]

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(N-1):
    val*=val
    if val >= base:
      val %= base

    if checked[val] != False:
      loop_start_index = checked[val]+1

      loop_val = sum(val_list[loop_start_index:])
      loop_length = len(val_list[loop_start_index:])
      
      if loop_length != 0:
        ans += ((N - i - 1) // loop_length) * loop_val
        segment = val_list[loop_start_index:loop_start_index + ((N - i - 1) % loop_length) ]
        ans += sum(segment)
      break
    ans += val
    checked[val] = i
    val_list.append(val)


  print(ans)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
n,x,m = map(int,input().split())
suma = []
repid = 0
for i in range(n):
    tmp = pow(x,2**i,m)
    if tmp in suma:
        repid = suma.index(tmp)
        break
    suma.append(tmp)
    
if n <= len(suma):
    print(sum(suma))
else:
    replen = len(suma)-repid # 繰り返し長さ
    repa = suma[-replen:] # 繰り返し配列
    presum = sum(suma[:repid+1]) # 繰り返し前sum
    repn = (n-repid)//replen # 繰り返し回数
    repsum = repn*sum(suma[repid:])
    endsum = sum(repa[:(n-repid)%repn]) # 繰り返し終了後の残りsum
    print(presum+repsum+endsum)

Submission status: Wrong Answer

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:
    print(loop)
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)

Submission status: Wrong Answer

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:
    print(loop)
    t = (n-i)//length
    amari = (n-i) % length
    print("t, amari:",t,",",amari)
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

n, x, m = map(int, input().split())
ans = x % m
loop_lis = []
loop_num = 0
before_cnt = 1
remain = -100
while pow(x, 2) < m:
    if before_cnt == n:
        print(ans)
        exit()
    tmp = pow(x, 2)
    before_cnt += 1
    tmp %= m
    ans += tmp
    x = tmp
    # print(ans,tmp)

before_cnt += 1
loop_lis = [pow(x, 2) % m]
x = pow(x, 2) % m

for i in range(m):
    if before_cnt + i == n:
        ans += loop_lis[-1]
        break
    tmp = pow(x, 2) % int(m)
    if loop_lis[0] == tmp:
        remain = (n - before_cnt) % len(loop_lis)
        loop_num = math.floor((n - before_cnt) / len(loop_lis))
        if remain == 0:
            ans += loop_num * loop_lis[-1]
        else:
            ans += loop_num * loop_lis[-1] + loop_lis[remain]
        break
    loop_lis.append(tmp + loop_lis[-1])
    x = tmp
print(ans)
# print(ans,remain,loop_lis,loop_num)

Submission status: Wrong Answer

Solution code:
import math
n,x,m=map(int, input().split())
a = x
ans = a
lp=0
l=[a]
flg=[0]*m

for i in range(1,m+1):   
    if n <= i:
        break
    tmp=(a*a)%m
    a=tmp
    if flg[a]==1:
        lp = l.index(a)
        break
    else:    
        ans+=tmp
        l.append(a)
        flg[a]=1

if lp != 0:
    l2 = l[lp:]
    tmp = sum(l2)
    b=math.floor((n-len(l))/len(l2))
    c=n-len(l)-b*len(l2)
    if c==0:
        ans=ans+b*tmp
    else:
        ans=ans+(b*tmp)+sum(l2[:c])

print(ans)

Submission status: Wrong Answer

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

cnt = 0
flag = True
ruiseki = [x]
a = x
al = {}
al[x] = 0
loop_s = 0
loop_e = 0

for i in range(n - 1):
    na = (a ** 2) % m
    if na in al.keys():
        loop_s = al[na]
        loop_e = al[a]
        break
    else:
        al[na] = i + 1
        ruiseki.append(ruiseki[cnt] + na)
        cnt += 1
        a = na

if loop_e != 0:
    ans = ruiseki[loop_s - 1]
    ans += (ruiseki[loop_e] - ruiseki[loop_s - 1]) * ((n - loop_s + 1) // (loop_e - loop_s + 1))
    p = n - ((n - loop_s + 1) // (loop_e - loop_s + 1) * (loop_e - loop_s + 1)) - (loop_s - 1)
    if p > 0:
        ans += ruiseki[p] - ruiseki[loop_s - 1]
else:
    ans = ruiseki[-1]

print(ans)

Submission status: Wrong Answer

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))
else:
    t = (n-i)//length
    amari = (n-i) % length
    ans = sum(before) + t * sum(loop) + sum(loop[:amari])
    print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, X, M = map(int, input().split(" "))
  checked = [False] * M
  val = X
  ans = val
  val_list = [val]
  checked[val] = val

  base = M
  for i in range(N-1):
    val*=val
    if val >= base:
      val %= base
    # print(val)

    if checked[val] != False:
      loop_start_index = checked[val]+1

      loop_val = sum(val_list[loop_start_index:])
      loop_length = i - checked[val]

      ans += ((N - i - 1) // loop_length) * loop_val
      segment = val_list[loop_start_index:loop_start_index + ((N - i - 1) % loop_length) ]
      ans += sum(segment)
      break
    ans += val
    checked[val] = i
    val_list.append(val)

  print(ans)

if __name__ == "__main__":
  resolve()