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 sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, X,M = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    mod=M

    dp=[[0,0] for _ in range(M)]
    
    cnt=1
    tot=X
    dp[X]=[cnt,tot]
    while cnt<N:
        X=X*X%M
        printe(X)
        if X==0:
            print(tot)
            return
        if not dp[X][0]:
            cnt+=1
            tot+=X
            dp[X]=[cnt,tot]
            if cnt==N:
                print(tot)
                return
        else:
            break
    syuki=cnt+1-dp[X][0]
    val=X+tot-dp[X][1]
    d,a=divmod(N-dp[X][0],syuki)
    tot=dp[X][1]
    tot+=val*d
    for i in range(a):
        X=X*X%M
        tot+=X
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
a=[x]
check=set()
check.add(x)

past=x
cnt=1
while(1):
  now=(past**2)%m
  if now not in check:
    a.append(now)
    check.add(now)
    cnt+=1
    past=now
    if cnt==n:
      print(sum(a))
      exit()
  else:
    #timeは周期の長さ
    time=len(a)-a.index(now)
    #timeより前のものをpreとする
    pre=a.index(now)
    #preの合計
    pre_sum=sum(a[:a.index(now)])
    #循環したものの合計
    time_sum=((n-pre)//time)*sum(a[a.index(now):len(a)])+sum(a[a.index(now):a.index(now)+(n-pre)%time])
    
    print(pre_sum+time_sum)
    exit()

Submission status: Accepted

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####
MOD = 998244353
YES, NO, IMP = "YES", "NO", "IMPOSSIBLE"
from collections import defaultdict as ddic


def solve(N, X, M):
    seen = {X: 0}
    t = 0
    while True:
        t += 1
        if t == N:
            return sum(seen)
        X2 = X*X%M
        if X2 not in seen:
            seen[X2] = t
            X = X2
            continue
        break

    base = sum(seen)
    N -= t
    u = seen[X2]
    mu = t - u
    period = sum(k for k,v in seen.items() if v >= u)
    Q, R = divmod(N, mu)
    #print("YO", base, N, u, mu, period, Q, R, ';', X)
    
    base += Q * period

    X = X2
    while R:
        base += X
        X *= X
        X %= M
        R -= 1

    return base

def brute(N, X, M):
    A = [X]
    while len(A) < N:
        A.append(A[-1] ** 2 % M)
    #print(A)
    
    return sum(A)
#N, X, M = 3,2,7
#print(brute(N,X,M))
#ans = solve(N,X,M)
#print ans

if 0:
    for n in xrange(1, 100):
        for x in xrange(1, 10):
            for m in xrange(x + 1, 100):
                if solve(n,x,m) != brute(n,x,m):
                    print("!", n,x,m, ';',solve(n,x,m), brute(n,x,m))
                    break
            
print solve(*rrm())

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
ans = X
loop = 1
def f(a):
    return (a * a) % M


appear = [0] * (M + 1)
tmp = f(X)
appear[X] = loop
while appear[tmp] == 0:
    loop += 1
    appear[tmp] = loop
    tmp = f(tmp)

loopstart = tmp
tmp = X
before_loop_sum = 0
before_loop_len = 0
while tmp != loopstart:
    before_loop_sum += tmp
    before_loop_len += 1
    tmp = f(tmp)

loop_sum = loopstart
loop_len = 1
tmp = f(loopstart)
while tmp != loopstart:
    loop_sum += tmp
    loop_len += 1
    tmp = f(tmp)

if N < before_loop_len:
    tmp = X
    ans = 0
    for i in range(N):
        ans += tmp
        tmp = f(tmp)
else:
    N -= before_loop_len
    ans += before_loop_sum
    n_loop = N // loop_len
    N -= loop_len * n_loop
    ans += n_loop * loop_sum
    tmp = loopstart
    for i in range(N):
        ans += tmp
        tmp = f(tmp)
print(ans- X)

Submission status: Accepted

Solution code:
def main():
    n, x, mod = map(int, input().split())
    a = x
    val = set()
    val_arr = []
    idx = {}
    rep = []
    init = []
    for i in range(n):
        if a in val:
           rep = val_arr[idx[a]:]
           init = val_arr[:idx[a]]
           break
        else:
            idx[a] = i
            val.add(a)
            val_arr.append(a)
            a = a ** 2 % mod
    if len(rep) > 0:
        ans = sum(init)
        ans += sum(rep) * ((n - len(init)) // len(rep))
        ans += sum(rep[:(n - len(init)) % len(rep)])
    else:
        ans = sum(val_arr)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
seen=[-1]*(2*10**5)
A=[0]*(2*10**5)
A[0]=x


now=x ;seen[x]=0
for i in range(1,n):
    now= (now**2)%m 
    A[i]=now
    if seen[now]!=-1:
        st = sum(A[:seen[now]])
        gr = sum(A[seen[now]: i ])
        naga= i-seen[now]
        ret = (n-seen[now])//naga
        print(st+ gr*ret + sum(A[seen[now]: seen[now]+(n-seen[now])%naga]))
        exit()
    else:
        seen[now]=i
else:
    print(sum(A[:n]))

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
A = [0]*M
S = 0
r = X % M
A[r] = 1
d = 0
I = 0
for i in range(1,M+1):
    r = (r*r) % M
    if A[r] == 0:
        A[r] = i+1
    else:
        I = A[r]
        j = i+1
        d = j-I
        break
r = X
for i in range(I):
    S += r
    r = (r*r) % M
if d != 0:
    t,u = (N-I)//d,(N-I)%d
    s = 0
    for i in range(d):
        s += r
        r = (r*r) % M
    S += s*t
    for i in range(u):
        S += r
        r = (r*r) % M
print(S)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
nxt = [-1] * m
now = x
while nxt[now] == -1:
    nxt[now] = now * now % m
    now = nxt[now]
junction = now
ans = x
now = x
n = n - 1
while n and now != junction:
    now = nxt[now]
    n -= 1
    ans += now
if n == 0:
    print(ans)
    exit()

llen = 1
lsum = junction
now = nxt[junction]
while now != junction:
    llen += 1
    lsum += now
    now = nxt[now]
ans += lsum * (n // llen)
n = n % llen

now = junction
while n:
    now = nxt[now]
    n -= 1
    ans += now
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, X, M = map(int, input().split())
    a = X
    r = a
    i = 1
    S = {X: (0, 0)}
    ns = True
    while i < N:
        an = (a * a) % M
        if an == 0:
            break
        if ns and an in S:
            l = S[a][1] - S[an][1] + 1
            skip = (N - i - 1) // l
            r += (r - S[an][0]) * skip
            i += l * skip
            ns = False
        if i >= N:
            break
        a = an
        S[a] = (r, i)
        r += a
        i += 1

    return r

# print("Yes" if main() else "No")
print(main())

Submission status: Accepted

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

data = [X for i in range(M+1)]
val = set([X])

start = -1
period = -1
for i in range(1,M+1):
    data[i] = pow(data[i-1],2,M)
    if data[i] in val:
        for j in range(0,i):
            if data[j]==data[i]:
                start = j
                period = i-j
                break
        break
    else:
        val.add(data[i])

if N<=M:
    print(sum(data[:N]))
else:
    res = sum(data[:start])

    backet = sum(data[start:start+period])
    Q = (N - start) // period
    R = (N- start) % period

    res += backet*Q + sum(data[start:start+R])
    print(res)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
Memo = [-1] * M
Cumsum = [0] * M
cumsum = X
x = X

for i in range(N):
    if Memo[x] != -1:
        break
    Memo[x] = i
    Cumsum[x] = cumsum
    x = x * x % M
    cumsum += x
else:
    print(cumsum-x)
    exit()
loop_length = i - Memo[x]
init_sum = Cumsum[x]
loop_sum = cumsum - init_sum

n_from_init = N - i - 1
n_loops, n_from_loopend = divmod(n_from_init, loop_length)
cumsum += n_loops * loop_sum

for i in range(n_from_loopend):
    x = x * x % M
    cumsum += x

print(cumsum)

Submission status: Accepted

Solution code:
def main():
    n,x,m = map(int,input().split())
    if n == 1:
        print(x)
        return
    
    start = x
    arr = [x]
    visited = set()
    visited.add(x)
    prev = x
    curr = pow(prev,2,m)
    while curr not in visited:
        visited.add(curr)
        arr.append(curr)
        prev = curr
        curr = pow(prev,2,m)

    total = 0
    index = 0
    while n > 0 and index < len(arr):
        total += arr[index]
        n -= 1
        index += 1

    while arr[0] != curr:
        arr.pop(0)

    total += sum(arr)*(n//len(arr))
    for i in range(n%len(arr)):
        total += arr[i]

    print(total)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    n,x,m=MI()
    seq=[x]
    y=x
    for i in range(2*10**5+10):
        y=((y%m)**2)%m
        seq.append(y)
        #print(y)
    #print(seq)
    z=seq[m-1]
    repeat=[]
    for i in range(1,m+1):
        repeat.append(seq[i+m-1])
        if seq[i+m-1]==z:
            rep=i
            #print(i)
            break
    #print(len(repeat)==m)
    if n<=m:
        print(sum(seq[:n]))
    else:
        ans=sum(seq[:m])
        #print(repeat[:1])
        counts=(n-m)//rep
        S=sum(repeat)
        ans+=S*counts
        rest=(n-m)%rep
        last=m-1+counts*rep
        '''for i in range(last+1,n):
            ans+=repeat[(i-(m-1))%rep]'''
        for i in range(rest):
            ans+=repeat[i]
        print(ans)
    
        
        
        
        
    
        
                    
            
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:


def solve(N,X,M):
    if X == 0:
        return 0
    memo = [-1]*(M+3)
    acc = [0]*(M+4)
    x = X
    for i in range(M):
        if memo[x] >= 0:
            break
        acc[i+1] = acc[i]+x
        memo[x] = i
        x = (x*x)%M


    end = i
    start = memo[x]
    cycle = end - start

    if N < end:
        return acc[N]

    cycle_sum = acc[end]-acc[start]

    res = acc[start]

    N -= start
    res += (N//cycle)*cycle_sum
    res += acc[start+(N%cycle)]-acc[start]
    return res


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

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
p=[0]*(m+1)
a=x
t=0
s=0
for i in range(2*m):
    if p[a]==1:
        p[a]=2
        break
    else:
        p[a]=1
        a=a**2%m
a=x
S=0
for i in range(2*m):
    if p[a]==1:
        s+=1
        S+=a
        a=a**2%m
    else:
        s+=1
        S+=a
        break
T=0
A=0
for i in range(2*m):
    a=a**2%m
    t+=1
    T+=a
    if p[a]==2:
        A=a
        break


a=x
if n<=s:
    ans=0
    for i in range(n):
        ans+=a
        a=a**2%m
    print(ans)
else:
    ans=S
    a=A
    n-=s
    ans+=(n//t)*T
    n=n%t
    for i in range(n):
        a=a**2%m
        ans+=a
    print(ans)

Submission status: Accepted

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

ans = 0
A = []
T = [-1]*M
i = 0
f = False
while i<N:
  if T[X]!=-1 and not f:
    f = True
    ans += sum(A[T[X]:])*((N-i)//(i-T[X]))
    i += (N-i)//(i-T[X])*(i-T[X])
    continue
  A += [X]
  T[X] = i
  ans += X
  X = X*X%M
  i += 1
print(ans)

Submission status: Accepted

Solution code:


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

R = [-1] * M
R[X % M] = 0
A = [0] + [X % M]
a = X
for i in range(1, N):
  a **= 2
  a %= M
  if R[a] == -1:
    R[a] = i
    A += [A[-1] + a]
  else:
    print(X - X % M + (A[-1] - A[R[a]]) * ((N - R[a]) // (i - R[a])) + A[R[a] + (N - R[a]) % (i - R[a])])
    exit()
print(A[-1] + X - X % M)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

xs = [0] * M
cur = X
cicle = 0
A = []
for i in range(M + 5):
    v = cur % M 
    if xs[v] != 0:
        A.append(v)
        cicle = i
        break
    xs[v] += 1
    A.append(v)
    cur *= cur
    cur %= M

start = 0
for i in range(cicle):
    if A[i] == A[-1]:
        start = i
# print(start)
# print(A)
l = cicle - start
ans = sum(A[0:start])
ans += ((N - start) // l) * sum(A[start:-1])
ans += sum(A[start:start+((N - start) % l)])

print(ans)

Submission status: Accepted

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

table = [0]*m

def calc(init,iter):
    ret = 0
    for _ in range(iter):
        ret += init
        init = (init*init)%m
    return ret

ret = x
cur = x % m
table[cur] = 1
for rnd in range(2,min(m+2,n+1)):
    cur = (cur*cur) % m
    if table[cur]:
        per = rnd - table[cur]
        persum = calc(cur,per)
        rnds = (n - rnd) // per
        ret += rnds*persum
        ret += calc(cur,n - rnd - per*rnds+1) 
        #print(cur,table[cur],rnd,per,persum,rnds)
        break
    else:
        table[cur] = rnd
        ret += cur



print(ret)

Submission status: Accepted

Solution code:
n,x,m=[int(i) for i in raw_input().split()]
x%=m
a=[x]
d={}
d[x]=0
pos=-1
for i in range(1,min(n,100000)):
    t=(a[-1])**2
    t%=m
    if(d.get(t,-1)!=-1):
        pos=d[t]
        break
    d[t]=i
    a.append(t)
s=0
for i in a:
    s+=i
if pos!=-1:
    n-=len(a)
    a=a[pos:]
    s1=0
    for i in a:
        s1+=i
    s+=s1*(n/len(a))
    n%=len(a)
    for i in range(n):
        s+=a[i]
print s

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
cur = X
S = set([X])
while True:
    nA = cur**2 % M
    if nA in S:
        break
    S.add(nA)
    cur = nA
loop = [nA]
while True:
    ne = loop[-1]**2 % M
    if ne == nA:
        break
    loop.append(ne)
ll = len(loop)
sl = sum(loop)
ans = [X]
while True:
    ne = ans[-1]**2 % M
    if ne == nA:
        break
    ans.append(ne)
la = len(ans)
if N <= la:
    print(sum(ans[:N]))
else:
    loop_num = (N-la)//ll
    loop_head = (N-la) % ll
    print(sum(ans)+sl*loop_num+sum(loop[:loop_head]))

Submission status: Accepted

Solution code:
from itertools import accumulate

N, X, M = map(int, input().split())
s = []
A = X
ind = {}
i = 0
while A not in ind:
    s.append(A)
    ind[A] = i
    A = A * A % M
    i += 1
L = i - ind[A]
s = [0] + list(accumulate(s))
ans = s[ind[A]] + (s[-1] - s[ind[A]]) * ((N - ind[A]) // L) + s[ind[A] + (N - ind[A]) % L] - s[ind[A]]
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
li = [x]
se = {x}
for i in range(n-1):
    x = x*x%m
    if x==0:
        print(sum(li))
        exit(0)
    if x in se:
        idx = li.index(x)
        break
    li.append(x)
    se.add(x)
else:
    print(sum(li))
    exit(0)
ans = sum(li) + sum(li[idx:])*((n-len(li)) // (len(li)-idx)) + sum(li[idx:idx+(n-len(li)) % (len(li)-idx)])
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, x, m = map(int, input().split())
    dic = {}
    p = 0
    while not x in dic:
        p += 1
        dic[x] = p
        x = (x**2) % m
    if n <= p:
        ans = 0
        for ky in dic.keys():
            if dic[ky] <= n:
                ans += ky
        print(ans)
    else:
        ans = 0
        for ky in dic.keys():
            ans += ky
        n -= p
        q = dic[x]
        ln = p - q + 1
        tmp = 0
        for ky in dic.keys():
            if q <= dic[ky] <= p:
                tmp += ky
        tmp *= n // ln
        ans += tmp
        n %= ln
        for ky in dic.keys():
            if q <= dic[ky] < q + n:
                ans += ky
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ary=[x]
ans=x
d={x:0}
i=1
while x and i<n and (x**2)%m not in d:
  x=(x**2)%m
  ans+=x
  d[x]=i
  ary.append(x)
  i+=1
if x==0 or i==n:
  print(ans)
  exit()
s=d[(x**2)%m]
l=i-s
suml=sum(ary[s:])
tmp=n-i
ans+=suml*(tmp//l)
ans+=sum(ary[s:s+tmp%l])
print(ans)

Submission status: Accepted

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

exist = [False] * M 
exist[X] = True

A = [X]

while True:
    nex = A[-1]*A[-1] % M
    A.append(nex)
    if exist[nex]:
        break
    else:
        exist[nex] = True

L = len(A)
idx = 0
for i in range(L):
    if A[i] == A[-1]:
        idx = i
        break

ans = 0
for i in range(idx):
    ans += A[i]
    N -= 1
    if(N < 0): exit()

B = A[idx:(L-1)]

ans += (sum(B)*(N//len(B)) + sum(B[:(N%len(B))]))
print(ans)

Submission status: Accepted

Solution code:
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    #n = int(input())
    n, x, m = map(int, input().split())
    if n == 1:
        print(x)
        quit()
    #a, b = map(int, input().split())
    #c, d = map(int, input().split())
    #a = list(map(int, input().split()))
    #b = list(map(int, input().split()))
    ans = x
    st = set()
    from collections import deque
    a = deque([])
    xc = x
    n -= 1
    i = -1
    for i in range(n):
        xc = (xc * xc) % m
        if xc in st:break
        a += [xc]
        st.add(xc)
    if i != n-1:
        while a[0] != xc and n:
            ans += a.popleft()
            n -= 1
    total = sum(a)
    ans += (total * ((n)//(len(a))))
    for i in range((n) % len(a)):
        ans = (ans + a[i])
    print(ans)

Submission status: Accepted

Solution code:
n, x, m = [int(i) for i in input().split(" ")]

vis = [-1] * m
sq = [(i*i)%m for i in range(m)]

cur = x
y = x
flag = False
for i in range(n):
  if vis[cur] >= 0:
    flag = True
    break
  vis[cur] = i
  cur = (cur*cur)%m

cycle = max(vis) - vis[cur] + 1

ans = 0
if not flag:
  for i in range(n):
    ans += y
    y = (y*y)%m
    # print("hi")
  print(ans)
elif n <= vis[cur]:
  for i in range(min(n, vis[cur])):
    ans += x
    x = (x*x)%m
  # print("hi")
  print(ans)
else:
  for i in range(min(n, vis[cur])):
    ans += x
    x = (x*x)%m
  y = x
  rem = n - vis[cur]
  cyclesum = 0
  for i in range(cycle):
    cyclesum += y
    y = (y*y)%m
  total = rem//cycle
  extra = rem - cycle*total
  ans += cyclesum*total
  # print("cyclesum", cyclesum)
  for i in range(extra):
    ans += y
    y = (y*y)%m
  print(ans)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n,x,m = MAP()

temp = [x]

present = [-1]*(m+1)

present[x] = 0

i,j = -1, -1

for iter in range(1, n):
    new = (temp[-1]**2)%m
    if(present[new]==-1):
        temp.append(new)
        present[new] = iter
    else:
        i = present[new]
        j = iter
        break
    # print(temp)
# print(i,j)
if(i!=-1):
    sum1 = sum(temp[:i])
    left = n-i
    sum2 = sum(temp[i:j])
    zz = j-i
    sum1+=sum2*(left//zz)
    still = left%zz
    while(still>0):
        sum1+=temp[i]
        i+=1


        still-=1
else:
    sum1 = sum(temp)
print(sum1)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
s=set()
p=[]
while x not in s:
  s.add(x)
  p+=[x]
  x=(x*x)%m
  if len(p)>=n:print(sum(p));quit()
r=b=t=v=0
a=[0]
for i in p:
  if i==x:b=1
  r+=1-b
  t+=b*i
  v+=i
  a+=[a[-1]+i]*b
l=len(p)
print(v+t*((n-l)//(l-r))+a[(n-l)%(l-r)])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 998244353
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,X,M = IL()

loop = [X]
flag = DD(int)
counter = 1
flag[X] = counter


while True:
  nX = (X*X)%M
  if flag[nX]:
    loop_begin = flag[nX]
    loop_length = len(loop)-loop_begin+1
    break
  else:
    counter += 1
    flag[nX] = counter
    loop.append(nX)
  X = nX


zenhan = sum(loop[:loop_begin-1])
kouhan = sum(loop[loop_begin-1:])

if N < loop_begin:
  print(sum(loop[:N]))
else:
  N -= loop_begin-1
  kaisu = (N-1)//loop_length
  amari = (N-1)%loop_length + 1
  print(zenhan + kaisu*kouhan + sum(loop[loop_begin-1:loop_begin-1+amari]))