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:
from collections import deque

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

D = deque([X], M)
R = {X: 0}

x = X
for _ in range(min(N-1, M+1)):
  x = (x ** 2) % M
  if x in R:
    l = R[x]
    m = len(D) - l
    q, r = divmod(N - l, m)
    print(sum(D[i] for i in range(l)) + (q+1) * sum(D[i] for i in range(l, l+r)) + q * sum(D[i] for i in range(l+r, l+m)))
    break
  else:
    R[x] = len(D)
    D.append(x)
else:
  print(sum(D))

Submission status: Accepted

Solution code:
"""MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWO:,'..'xXWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO. .:kOo.,kNMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMO. .lNWWo..lXMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM
MNOxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMMMMWKxoloxKWNc  .:xxd;  ,dxxxkXMXkxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxMM
MKc''''''''''''''''.  ..'''''.   .''''.  .''MMMWx..,:. .xXo''.  .''.  ..'';kMk;'''''.  .'.''.  .''''''.  ..''.   .''MM
MWNXNNNNNNNNNNNNNNNO' ;KNNNNNKo. cKNNNd. lXNMMMK; ,0Wx. :NWXXl .dNNO' ;KNNNWMWNNNNNXc .kNNNNx. cXNNNNNO' ;KNN0; 'ONNMM
MMMMMMMMMMMMMMMMMWM0' :NMMMMWMX: .OMWWx. oWMMMMWx. ';. .dNMWWo .xMM0' :NWWMMMMMMMMWWl .OMMMWk. lWWMMWM0' ;XMMX: ,KMMMM
MMMMMMWMWkccccccccc;. :NMWNNNKd. :XMMWx. oWMMMWKo. .',. .,ldx; .dMM0' :NMMMMMMMNNWMWl .OMMMWk. lWMMMMM0' ;XMMX: ,0MMMM
MMWXKNWMWxcc,. .;cc;. :XMk,''..'lKWMMWx. oWMNx:. .lONNKxl.     .xMM0' :NMMMMMM0:,oKO' ,KMMMMk. lWWNkoc,. .;::;. ,KMMMM
MMXc.lXMMWWWNd..xWM0' :NM0;  ;kXWMMMWNl  oWMK:.;xXWWMWXx:. ,c' .dMM0' :NMMMMMMKc. ...;kWMMMMk. lWWc .:;. .clc:. ,KMMMM
MWWx. lXMWMMMK, lWM0' :NMMNx'.,ldxxoc'   oWMWNKNWWWN0o' .:kNWo .dMM0' :NMMMMMMMNO;  ,OWWWMMMk. lWM' lXx. lNMMX: ,KMMMM
MMMWk'.,xKNX0c..kWM0' :NMMMMNkl;,'',:l:  oWMMMMMWMWO' 'l0WMWWo .xMM0' :NMMMMMMMMMNd. .oXWMMMk. lWMd.....;0WMMX: ,KMMMM
MMMMWKo'...'..:kWMM0' :NMMMMMMMWWNNWWWx. oWMMMMMMMMWOxXWMWMWWo .xMM0' :NMMMMMMMMMMMKl. ,kNMMk. lWMWKkxx0NMWMMX: ,KMMMM
MMMMMMMN0kxk0XNWMMWKl;xNMMMMMMMMMMMMWM0c;kWMMMMMMMMMMMWWMMMMWk;:OMMXl,dNMMMMMMMMMMMMWO; .dNM0c;kWWMMMMMMMMMMMNd,oXMMMM
MMMMMMMMWWMWMMMMMMMMMWWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMWWMMWWMMWMMMMMMMMMMMMMMNkxKWMMWWMMMMMMMMMMMMMMWMMWMMMMM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM"""


#				 Author: Udit "luctivud" Gupta @ https://www.linkedin.com/in/udit-gupta-1b7863135/					 #


import math;   		from collections import *
import sys;   		from functools import reduce
import time;   		from itertools import groupby

# sys.setrecursionlimit(10**6)

# def input()         : return sys.stdin.readline()
def get_ints()      : return map(int, input().strip().split())
def get_list()      : return list(get_ints())
def get_string()    : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args)  : return print(*args, end=" ")


DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (+1, -1)] 
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
              (+1, +1), (+1, +0), (+1, -1), (+0, +1)]



# MAIN >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

# se = set()
# n = 16; x = 2; m = 1001
# for i in range(n):
# 	print(x % m, i)
# 	if (x % m) in se:
# 		print(x % m, i)
# 	else:
# 		se.add(x % m)
# 	x **= 2;
# 	x %= m


n, x, m = get_ints()
prefix_sum = [0]
found = set()
d = dict()
ind = 0; doneInd = 1;
for i in range(n):
	if (x % m) not in found:
		found.add(x % m)
		d[x % m] = i
		prefix_sum.append(prefix_sum[-1] + (x % m))
	else:
		ind = d[x % m]
		doneInd = i
		break
	x **= 2
	x %= m
# print(ind, doneInd, prefix_sum[ind])
# print(prefix_sum)
# print(prefix_sum)

try:
	lastset = prefix_sum[-1] - prefix_sum[ind];
	offset = prefix_sum[ind]

	sz = len(prefix_sum) - ind - 1

	rem = n - ind
	ans = offset
	ans += lastset * (rem // sz)
	ans += prefix_sum[ind + (rem % sz)] - offset
# print(sz, lastset, rem)
except:
	ans = 1

print(ans)

Submission status: Accepted

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

if X == 0:
    print(0)
    exit()

A_history = [-1] * M
sum_history = [0] * (M + 1)
A = X
all_sum = A

sum_history[0] = A

for i in range(M):
    Anext = (A * A) % M
    all_sum += Anext
    sum_history[i + 1] = all_sum
    if A_history[A] == -1:
        A_history[A] = i
    else:
        break
    A = Anext

if i >= N:
    print(sum_history[N - 1])
else:
    cycle_start = A_history[A]
    cycle_end = i - 1
    cycle_length = cycle_end - cycle_start + 1
    cycle_time = N - cycle_start
    cycle_count = cycle_time // cycle_length
    cycle_mod = cycle_time % cycle_length
    ans = sum_history[cycle_start] + (sum_history[cycle_end + 1] - sum_history[cycle_start]) * cycle_count + \
          (sum_history[cycle_start + cycle_mod - 1] - sum_history[cycle_start])
    print(ans)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, X, M = iim()

    if X == 0:
        print(0)
        return
    A = [X]

    i = 0
    vis = {X: 0}
    while i < N-1:
        a = A[i]**2 % M
        if a in vis:
            break
        elif a == 0:
            print(sum(A))
            return
        A.append(a)
        i += 1
        vis[a] = i
    else:
        a = X

    i = vis[a]
    n = len(A) - i
    a, b = divmod(N-i, n)
    ans = sum(A[i:]) * a
    for j in range(i):
        ans += A[j]
    for j in range(i, i+b):
        ans += A[j]
    print(ans)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools
import decimal
import copy
import heapq

# import numpy as np

# sys.setrecursionlimit(10 ** 6)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))
flush = lambda: sys.stdout.flush()


# ===CODE===
def main():
    n, x, m = ns()

    total = x
    ai = x
    st = {x}
    prev = [x]

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

        if ai in st:
            start = prev.index(ai)
            itrlen = len(prev) - start
            remainlen = n - i

            head = sum(prev[:start])
            itr = prev[start:]
            itrsum = sum(itr)
            remainitrsum = (remainlen // itrlen) * itrsum
            tail = sum(itr[:remainlen % itrlen])
            ans = head + itrsum + remainitrsum + tail
            print(ans)
            exit(0)

        st.add(ai)
        prev.append(ai)

    print(total)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mod=[0]*(m)

mod[x%m]=1
ans=x

for i in range(2,n+1):
    x=(x**2)%m
    #print(i,x)
    if mod[x]==0:
        ans+=x
        mod[x]=i
    else:
        #過去に2度来たことがある
        if mod[x]==-1:
            break
        #過去に1度来たことがある
        else:
            turn=i-mod[x]
            ans+=x*(((n-i)//turn+1))
            mod[x]=-1

print(ans)

Submission status: Accepted

Solution code:
N,x,MOD = map(int, input().split())
s = x
flag = False
sflag = False
if N == 1:
  flag = True
  sflag = True
  print(s)
for i in range(1,MOD):
  x = (x*x) % MOD
  s += x
  if N == (i+1):
    flag = True
    break
if flag == True:
  if sflag == False:
    print(s)
else:
  t_s = 0
  cnt = 0
  init = x
  for i in range(MOD):
    x = (x*x) % MOD
    t_s += x
    cnt += 1
    if x == init:
      break
  bi = (N-MOD)//cnt
  res = (N-MOD)%cnt
  s += t_s * bi
  for i in range(res):
    x = (x*x) % MOD
    s += x
  print(s)

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

n,x,m=mdata()
d=dd(int)
d[x]=0
l=[x]
ans=x
for i in range(n-1):
    x**=2
    if x%m in d:
        x%=m
        ans+=sum(l[d[x]:])*((n-1-i)//(len(l)-d[x])) + sum(l[d[x]:d[x]+((n-1-i)%(len(l)-d[x]))])
        break
    else:
        x%=m
        ans+=x
        d[x]=i+1
        l.append(x)
out(ans)

Submission status: Accepted

Solution code:
def do():
    n, x, m = map(int, input().split())
    if x == 1: # x = 1の時は強制的にn
        print(n)
        return
    #print(n,x,m)
    dat = []
    d = dict()
    dat.append(x)
    d[x] = True
    #print(x)
    issyu_total = x % m
    isloop = False

    for i in range(n-1): # 最大でもn-1回
        #print(x)
        x = x ** 2 % m
        if x == 0: # 0になったときはそのあと全部0 なので、
            print(sum(dat) % m)
            return
        if x in d:
            #print("hit" + str(i) + " " + str(x))
            isloop = True
            loopstart = dat.index(x)
            break
        dat.append(x)
        issyu_total = (issyu_total + x)
        d[x] = True

    if isloop is False:
        print(issyu_total)
        return

    import math

    res = 0
    #print("loop on")
    #print(loopstart)
    loopsum = sum(dat[loopstart:])
    looplength = len(dat) - loopstart

    res = sum(dat)
    n -= len(dat)

    fullloop = math.floor(n / looplength) # 範囲分
    res += fullloop * loopsum

    nokori = n % fullloop
    res += sum(dat[loopstart:loopstart+nokori])

    #print("loopcount={0}, issyutotal={1}, nokori={2}, fl ={3} ".format(looplength, issyu_total, nokori,fullloop))
    print(res)
    #print(492443256176507 - res)






do()

Submission status: Accepted

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

if N == 1:
    print(X)
    exit()

A = [-1] * (10**5 + 1)
A[1] = X

# %M は答えをMOD Mにしなさいといってくれているだけ
# M はたかだか10^5なので10^5繰り返すとどこかで循環する。循環するまで繰り返す。
S = set([X])
i = 2
while True:
    A[i] = ((A[i - 1])**2) % M
    if A[i] in S:
        break
    S.add(A[i])
    i += 1
# i -= 1
# print(f'{A[:20]=}, {S=}, {i=}')

end_idx = i - 1
start_idx = 0
for start_idx in range(i):
    if A[start_idx] == A[i]:
        break

num_circles = end_idx - start_idx + 1
# print(f'{start_idx=}, {end_idx=}, {num_circles=}')

A[0] = 0
if start_idx > N:
    ans = sum(A[:N + 1])
    print(ans)
    exit()

# print(f'{A[:20]=}')
# print(f'{A[:start_idx]=}')
v1 = sum(A[:start_idx])

remain_N = N - start_idx + 1
# print(f'{remain_N=}')

div, mod = divmod(remain_N, num_circles)
# print(f'{div=}, {mod=}')
# print(f'{A[start_idx:end_idx + 1]=}')
sum_circles = sum(A[start_idx:end_idx + 1])
# print(f'{sum_circles=}')

v2 = sum_circles * div

if mod == 0:
    v3 = 0
else:
    # print(f'{A[start_idx:start_idx + mod]=}')
    v3 = sum(A[start_idx:start_idx + mod])

ans = v1 + v2 + v3
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())
N,X,M = map(int, input().split())

first_A = [X]
mod_M = [False for i in range(M+1)]
mod_M[0] = True
mod_M[1] = True

is_break = False
for i in range(min(N-1,M+1)):
    A_n1 = pow(first_A[-1],2)%M
    if mod_M[A_n1]:
        is_break = True
        last_num = A_n1
        break
    else:
        first_A.append(A_n1)
        mod_M[A_n1] = True

if is_break:
    if last_num == 0:
        print(sum(first_A))
    elif last_num == 1:
        nokori = N-len(first_A)
        print(sum(first_A)+nokori)
    else: # roop
        loop_idx = first_A.index(last_num)
        first_A, second_A = first_A[:loop_idx], first_A[loop_idx:]
        roop = int((N-len(first_A))/len(second_A))
        nokori_kaisuu = (N-len(first_A)) - (roop*len(second_A))
        if nokori_kaisuu == 0:
            print(sum(first_A)+(sum(second_A)*roop))
        else:
            print(sum(first_A)+(sum(second_A)*roop)+sum(second_A[:nokori_kaisuu]))
else:
    print(sum(first_A))

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
init, cr = x, x
hist = [m+1, x]
for idx in range(2, n + 1):
    cr = (cr ** 2) % m
    if cr in hist:
        idx_bef = hist.index(cr)
        remains = n - idx + 1
        ans = sum(hist[1:])
        sum_period = sum(hist[idx_bef:])
        period_num = idx - idx_bef
        ans += sum_period * (remains // period_num)
        ans += sum(hist[idx_bef: idx_bef + remains % period_num])
        print(ans)
        exit()
    else:
        hist.append(cr)
print(sum(hist[1:]))

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)

n,x,m= map(int, input().split())
ans=0
v=[]
cnt=x
for i in range(m+10):
    if cnt==0 or i==n:
        print(ans)
        exit()

    elif d[cnt]==0:
        v.append(cnt)
        ans += cnt
        d[cnt]=i
        cnt = pow(cnt, 2, m)
    else:
        # 周期の始まり
        y=d[cnt]
        break
u=0
for i in range(y,len(v)):
    u+=v[i]
l=len(v)-y
xx=(n-len(v))//l
yy=(n-len(v))%l
ans+=xx*u+sum(v[y:y+yy])
print(ans)

Submission status: Accepted

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

appearance = [0] * (M + 1)
cum_sum = [0]
A = X
appearance[A] = 1
cum_sum.append(A)
a = 1
for a in range(2, N + 1):
    A = (A**2)%M
    if appearance[A] != 0:
        n = a - 1
        break
    appearance[A] = a
    cum_sum.append(cum_sum[a - 1] + A)
else: n = a

k = appearance[A]
l = (N - n) // (n - k + 1)
m = (N - n) - (n - k + 1)*l + k - 1

ans = cum_sum[n] + (cum_sum[n] - cum_sum[k - 1])*l + cum_sum[m] - cum_sum[k - 1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, X, M = map(int, input().split())
    l = [X]
    lset = set(l)
    ans = X
    bf = X
    for i in range(N):
        nx = bf**2%M
        if nx in lset:
            break
        ans += nx
        lset.add(nx)
        l.append(nx)
        bf = nx
    st = l.index(nx)
    retry = l[st:]
    remain = N - len(l)
    ans += (remain//len(retry))*sum(retry) + sum(retry[:remain%len(retry)])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

mods = [0 for i in range(M)]
vals = []
for i in range(1, M+2):
  if i == 1:
    p = X
  else:
    p = p**2 % M
  
  if mods[p] > 0:
    break
  else:
    mods[p] = i
    vals.append(p)
    if i == N:
      print(sum(vals))
      exit()

len_loop = i - mods[p]
sum_answer = sum(vals)
N_res = N - len(vals)
sum_answer += sum(vals[mods[p]-1:]) * (N_res // len_loop)
N_res = N_res % len_loop
sum_answer += sum(vals[mods[p]-1:mods[p]-1+N_res])

print(sum_answer)

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
# from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
# import numpy as np
starttime = time.time()
# import numpy as np
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

try:
    # sys.setrecursionlimit(int(pow(10,5)))
    sys.stdin = open("input.txt", "r")
    # sys.stdout = open("../output.txt", "w")
except:
    pass



n,x,m=L()
A=[x]
d={}
k=1
d[x]=1
while(A[-1]!=0 and k<n):
    y=A[-1]*A[-1]%m
    if y in d:
        break
    else:
        d[y]=1
    A.append(y)
    k+=1
if A[-1]==0:
    print(sum(A))
elif k==n:
    print(sum(A))
elif k<n:
    # print(n,k,A,y)

    # idx=A.index(y)
    # # print(idx)
    # ans=sum(A[:idx])
    # z=A[idx:]
    # # print(z)
    # ans+=sum(z)*(n-idx)//len(z)
    # total=idx+((n-idx)//len(z))*len(z)
    # rem=n-total
    # ans+=sum(z[:rem])

    # print(ans)
    pref=0
    ans=0
    rem=-2
    cnt=-1
    # print(A[:10])
    for i in range(len(A)):
        if A[i]==y:
            ans+=pref
            pref=0
            cnt=0
            rem=(n-i)%(len(A)-i)
            # print(ans)
        if rem==cnt:
            ans+=pref
        if cnt>=0:
            cnt+=1
        pref+=A[i]
    ans+=pref*((n-k+cnt)//(cnt))
    print(ans)

endtime = time.time()
# print(f"Runtime of the program is {endtime - starttime}")

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
if X == 0:
    print(0)
    exit()
U = [0] * (M + 10)
U[X] = 1
S = [0] * (M + 10)
S[1] = X
v = X
l = r = 0  # [l,r) で巡回
cycle_sum = 0
for i in range(2, M + 1):
    v = (v * v) % M
    if U[v]:
        l = U[v]
        r = i
        cycle_sum = S[i - 1] + v - S[l]
        break
    U[v] = i
    S[i] = S[i - 1] + v
if N <= l:
    print(S[N])
    exit()

ans = S[l - 1]
N -= l - 1
d, m = divmod(N, r - l)
ans += d * cycle_sum
ans += S[l + m - 1] - S[l - 1]
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
a = [-1]*10**5; a[x%m] == 0; b = [x%m]
for i in range(1, n):
    x = x**2%m
    if a[x%m] == -1:
        a[x%m] = i; b.append(b[-1]+x%m)
    else:
        s = a[x%m]-1; g = i-1
        print((b[g]-b[s])*((n-s-1)//(g-s))+b[s+(n-s-1)%(g-s)])
        break
else: print(b[-1])

Submission status: Accepted

Solution code:
N, X, M = list(map(int, input().split()))
i = 1
a = X
s = 0
L = []
while i < N and a > 0:
    L.append(a)
    s += a
    a = (a**2) % M
    if a in L:
        j = L.index(a)
        break
    i += 1
else:
    s += a
    print(s)
    exit()

# print(L)
t = sum(L[:j])
L = L[j:]
u = s-t
N = N-j
v = t+u*(N//(i-j))
if N % (i-j) == 0:
    pass
else:
    v += sum(L[:N % (i-j)])
print(v)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N, X, M = inpl()
hisS = [0] * M
pos = [-1] * M
c = S = hisS[0] = X
pos[X] = 0
for i in range(1, min(M+1,N)):
    c = c * c % M
    S += c
    if pos[c] >= 0:
        prev = pos[c]
        period = i - prev
        q = (N - prev) // period
        r = (N - prev) % period
        if prev == 0 and r == 0:
           ans = (S - hisS[prev]) * q
        else:
            ans = (S - hisS[prev]) * q + hisS[prev+r-1]
        print(ans)
        break
    else:
        hisS[i] = S
        pos[c] = i
else:
    print(S)
    exit()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
a=list()
ans=0
s=n
for i in range(n):
    ans+=x
    a.append(x)
    x=(x**2)%m
    if x in a:
        s=a.index(x)
        break

sum=0
if s!=n:
    for i in range(s, len(a)):
        sum+=a[i]   

if len(a)>s:
    ans+=sum*(((n-s)//(len(a)-s))-1)

    z=(n-s)%(len(a)-s)
    if z!=0:
        for i in range(z):
            ans+=a[s+i]
print(ans)

Submission status: Accepted

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

LOOP = [X]
wk = X
s = set()
s.add(X)
flg = True
for i in range(N-1):
  a = wk * wk % M
  if a == 0:
    print(sum(LOOP))
    exit(0)
  if a in s:
    wk = a
    flg = False
    break
  LOOP.append(a)
  s.add(a)
  wk = a
#print(LOOP)
if flg:
  print(sum(LOOP))
else:
  for i in range(len(LOOP)):
    if LOOP[i] == wk:
      beg_i = i
      break
  fin_i = len(LOOP) -1
  ans = sum(LOOP[:beg_i])
  N -= beg_i
  L = LOOP[beg_i:]
  LS = len(L)
  #print(LS)
  ans += sum(L) * (N//LS)
  N = N % LS
  ans += sum(L[:N])
  print(ans)

Submission status: Accepted

Solution code:
n,x,m = map(int, input().split())
visited=set()
from collections import defaultdict
ans=0
cnt=0
now=x
last=defaultdict(list)
while cnt!=n:
    cnt+=1
    if now in visited:
        break
    visited.add(now)
    last[now]=[ans,cnt]
    ans+=now

    now=(now**2) % m
    if now==0:
        print(ans)
        exit()

if cnt==n:
    print(ans)
    exit()

looplen=cnt-last[now][1]
looppoint=ans-last[now][0]
loopcnt,nokori = divmod(n-cnt,looplen)
ans+=(loopcnt*looppoint)
ans+=now

for i in range(nokori):
    now=(now**2) % m
    ans+=now

print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
checklist = [True] * 100000
ind = 0
l = [X]
while True:
  t = l[-1] ** 2 % M
  if checklist[t]:
    l.append(t)
    checklist[t] = False
  else:
    ind = l.index(t)
    break
S = sum(l[ind:])
L = len(l)
ans = 0
if N <= L:
  ans = sum(l[:N])
else:
  ans = sum(l)
  N -= L
  ans += S * (N // (L - ind))
  ans += sum(l[ind:ind+(N % (L - ind))])
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, x, m = map(int, input().split())
    a = x
    s = a
    seen = {a}
    seq = [a]
    for i in range(n - 1):
        if a == pow(a, 2, m):
            print(s + a * (n - i - 1))
            return
        else:
            a = pow(a, 2, m)
            if a in seen:
                si = seq.index(a)
                sl = i - si + 1
                ps = s - sum(seq[:si])
                ln = (n - i - 1) // sl
                lm = (n - i - 1) % sl
                print(s + ps * ln + sum(seq[si:si + lm]))
                return
            s += a
            seen.add(a)
            seq.append(a)
    print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def naive(N, X, M):
    ans = X
    ans_prev = X
    for i in range(2, N + 1):
        an1 = ans_prev % M
        an1 = pow(an1, 2, M)
        ans += an1
        ans_prev = an1
    return ans

def doubling(N, X, M):
    ans = X
    ans_prev = X
    A = [X]
    computed = set({})

    for i in range(2, N + 1):
        an1 = ans_prev % M
        an1 = pow(an1, 2, M)
        if an1 in computed:
            breakA = an1
            break
        A.append(an1)
        computed.add(an1)
        ans_prev = an1

    # if break
    num_break = len(A)
    index = A.index(breakA)
    num_length = len(A) - index
    total = sum(A[:index])
    repeat_length = (N - index) // num_length
    remain_length = (N - index) % num_length
    total_sub = sum(A[index:]) * repeat_length
    total += total_sub
    if remain_length > 0:
        sub = naive(remain_length, breakA, M)
        total += sub    
    return total


def solve(N, X, M):
    return -1

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

    if N < 10 ** 7:
        print(naive(N, X, M))
    else:
        print(doubling(N, X, M))
        # print(naive(N, X, M))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A=[]
A.append(X)
visit={}
for i in range(M+1):
    X=pow(X,2,M)
    if X not in visit:
        visit[X]=1
        A.append(X)
    else:
        break
loop_point=A.index(X)
notloop=A[:loop_point]
loop=A[loop_point:]

len_notloop=len(notloop)
len_loop=len(loop)


SUM_notloop=[0]
for x in notloop:
    SUM_notloop.append(SUM_notloop[-1]+x)


SUM_loop=[0]
for x in loop:
    SUM_loop.append(SUM_loop[-1]+x)

ans=0
if len_notloop<N:
    ans+=SUM_notloop[-1]
    N-=len_notloop
    sho,amari=N/len_loop,N%len_loop
    ans+=SUM_loop[-1]*sho
    ans+=SUM_loop[amari]
elif N<=len_notloop:
    ans=SUM_notloop[N]
print ans

Submission status: Accepted

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

term_set={X}
term_list=[X]
for i in range(1,N):
  term1=term_list[-1]
  term2=term1**2%M
  term_list.append(term2)
  if term2 in term_set:
    break
  else:
    term_set.add(term2)
#print(term_list)
#print(len(term_list))

if len(term_list)==N:
  print(sum(term_list))
else:
  c2=len(term_list)-1
  c1=term_list.index(term_list[-1])
  #print(c1,c2)
  
  answer=sum(term_list[:c1])
  sum_cycle=sum(term_list[c1:c2])
  
  num_cycle=(N-c1)//(c2-c1)
  rem_cycle=(N-c1)%(c2-c1)
  answer+=sum_cycle*num_cycle
  answer+=sum(term_list[c1:c1+rem_cycle])
  print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, X, M = MI()
    def f(x): return x % M
    # N += 2

    ans = 0
    r = [0] * (M+1)
    p = 1
    q = 0
    pre = X
    # S = [0] * (N+1)
    # S[0] = X
    S = [X]
    for i in range(1, N):
        tmp = f(pre ** 2) % M
        # print(tmp)
        if r[tmp]:
            # print('aa', i, r[tmp])
            left = N - r[tmp]
            loop = i - r[tmp]
            # print(left, loop)
            p, q = left // loop, left % loop
            # print(p, q, S[i-1] - S[r[tmp]-1], i-1, r[tmp]-1)
            # print(S)
            ans = S[r[tmp]-1]
            ans += p * (S[i-1] - S[r[tmp]-1])
            if q > 0:
                ans += (S[r[tmp]+q-1] - S[r[tmp]-1])
            print(ans)
            # ans += S[]
            return 
        pre = tmp
        r[tmp] = i
        # S[i] = tmp + S[i-1]
        S.append(tmp + S[i-1])
    else:
        # print(S)
        print(S[N-1])



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
A = [100001]*(2*(10**5)+100)
A[1] = X
S = {X}
ans = X
for i in range(2,min(2*M+1,N)+1):
  X = X**2
  X %= M
  ans += X
  A[i] = X
  if X in S:
    break
  S.add(X)
  #print(i)
#[print(A[i]) for i in range(6)]
if N == 1:
  print(X)
  exit()
elif i == N:
  print(ans)
else:
  j = A[:i+1].index(A[i])
  if i == j:
    print(ans)
  k = (N-i)//(i-j)
  l = (N-i)%(i-j)
  #print(j,k,l)
  ans += k*sum(A[j+1:i+1])+sum(A[j+1:j+l+1])
  print(ans)

Submission status: Accepted

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

r = [0] * (m)

r[x] = 1
a = x

t = 0
u = 0

s = [0, x]

for i in range(2, m+2):

    a = (a ** 2) % m
    s.append(s[-1] + a)

    if r[a] == 0:
        r[a] = i
    else:
        t = i - r[a]
        u = r[a]
        break

if u >= n:
    print(s[n])

else:
    #print(s, t, u)
    p = (n - (u-1)) // t
    q = (n - (u-1)) % t

    ans = s[u-1+ q] + p * (s[u+t] - s[u])

    print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
l=[x]
c=1
d=-1
f=0
while(x>0 and c<n):
    g=(x*x)%m
    d=g
    if(g in l):
        f=1
        break
    l.append(g)
    x=g
    c+=1
s=sum(l)
if(f==1):
    r=l.index(g)
    o=(n-c)//(c-r)
    t=(n-c)%(c-r)
    s+=o*(sum(l[r:]))+sum(l[r:r+t])
print(s)

Submission status: Accepted

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

A=[0,X]
D={}
D[X]=1
for i in range(2,10**7):
    A.append((A[-1]**2)%M)
    if A[-1] not in D:
        D[A[-1]]=i
    else:
        R=i
        L=D[A[-1]]
        break
    
#print(A)
#print(D)
#print(L,R)
    
Front=L-1

if N<=Front:
    print(sum(A[:N+1]))
    exit()
N-=Front
X=N//(R-L)
Y=N%(R-L)
#print(Y)
if Y>0:
    print(sum(A[:Front+1])+X*sum(A[L:R])+sum(A[L:L+Y]))
else:
    print(sum(A[:Front+1])+X*sum(A[L:R]))
#print(sum(A[:Front+1]),sum(A[L:R+1]))

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ans=x
totol=n
was=[0]*m
was[x]=1
cs=x
cr=1
n-=1
seq=[x]
while n>0:
	cs=cs*cs%m
	seq.append(cs)
	cr+=1
	n-=1
	if was[cs]:
		if cs<=1:exit(print(ans+cs*(n+1)))
		res=sum(seq[:was[cs]-1])
		totol-=was[cs]-1
		loop=cr-was[cs]
		sumonloop=sum(seq[was[cs]:cr])
		res+=totol//loop*sumonloop
		for i in range(totol%loop):
			res+=cs
			cs=cs*cs%m
		exit(print(res))
	else:was[cs]=cr
	ans+=cs
print(ans)
'''
492443256176507
9 2 7

26

'''

Submission status: Accepted

Solution code:
N, X, M = map(int,input().split())
A = [X]
As = set(A)
Lstart = 0
for i in range(N):
    An = A[-1]**2 % M
    if An in As:
        Lstart = A.index(An)
        break
    else:
        A.append(An)
        As.add(An)
LenBefL = Lstart
LenLoop = len(A) - Lstart
if LenLoop > 0:
    ans = sum(A[:Lstart])+sum(A[Lstart:])*((N-LenBefL)//LenLoop) + sum(A[Lstart:Lstart + (N-LenBefL)%LenLoop])
else:
    ans = sum(A)
print(ans)

Submission status: Accepted

Solution code:
#
import sys
import math
import itertools


# 整数をいくつか入力
n,x,m = (int(i) for i in input().split())

if n < 100000:
    b=0
    for i in range(n):
        b += x
        #print(x)
        x = (x*x) %m
    print(b)
else:
    ll=[0]*100000
    s=0
    for i in range(100000):
        ll[i]=x
        s += x
        x = (x*x) %m
    for i in range(99998,-1,-1):
        if ll[i]==ll[99999]:
            term=99999-i
    p=(n-100000)//term
    q=(n-100000)%term
    r=0
    for i in range(term):
        r += ll[100000-term+i]
    s += r * p
    for i in range(q):
        s += ll[100000-term+i]
    print(s)

Submission status: Accepted

Solution code:
def main():
    n,x,m = map(int,input().split())
    R = [x]
    g = set([x])
    for i in range(1,min(m,n)):
        x = x**2 % m
        if not x in g:
            R.append(x)
            g.add(x)
        else:
            break
    
    R_ac = [0]*(len(R)+1)
    for i in range(len(R)):
        R_ac[i+1] = R_ac[i] + R[i]

    j = R.index(x)
    ct = n
    
    ans = R_ac[j]
    ct-=j

    q = ct//(len(R)-j)
    ans+= q*(R_ac[-1]-R_ac[j]) 
    ct-=q*(len(R)-j)

    ans+= R_ac[j+ct] - R_ac[j]

    print(ans)
main()