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: Accepted

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: Accepted

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

id_ = [-1] * M
a = []
len_ = 0
ans = 0
x = X
while id_[x] == -1:
    id_[x] = len_
    len_ += 1
    ans += x
    a.append(x)
    x = x**2 % M

c = len_ - id_[x]
s = 0
for i in range(id_[x], len_):
    s += a[i]

if len_ >= N:
    ans = 0
    for i in range(N):
        ans += a[i]
else:
    n = N
    n -= len_
    ans += s * (n // c)
    n %= c
    for i in range(n):
        ans += a[id_[x]+i]
print(ans)

Submission status: Accepted

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]**2, 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: Accepted

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

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: Accepted

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

Submission status: Accepted

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

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False
#for i in range(1,N):
"""
【for文のループ用の変数を、
　●for文外で使ったり
 ●for文内で書き換えたり
 してはいけない】
 (理由)
●for文外で使うとき、for文に入らない入力値の場合
　　【未定義】
　となり、エラーが出る。　
 ⇒　【for文外で定義済み】の他の変数に保存する
●for文内で書き換えると、ループが壊れてしまう
 ⇒　一旦別の変数に保存し、その変数を書き換える

【整数の切り捨て演算は計算順序に注意】
*ans += T_sum * (N-j)//T
　⇒T_sum * (N-j)　を Tで割っているのでダメ
<対策 1: 切り捨て演算は括弧で囲む>
 ⇒ans += T_sum * ( (N-j)//T )
<対策 2: 切り捨て演算は予め計算しておく>
 ●divmod(a,b) => return (a//b,a%b)

"""
l = 1
for i in range(1,min(10**6,N)):
    l = i
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = l
T = l - j
ans = 0
if T != 0:  
    #print("A")
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    q, r = divmod(N-j,T)
    ans += T_sum * q
    #print((N-j)//T, T_sum)
    T_lis = mod_lis[j:]   
    ans += sum(T_lis[:r])
else:
    #print("B")
    ans = sum(mod_lis)
   # print(mod_lis)
#print(T_lis)
#print((N-j)%T)
#print(T_lis[:10])
print(ans)
#print(T_sum)
#print(sum(T_lis))

Submission status: Accepted

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

dp = [None]*mod

a = x
arr = [a]

for i in range(n-1):
  if dp[a] is not None:
    idx = arr.index(a)
    sum_early = sum(arr[:idx])
    cycle = i - idx
    sum_repeat = sum(arr[idx:-1])
    repeat_num = (n - idx) // cycle
    end_num = (n - idx) % cycle
    sum_end = sum(arr[idx:idx+end_num])
    ans = sum_early + sum_repeat*repeat_num + sum_end
    print(ans)
    exit()
  tmp = pow(a, 2, mod)
  dp[a] = tmp
  a = tmp
  arr.append(a)

print(sum(arr))

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    n,x,m = map(int,ipt().split())
    rps = [x]
    ln = [-1]*m
    ln[x] = 0
    nn = x
    rs = 0
    rg = n
    for i in range(1,n):
        nn = (nn**2)%m
        if ln[nn] == -1:
            ln[nn] = i
            rps.append(nn)
        else:
            rs = ln[nn]
            rg = i
            break
    ans = sum(rps[:rs:])
    smsg = sum(rps[rs:rg:])
    rpl = rg-rs
    ans += (n-rs)//rpl*smsg
    ans += sum(rps[rs:rs+(n-rs)%rpl:])

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = {X : 1}

path = [X]

cnt = 1
ans = X
a = X
for i in range(2, N + 1):
    a = a * a % M
    if a in S:
        cnt = i - S[a]
        break
    S[a] = i

    ans += a
    path.append(a)

pre_len = S[a] - 1

Q, R = divmod(N - pre_len - 1, len(path) - pre_len)

pre = sum(path[:pre_len])
cycle = sum(path) - pre

ans = a
for _ in range(R):
    a = a * a % M
    ans += a

print(pre + Q * cycle + ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, X, M = NMI()
    A = []
    A_ID = {}
    break_flag = False
    start = 0
    end = N
    for i in range(M):
        if i == 0:
            A.append(X)
            A_ID[X] = 0
        else:
            x = A[-1]**2 % M
            if x not in A_ID:
                A.append(x)
                A_ID[x] = i
            else:
                A.append(x)
                start = A_ID[x]
                end = i
                break_flag = True
            if break_flag:
                break

    if N < start+1:
        print(sum(A[:N]))
        exit()

    ans = sum(A[:start])
    lp = sum(A[start:end])
    gap = end - start
    lp_n = (N - start) // gap
    rem = (N - start) % gap
    ans += lp * lp_n + sum(A[start: start + rem])
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, x, m = I()

seen = [x]
ans = x
for i in range(1, n):
    now = seen[-1]
    next = (now * now) % m

    if next not in seen:
        seen.append(next)
        ans += next
    else:
        loop = seen[seen.index(next):]
        count = len(loop)
        total = sum(loop)
        remain = n - i
        
        q, r = remain // count, remain % count
        ans += q * total
        ans += sum(loop[:r])
        break
        
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
lis = set()
loop_lis = []
cnt = 0
while x not in lis:
    cnt += 1
    lis.add(x)
    loop_lis.append(x)
    x = pow(x, 2) % m
    if cnt == n:
        print(sum(lis))
        exit()

start = loop_lis.index(x)
length = len(loop_lis) - start
loop_sum = sum(loop_lis[start:])
before = sum(loop_lis[:start])
loop = loop_sum * ((n - start) // length)
remain = sum(loop_lis[start : (start + (n - start) % length)])

print(before + loop + remain)

Submission status: Accepted

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

@author: liang
"""

N, X, M = map(int,input().split())
mod_set = {X}
mod_lis = [X]
A = [0]*(10**6+1)
A[0] = X
flag = False
#for i in range(1,N):
i = 1
for i in range(1,min(10**6,N)):
    tmp = A[i-1]**2%M
    if tmp in mod_set:
        flag = True
        break
    A[i] = tmp
    mod_set.add(tmp)
    mod_lis.append(tmp)

if flag:
    j = mod_lis.index(tmp)
else:
    j = i
T = i - j
ans = 0
if T != 0:  
    #print("A")
    ans += sum(mod_lis[:j])
    T_sum = sum(mod_lis[j:])
    """
    【切り捨て演算は必ず()をつけて先に計算】
    """
    ans += T_sum * ((N-j)//T)
    #print((N-j)//T, T_sum)
    T_lis = mod_lis[j:i]   
    ans += sum(T_lis[:(N-j)%T])
else:
    #print("B")
    ans = sum(mod_lis)
   # print(mod_lis)
#print(T_lis)
#print((N-j)%T)
#print(T_lis[:10])
print(ans)
#print(T_sum)
#print(sum(T_lis))

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
N -= 1
L = 1
while 1 << L <= N:
    L += 1
table = [[None] * M for _ in range(L)]
for i in range(M):
    x = i * i % M
    table[0][i] = (x, x)
for i in range(1, L):
    for j in range(M):
        k, s = table[i-1][j]
        l, t = table[i-1][k]
        table[i][j] = (l, s + t)
ans = X
for i in range(L)[::-1]:
    if (1 << i) <= N:
        j, s = table[i][X]
        ans += s
        N -= (1 << i)
        X = j
print(ans)

Submission status: Accepted

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: Accepted

Solution code:
N,X,M = map(int,input().split())
#全体ループを見る配列
t_loop = [X]
#初回ループを見る配列
f_loop = [X]
#出現回数を見る辞書
memo = {X:1}
#2回目以降のループを見る配列
s_loop = []
while True:
    new_val = t_loop[-1]**2%M
    t_loop.append(new_val)
    if new_val not in memo:
        memo[new_val] = 1
        f_loop.append(new_val)
    else:
        memo[new_val] += 1
        if memo[new_val] == 3:
            break
        else:
            s_loop.append(new_val)

ans = 0
if N <= len(f_loop):
    ans += sum(f_loop[:N])
else:
    ans += sum(f_loop)
    shou = (N-len(f_loop))//len(s_loop)
    amari = (N-len(f_loop))%len(s_loop)
    ans += shou*sum(s_loop)
    ans += sum(s_loop[:amari])
    
print(ans)

Submission status: Accepted

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])
    print(ans)
    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: Accepted

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)

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
t_loop = [X]
f_loop = [X]
f_memo = {X:1}
s_loop = []
while True:
    new_val = t_loop[-1]**2%M
    t_loop.append(new_val)
    if new_val not in f_memo:
        f_memo[new_val] = 1
        f_loop.append(new_val)
    else:
        f_memo[new_val] += 1
        if f_memo[new_val] == 3:
            break
        else:
            s_loop.append(new_val)

ans = 0
if N <= len(f_loop):
    ans += sum(f_loop[:N])
else:
    ans += sum(f_loop)
    shou = (N-len(f_loop))//len(s_loop)
    amari = (N-len(f_loop))%len(s_loop)
    ans += shou*sum(s_loop)
    ans += sum(s_loop[:amari])
    
print(ans)

Submission status: Accepted

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:
        offset = alist.index(aa)
        loop = alist[offset:i]
        nloop, tail = divmod(n-offset, len(loop))
        ans += sum(loop)*(nloop-1)
        ans += sum(loop[0:tail])
        break
    else:
        ans += aa
        aset.add(aa)
        alist.append(aa)

print(ans)

Submission status: Accepted

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

tmp = []

while True:
    tmp.append(x)
    x = pow(x, 2, m)
    if x in tmp:
        break

k = 0
while True:
    if tmp[k] == x:
        break
    k += 1

if k > n:
    print(sum(tmp[:n]))
else:
    t = k
    a = (n - k) // (len(tmp) - k)
    s = (n - k) % (len(tmp) - k)
    print(sum(tmp[:k]) + sum(tmp[k:]) * a + sum(tmp[k: k + s]))

Submission status: Accepted

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 += 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: Accepted

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
rset=set()
rireki=list()
rset.add(start)
rireki.append(start)
ss=0
for j in range(1,M+1):
    start=(start**2)%M
    if start in rset:
        ss=rireki.index(start)
        break
    else:
        rireki.append(start)
        rset.add(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: Accepted

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

lis = [x]
flag = [-1 for i in range(m)]
flag[x] = 0
left = -1
right = -1
for i in range(n-1):
    x = x**2 % m
    if flag[x] >= 0:
        left = flag[x]
        right = i
        break
    else:
        lis.append(x)
        flag[x] = i+1

ans = 0
if left == -1:
    ans = sum(lis)
else:
    ans += sum(lis[0:left])
    length = right - left + 1
    ans += sum(lis[left:]) * ((n-left)//length)
    ans += sum(lis[left:left+((n-left)%length)])
print(ans)

Submission status: Accepted

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

for i in range(1,n):
    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 != -1:
    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: Accepted

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
# ループの頭の直前まで
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)
exit()

Submission status: Accepted

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

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 != -1:
    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: Accepted

Solution code:
N, X, M = map(int, input().split())
tmp = X
seq = []
ans = 0
for i in range(N):
  if X in seq:
    break
  seq.append(X)
  X = (X ** 2) % M

ans = sum(seq[:min(N, len(seq))])
N -= len(seq)
if N < 1:
    print(ans)
    exit()
i = seq.index(X)
l = len(seq) - i
ans += sum(seq[i:]) * (N//l)
N %= l
ans += sum(seq[i:i+N])
print(ans)

Submission status: Accepted

Solution code:

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

s = [0, x]
d = {x: 1}
su = x
ans = x
for i in range(2, n+1):
    x = (x * x) % m
    su += x
    if x in d:
        a = su - s[d[x]]
        ans = s[d[x]] - x
        le = i - d[x]
        rep = (n - d[x] + 1) // le
        ans += a * rep
        amari = (n - d[x] + 1) % le
        for j in range(amari):
            ans += x
            x = (x * x) % m
        break
    else:
        s.append(su)
        d[x] = i
        ans = su
print(ans)