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:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n,x,m = MI()
li = [x]
ans = 0
b = 0
for i in range(1,n):
    k =  pow(x,2,m)
    if k in li:
        b = 1
        ind = li.index(k)
        break
    li.append(k)
    x = k
    ##周期はlen(li)-ind
if b == 0:
    ans = sum(li)
else:
  ##print(li)
  ##print(ind)
  T = len(li) - ind
  ans += sum(li[:ind])##n個のうちind+1個足したからあとn-(ind+1)個足す
  ##print(ans)
  n = n-ind
  q = n//T
  S = sum(li[ind:])
  r = n%T
  ans += q*S + sum(li[ind:ind+r])
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
from collections import defaultdict
check = defaultdict(int)
L = [0,X]
L_ans = [0,X]
roop_end = 0

ans = X

old_a = X
for i in range(2,N+1):
  a = (old_a**2)%M
  ans += a
  old_a = a
  L.append(a)
  L_ans.append(ans)
  
  if check[a] != 0:
    roop_first = check[a]
    roop_end = i
    roop_iter = roop_end - roop_first
    ans = L_ans[roop_first - 1]
    roop_first_ans = L_ans[roop_first]
    roop_end_ans = L_ans[roop_end]
    roop_plus = roop_end_ans - roop_first_ans
    break
  else:
    check[a] = i
if roop_end == 0:
  print(ans)
else:
  roop_phase = N - roop_first + 1
  roop_num = roop_phase // roop_iter
  ans += roop_plus * roop_num
  roop_addition = roop_phase % roop_iter
  addition = L_ans[roop_first - 1 + roop_addition] - L_ans[roop_first - 1]
  ans += addition
  print(ans)

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,X,M = MI()


if M == 1:
    print(0)
    exit()

flag = [-1]*M
Z = [X]
flag[X] = 1
r = X
for i in range(2,M+2):
    r = r ** 2
    r %= M
    if flag[r] != -1:
        a,b = flag[r],i
        break
    else:
        flag[r] = i
        Z.append(r)

B = [0]*(len(Z))
for i in range(a-1):
    B[i] = 1
n = N-a+1
q = n//(b-a)
r = n % (b-a)

for i in range(a-1,a+r-1):
    B[i] = q+1
for i in range(a+r-1,b-1):
    B[i] = q

ans = 0
for i in range(len(Z)):
    ans += B[i]*Z[i]


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, A, M = map(int, input().split())

    ans = 0
    loop = set([A])
    lst = [A]
    for _ in range(N):
        ans += A
        A = pow(A, 2, M)
        if A in loop:
            loop_start = lst.index(A)
            loop_sum = sum(lst[loop_start:])
            loop_length = len(lst[loop_start:])
            a = sum(lst[:loop_start])
            b = loop_sum * ((N - loop_start) // loop_length)
            c = sum(lst[loop_start:loop_start + ((N - loop_start) % loop_length)])
            ans = a + b + c
            break
        else:
            loop.add(A)
            lst.append(A)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0

dic = {}

roopCounter = 0
tmp = X
dic[tmp]=0
consump=0

while True:
    ans += tmp
    tmp = pow(tmp,2,M)
    roopCounter += 1
    if tmp in dic:
        consump = roopCounter
        roopCounter = roopCounter-dic[tmp]
        rooper = tmp
        break
    else:
        dic[tmp]=roopCounter

new_dic = {}
tmp = rooper
new_dic[tmp]=0
while True:
    tmp = pow(tmp,2,M)
    if tmp in new_dic:
        break
    else:
        new_dic[tmp]=0
once = 0
for i in new_dic:
    once+=i

ans += once*((N-consump)//roopCounter)

tmp = rooper
for i in range(0,(N-consump)%roopCounter):
    ans += tmp
    tmp = pow(tmp,2,M)

print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
# mod = 10 ** 9 + 7
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]



def main():
    N, X, M = read_values()
    F = [-1] * (M + 1)

    A = X
    t = 0
    while F[A] < 0:
        F[A] = t
        A = pow(A, 2, M)
        t += 1
    
    if t == 1:
        print(X * N)
        return
    d = (N - F[A]) // (t - F[A])
    r = ((N - F[A]) % (t - F[A])) + F[A]

    K = 0
    for _ in range(F[A], t):
        K += A
        A = pow(A, 2, M)
    
    K *= d

    A = X
    for _ in range(r):
        K += A
        A = pow(A, 2, M)

    print(K)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a = [x]
while True:
  res = (a[-1]**2) % m
  if len(a) == n:
    print(sum(a))
    sys.exit()
  elif res == 0:
    print(sum(a))
    sys.exit()
  elif res in a:
    ai = a.index(res)
    aa = a[ai:]
    break
  else:
    a.append(res)

if len(a) >= n:
  print(sum(a[:n]) )
  sys.exit()

shuuki = len(aa)
shuuki_sum = sum(aa)

ans = sum(a) + shuuki_sum * ( (n-len(a)) // shuuki ) + sum( aa[:(n-len(a)) % shuuki] )
print(ans)

Submission status: Accepted

Solution code:
n,x,mod=map(int,input().split())
#32 回やればコーナーは回避できる
now=x
xs=0
for i in range(min(n,32)):
    if now%mod==0:print(xs);exit()
    else:
        xs+=now
        now=now*now%mod
        
if x%mod:
    from collections import defaultdict
    d=defaultdict(int)
    su=defaultdict(int)
    s=0
    for i in range(1,n+1):
        if  d[x]:cnt=i;pre=d[x];break
        d[x]=i
        s+=x
        su[i]=s
        x=x**2%mod
    else:print(s);exit()
    length=cnt-pre
    roop=(n-pre)//length
    amari=(n-pre)%length
    once=s-su[pre]+x

    print(su[pre]+roop*once+su[pre+amari]-su[pre-1]-x)


else:print(0)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().strip()

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def main():

    n,x,MOD = get_nums_l()

    ans = x
    now = x

    known = {x}
    history = [x]

    for i in range(1, n):
        y = now**2 % MOD
        if y in known:
            # ループ長と合計を検出する
            last_known = i-1
            loop_sum = y
            while history[last_known] != y:
                loop_sum += history[last_known]
                last_known -= 1
            loop_len = i - last_known

            ans += (n-i) // loop_len * loop_sum

            # log(loop_len, loop_sum)

            for j in range((n-i) % loop_len):
                if (last_known + j) < len(history):
                    ans += history[last_known + j]
            break

        known.add(y)
        history.append(y)
        ans += y
        now = y
    
    print(ans)


main()

Submission status: Accepted

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

L = [0] * M
S = [0] * (M + 1)
cnt = 1

L[X] = 1
S[1] = X

t = X
cnt = 1
for i in range(N):
  t = t * t % M
  if L[t] != 0:
    r = L[t]
    break
  L[t] = i + 2
  S[cnt + 1] = S[cnt] + t
  cnt += 1

if N <= cnt:
  print(S[N])
  exit()

roop = cnt - r + 1
d, m = divmod(N - r + 1, roop)

ans = (S[cnt] - S[r - 1]) * d
ans += S[r + m - 1]
print(ans)

Submission status: Accepted

Solution code:
n, x, m  = map(int, input().split())
a = [x]
found = {x}
while True:
    y = (a[-1] ** 2) % m
    a.append(y)
    if y in found:
        break
    found.add(y)
if n <= len(a):
    print(sum(a[:n]))
else:
    z = a.index(a[-1])
    a.pop()
    n -= z
    res = sum(a[:z])
    res += sum(a[z:]) * (n // (len(a) - z))
    res += sum(a[z:z + (n % (len(a) - z))])
    print(res)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
l=[x]
n-=1
f=-1
while(n>0):
    x=x*x
    x%=m
    if x in l:
        for i in range(len(l)):
            if x==l[i]:
                f=i
                s=l[i:].copy()
                break
    if f!=-1:
        break
    l.append(x)
    n-=1

if n==0:
    print(sum(l))
else:
    ans=sum(l)
    l=s.copy()
    ans+=sum(l)*(n//len(l))
    c=n%len(l)
    f=0
    while(c!=0):
        ans+=l[f]
        c-=1
        f+=1
    print(ans)

Submission status: Accepted

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

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

    if n == 1:
        return x

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

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

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

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

    if n == 1:
        return x

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

    return total

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

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

    if n == 1:
        return x

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

    if i == n-1:
        return total

    hoge = i
    r = i - loop_range[0][0]
    v = total - loop_range[0][1]
    hoge += r
    total += v * ((n - hoge) // r)
    hoge += r * ((n - hoge) // r)
    #while hoge < n:
    #    total += v
    #    hoge += r

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

    return total

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

Submission status: Accepted

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

now = X
temp_answer = now
exists = set([now])
order = [now]
rewards = [now]

for i in range(N-1):
    now = now**2 % M
    #print(now, exists)
    if now in exists:
        pre = order.index(now)
        circle = i+1 - pre
        circle_reward = rewards[-1] + now - rewards[pre]
        stopped = i + 1
        temp_answer += now
        break
    exists.add(now)
    order.append(now)
    rewards.append(rewards[-1] + now)
    temp_answer += now
else:
    print(temp_answer)
    sys.exit()

N = N - (stopped)
answer = temp_answer

answer += circle_reward * ((N-1)//circle)
rest = (N-1) % circle

for i in range(rest):
    now = now**2 % M
    answer += now

print(answer)

Submission status: Accepted

Solution code:
import sys
n,x,m=map(int,input().split())
a=[0]*(m+2)
cnt=[0]*(m+2)
a[1],f=x,x
cnt[f]=1
if x==0:
  print(0)
  sys.exit()
for i in range(2,m+1):
  f=f*f%m
  a[i]=f
  if cnt[f]==0:
    cnt[f]=1
  else:
    break
ind=a[1:].index(f)+1
ans=sum(a[:ind])+sum(a[ind:i])*((n-ind+1)//(i-ind))
p=(n-ind+1)%(i-ind)
ans+=sum(a[ind:ind+p])
print(ans)

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
if x == 1:
  print(n)
  exit()
u = [0 for _ in range(m)]
rs = [0 for _ in range(m+1)]
s = x
u[x] = 1
rs[1] = x
i = 2
while True:
  x = (x*x)%m
  if u[x] == 0:
    u[x] = i
    s += x
    rs[i] = s
    i += 1
  else:
    ls = u[x]
    le = i-1
    break
if n <= le:
  print(rs[n])
  exit()
ans = rs[ls-1]
ll = le-ls+1
nl = n-ls+1
lsum = rs[le] - rs[ls-1]
q = nl//ll
r = nl%ll
ans += q*lsum
ans += rs[ls-1+r] - rs[ls-1]
print(ans)

Submission status: Accepted

Solution code:

N, X, M = map(int, input().split())
dp = [False]*(M+1)
dp[X] = True
S = [0]*(M+1)
S[1] = X
tmp = X
for i in range(2, min(M+1, N+1)):
    tmp = pow(tmp, 2, M)
    if dp[tmp]:
        for j in range(1, i):
            if tmp == S[j]:
                break
        ans = 0
        for k in range(j, i):
            ans += S[k]
        ans *= (N-j+1)//(i-j)
        for k in range(1, j):
            ans += S[k]
        for k in range(j, j+(N-j+1)%(i-j)):
            ans += S[k]
        print(ans)
        break
    else:
        dp[tmp] = True
        S[i] = tmp
else:
    print(sum(S))

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
L=[]
L.append(X)
J=[0 for i in range(M+1)]
key=0
start=0
end=0
for i in range(1,M+2):
    X=(X**2)%M
    L.append(X)
    if J[X]>=1:
        key=X
        end=i
        break;
    J[X]+=1
for i in range(1,end):
    if L[end-i]==key:
        start=end-i
A=L[0:start]
B=L[start:end]
C=(N-start)//(end-start)
D=(N-start)%(end-start)
E=L[start:start+D]
if N<end:
    print(sum(L[0:N]))
else:
    print(sum(A)+sum(B)*C+sum(E))

Submission status: Accepted

Solution code:

def main():
    N, X, M = map(int, input().split())
    Set = {X}
    A = [X]
    for i in range(1,M+1):
        nextA = A[i-1]**2 % M
        if nextA in Set:
            loop = A[A.index(nextA):]
            break
        else:
            Set.add(nextA)
            A.append(nextA)

    lenloop = len(loop)
    x, y = divmod(N-len(A), lenloop)
    ans = sum(A) + x*sum(loop) + sum(loop[0:y])
    print(ans)

main()

Submission status: Accepted

Solution code:
# %
n, x, m = map(int, input().split())
import sys

result = [x]
pat = set()
pat.add(x)
flg = False
for _ in range(n - 1):
    tmp = pow(result[-1], 2, m)
    if tmp in pat:
        flg = True
        break
    elif tmp == 0:
        print(sum(result))
        sys.exit()
    else:
        result.append(tmp)
        pat.add(tmp)
        
if not flg:
    print(sum(result))

else:
    cnt = result.index(tmp)
    cycle = result[-(len(result) - cnt):]
    rest = (n - cnt)
    print(sum(result[:cnt]) + (rest // len(cycle)) * sum(cycle) + sum(cycle[:rest % len(cycle)]))

Submission status: Accepted

Solution code:
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")


N,X,M = LI()

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

# 訪れる順序、indexは移動回数
route = [X]
# 訪れた番号、高速検索用にhash tableを使う
visited = set([X])
next = X**2 % M

while True:
    if next in visited:
        loopStart = route.index(next)
        break
    else:
        route.append(next)
        visited.add(next)
        next = next**2 % M    

beforeLoop = route[:loopStart]
# print(beforeLoop)
loop = route[loopStart:]
# print(loop)

# loop前
if N < loopStart:
    ans = sum(beforeLoop[:N])
# loop後
else:
    numOfLoops,mod = divmod((N-(loopStart)),len(loop))
    # print(numOfLoops,mod)
    ans = sum(beforeLoop) + numOfLoops * sum(loop) + sum(loop[:mod])

print(ans)

Submission status: Accepted

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

dp=[False]*m
flag = True

res=[]
for i in range(n):
    res.append(x % m) 
    if dp[x] != False:
        flag = False
        break
    dp[x] = i 
    x = (x*x) % m
    if x ==0:
        print(sum(res))
        exit()
    if x==1:
        print(sum(res)+n-i-1)
        exit()

if flag:
    print(sum(res))
    exit()

r_sum = sum(res[dp[x]:i])
r_kaisu = (n-dp[x]) // (i-dp[x])
r_amari = (n-dp[x]) % (i-dp[x])

amari_st = sum(res[:dp[x]])
amari_en = sum(res[dp[x]:dp[x]+r_amari])

print(r_sum*r_kaisu+amari_st+amari_en)

Submission status: Accepted

Solution code:
def main():
    n,x,m=map(int,input().split())
    visited=[0]*m
    visit_sum=[0]*m
    i=1
    sm=x
    visited[x]=1
    visit_sum[x]=x
    work=x
    while i < n:
        work**=2
        work%=m
        sm+=work
        i+=1
#        print(sm,work)
        if not visited[work]:
            visited[work]=i
            visit_sum[work]=sm
        else :
            break
    else :
        print(sm)
        exit()
    loop_sum=sm-visit_sum[work]
    loop_num=i-visited[work]
    if visited[work]!=1: 
        initial_sum=visit_sum[visited.index(visited[work]-1)]
    else :
        initial_sum=0

    out=initial_sum
#    print(out)
    out+=(n-visited[work]+1)//loop_num*loop_sum
#    print(out)
    work_num=(n-visited[work]+1)%loop_num
    if work_num>0:
        out+=visit_sum[visited.index(visited[work]-1+work_num)]-initial_sum
        
    print(out)

main()

Submission status: Accepted

Solution code:
N, X, M = [int(v) for v in input().split()]

def f(a):
    return a * a % M

a = X

map = {}
ary = [a]
map[a] = 0

sub = [0, a]
last_sub = a

count = 1
for i in range(1, N):
    a = f(a)
    if a == 0:
        break
    if a in map:
        break
    else:
        map[a] = i
    count += 1
    last_sub += a
    sub.append(last_sub)

if a == 0:
    print(sub[-1])
    exit()


def naive(a):
    total = a
    ary = [a]
    for i in range(1, N):
        a = f(a)
        ary.append(a)
    return ary
    
#n_ary = naive(X)
#print(n_ary)
#print(sum(n_ary))

j = map[a]

#print(sub)
#print(j)

unit = sub[-1] - sub[j]
#print(unit)

l = count
i = (N - j) % (l - j)
d = (N - j) // (l - j)

#i = N % l
#d = N // l

#print(len(sub), i, j)
print(unit * d + sub[i + j])

#print(sub[-1] * (d + 1) * d // 2 + sub[i])

Submission status: Accepted

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

ans = []
chk = [0]*(m+1)

tmp = x
tmp %= m
idx = 0

for i in range(n):
    ans.append(tmp)
    if tmp == 0:
        print(sum(ans))
        exit()
    if chk[tmp] == 1:
        idx = i
        break
    chk[tmp] = 1
    tmp *= tmp
    tmp %= m

if idx == 0:
    print(sum(ans))
    exit()

li = [0]*(m+1)

l_num = ans[-1]

for i in range(len(ans)):
    if l_num == ans[i]:
        f_idx = i
        break

li[0] = l_num

shuki = len(ans)-f_idx-1

for i in range(1,shuki):
    li[i] = li[i-1] + ans[f_idx+i]

t_ans = 0
t_ans += (n-idx-1) // shuki * li[shuki-1]
t_ans += li[(n-idx-1) % shuki]

print(sum(ans)-ans[-1]+t_ans)
#print(t_ans,n,sum(ans),li[shuki])

Submission status: Accepted

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

a = X
s = set([a])
lst = [0]*M
lst[a] = 1
rlt = 0

j = 0
f = 1
for i in range(2,N+1):
  a = a**2 % M
  if a == 0:
    f = 2
    break
  elif a in s:
    j = lst[a]
    f = 0
    break
  else:
    lst[a] = i
    s.add(a)

if f > 0:
  print(sum(s))
else:
  t = 0
  k = i - j
  p = (N-j+1)//k
  r = (N-j+1)%k
  for u in range(1,M):
    if 0 < lst[u] < j:
      rlt += u
    elif lst[u] >= j:
      t += u
      if lst[u]-j+1 <= r:
        rlt += u
  rlt += t*p
  print(rlt)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
d = [0]*(m+1)
check = [x]
tmp = x
for i in range(1, n):
    tmp = (tmp**2)%m
    if d[tmp]: break
    d[tmp] = 1
    check.append(tmp)

for i in range(len(check)):
    if tmp == check[i]:
        index = i
        break
sum_c = sum(check[index:])
ans = sum(check)
nokori = n - len(check)
kuri = nokori//len(check[index:])
ans += kuri*sum_c
nokori -= kuri*len(check[index:])
ans += sum(check[index:index+nokori])
print(ans)

Submission status: Accepted

Solution code:
import math
import collections
def main():

    N, X, M = map(int, input().split())
    visited = dict()
    visited[X] = 0
    A = [X]
    v = X
    j = -1
    isperiod = False
    for i in range(1, N):
        v = (v * v) % M
        if v not in visited:
            visited[v] = i
            A.append(v)
        else:
            j = visited[v]
            isperiod = True
            break

    if isperiod:
        u = sum(A[:j])
        B = A[j:]
        p = len(B)
        u += ((N-j) // p) * sum(B) + sum(B[:(N-j) % p])
        return u
    return sum(A)



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
l=input().split()
n=int(l[0])
x=int(l[1])
m=int(l[2])
hashi=dict()
pref=0
count=0
prefix=[]
for i in range(n):
    if(i==0):
        ans=x%m
    else:
        ans=ans*ans
        ans%=m
    if(ans in hashi):
        period=i-(hashi[ans][0])
        num1=hashi[ans][0]
        k=(n-num1)//period
        rem=(n-(num1+k*period))
        count=count+prefix[num1]
        count=count+k*(pref-hashi[ans][1])
        for j in range(rem):
            if(j!=0):
                ans=ans*ans
            ans%=m
            count+=ans
        break
    hashi[ans]=(i,pref)
    prefix.append(pref)
    pref+=ans
print(max(pref,count))

Submission status: Accepted

Solution code:
def main():
    n,x,m = tuple([int(t)for t in input().split()])

    a = x
    s = a

    nextvalues = [a]
    values = set([a])

    for i in range(1,n):
        a = a*a % m
        if a in values:
            idx = nextvalues.index(a)
            size = i-idx
            sumofsubset = sum(nextvalues[idx:i])
            s += sumofsubset*((n-i)//size)+sum(nextvalues[idx:idx+(n-i)%size])
            break
        s += a
        nextvalues.append(a)
        values.add(a)
    print(s)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, X, M = read_ints()
    seen = [0]*M
    answer = X
    cycle_length = 1
    cycle_prefix = [0, X]
    N -= 1
    count = 0
    while N > 0:
        next_X = (X**2) % M
        if seen[next_X]:
            cycle_length = count-seen[next_X]+1
            break
        seen[next_X] = seen[X]+1
        cycle_prefix.append(cycle_prefix[-1]+next_X)
        answer += next_X
        N -= 1
        X = next_X
        count += 1
    if N == 0:
        return answer
    answer += (N//cycle_length)*(cycle_prefix[-1]-cycle_prefix[-cycle_length-1])
    N %= cycle_length
    while N > 0:
        X = (X**2) % M
        answer += X
        N -= 1
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import copy

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

visited = [-1]*(m+1)
when = [-1]*(m+1)
ans = 0
i = 1
while i <= n:
    ans += x
    if x == 0:
        break
    if visited[x] > -1:
        cycle = (n - i) // (i - when[x])
        ans += cycle*(ans - visited[x])
        i += cycle*(i - when[x]) + 1
        visited = [-1]*(m+1)
        when = [-1]*(m+1)
        x **= 2
        x %= m    
        continue
    visited[x] = copy.deepcopy(ans)
    when[x] = copy.deepcopy(i)
    x **= 2
    x %= m
    i += 1


print(ans)

Submission status: Accepted

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

lm = [x]
a = x

zero = 0
for i in range(m):
    a = a ** 2 % m
    if a == 0:
        zero = 1
        break
    lm.append(a)

if zero == 1:
    if n < len(lm):
        print(sum(lm[:n]))
    else:
        print(sum(lm))
        

else:
    last = lm[m]
    for i in range(1, m+1):
        if lm[m-i] == last:
            syuki = i
            break

    for i in range(2, m//syuki + 2):
        if m - i*syuki < 0:
            amari = (m+1) % syuki
        if lm[m - i*syuki] != last:
            amari = m - (i-1) * syuki + 1
            break

    l1 = lm[:amari]
    l2 = lm[amari:amari + syuki]


    if n <= amari:
        print(sum(l1[:n]))

    else:
        n -= amari
        print(sum(l1) + sum(l2) * (n//syuki) + sum(l2[:(n%syuki)]))

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
pass_num = set()
route = []
num = x
count = 0
ans = 0
while num not in pass_num:
    count += 1
    pass_num.add(num)
    route.append(num)
    num = (num * num) % m
# 何回目からループなのか求める
index = route.index(num)
pre = route[:index]
latter = route[index:]
if count >= n:
    # 趣味レーションで間に合う
    print(sum(route[:n]))
    exit()
else:
    ans = sum(pre)
    n -= len(pre)
    roop_cnt = len(latter)
    N = n // roop_cnt
    ans += N * sum(latter)
    n -= N * roop_cnt
    ans += sum(latter[:n])
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n,x,m=LI()
s={x%m:(1,x%m)}
L=[x%m]
now=x%m
cycle=1
ret=x%m
diff=0
pre=0
for i in range(2,m+2):
    now=pow(now,2,m)
    ret += now
    if now in s:
        pre, pre_ret = s[now]
        cycle=i-pre
        diff=ret-pre_ret
        break
    s[now]=(i,ret)


ans=diff*((n-pre)//cycle)+pre_ret
for k in range((n-pre)%cycle):
    now = pow(now, 2, m)
    ans+=now

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, x, m = map( int, input().split() )
# n, x, m = 10000000000, 10, 99959

found = [ -1 for _ in range( m ) ]
summation = [ 0 ]
a = x
length, loop_s, s_0, start = -1, -1, -1, -1
for i in range( n ):
    if found[ a ] > -1:
        length = i - found[ a ]
        loop_s = summation[ i ] - summation[ found[ a ] ]
        start = found[ a ]
        s_0 = summation[ start ]
        # print( length, loop_s, s_0, a, start )
        break
    else:
        found[ a ] = i
    # print( i, a )
    summation.append( summation[ -1 ] + a )
    a = ( a * a ) % m

if length < 0:
    print( summation[ n ] )
else:
    times = ( n - start ) // length
    rem = ( n - start ) % length
    rem_s = summation[ start + rem ] - s_0
    print( s_0 + loop_s * times + rem_s )

Submission status: Accepted

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

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, X, M = map(int, input().split())

def mod(x):
    return x % M

a = X

i = 0

ans = 0
last = -1

dic = []

while a != 0 and i < N:
    ans += a
    a = mod(a * a)
    i += 1

    if a in dic:
        last = dic.index(a)
        break

    dic.append(a)


if i != N and a != 0:
    tdic = dic[last:]
    if N - i >= len(tdic):
        sdic = sum(tdic)
        ans += sdic * ((N - i) // len(tdic))

    for j in range((N - i) % len(tdic)):
        ans += tdic[j]

print(ans)

Submission status: Accepted

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

amari = [x]
amariset = {x}
cnt = 0
p = 0

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

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

Submission status: Accepted

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

A = [x]
where = {x: 0}
a = x
for i in range(1, n):
    a = A[-1]**2 % m
    if a in where:
        break
    where[a] = i
    A.append(a)

perstart = where[a]
res = sum(A)
rem = n - len(A)
per = len(A) - perstart
res += rem//per*sum(A[perstart:perstart+per])
res += sum(A[perstart:perstart + (rem%per)])

print(res)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
C = X
F = {X}
S = 0
cnt = 0
loop = 0
loop_S = 0
while cnt < N:
    S += C
    cnt += 1
    C *= C
    C %= M
    if C in F:
        break
    F.add(C)
st = C
L = 0
if cnt < N:
    val = (st * st) % M
    loop += 1
    loop_S = st
    while val != st:
        loop_S += val
        loop += 1
        val *= val
        val %= M
    ccnt = N - ((N-cnt)//loop)*loop - cnt
    res = 0
    val = st
    while ccnt > 0:
        res += val
        val *= val
        val %= M
        ccnt -= 1
    print(S+loop_S*((N-cnt)//loop)+res)
else:
    print(S)

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)