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

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

cnt = [0] * M
accu = [X]
cnt[X] = 1
for i in range(2,min(N+1, M+3)):
    s = (accu[-1] ** 2) % M
    if cnt[s] == 0:
        cnt[s] = i
        accu.append(s)
    else:
        c = i - cnt[s] 
        su = sum(accu[cnt[s]-1:])
        ans = sum(accu[:cnt[s]-1])
        N -= (cnt[s] - 1)
        n = N // c
        ans += n * su
        N %= c
        ans += sum(accu[cnt[s]-1:cnt[s]+ N -1])
        print(ans)
        sys.exit()

print(sum(accu))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

n, x, m = map(int, input().split())
s = set([x])
l = [x]
for i in range(m):
    x = x**2 % m
    if x in s:
        start_index = l.index(x)
        break
    else:
        s.add(x)
        l.append(x)
ans = sum(l[:start_index])

q = l[start_index:]
p = (n - start_index) // len(q)
ans += sum(q) * p
ans += sum(q[:(n - p*len(q) - start_index)])
print(ans)

Submission status: Accepted

Solution code:
N,X,mod = map(int,input().split())
visited = [False for i in range(mod)]
visited[X]=True
mod_loop = [X]
now = X
while visited[now**2%mod] == False:
    mod_loop.append(now**2%mod)
    visited[now**2%mod] = True
    now = now**2%mod
now=now**2%mod

que = []
for i in range(len(mod_loop)):
    if mod_loop[i] == now:
        que.append(i)

leftsum = mod_loop[:que[0]]

looper = mod_loop[que[0]:]

if N<=len(leftsum):
    print(sum(leftsum[:N]))
else:
    ans = sum(leftsum)
    u,v = divmod(N-len(leftsum),len(looper))
    ans += u*sum(looper) + sum(looper[:v])
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n,x,m = map(int,input().split())
    if m == 0:
        print(0)
        return
    t = [x]
    k = -1
    for _ in range(n-1):
        x = x**2 % m
        if x in t:
            k = x
            break
        t.append(x)
    if k not in t:
        print(sum(t))
        return
    else:
        s = t.index(k)
        ans = sum(t[0:s])
        b = t[s:len(t)]
        n -= s
        ans += sum(b) * (n//len(b))
        ans += sum(b[0:n%len(b)])
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

period = 0


UNDEF = -1
last_idx = [UNDEF] * (m + 1)


ans = 0


def get_start_and_loop(n, x, m):
    first = x
    cur = first
    i = 0
    vals = []
    for i in range(n):
        if last_idx[cur] != UNDEF:
            return last_idx[cur], sum(vals[: last_idx[cur]]), i - last_idx[cur], sum(vals[last_idx[cur]: ]), cur
        last_idx[cur] = i
        vals.append(cur)
        cur = (cur * cur) % m
        i += 1
    return n, sum(vals), 1, 0, 0

start, start_sum, period, period_sum, cur = get_start_and_loop(n, x, m)

ans = start_sum
n -= start
ans += n // period * period_sum
n %= period

for i in range(n):
    ans += cur
    cur = (cur * cur) % m

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
dic = defaultdict(int)
N, X, M = map(int, input().split())
A = [X]
ans = X
fir = -1
if N>1:
    temp = 1
    dic[X]=temp
    for i in range(2, N+1):
        a = A[-1]*A[-1]%M
        if dic[a]>0:
            fir = dic[a]
            break
        A.append(a)
        ans+=a
        temp+=1
        dic[a]=temp
    if fir!=-1:
        T = temp-fir+1#周期
        Tsum = 0 #周期の和
        TempSum = 0 #後半あまりの和
        M=N-fir+1 # 先頭のぞく 
        amari = M%T # 後半あまり
        for k in dic:
            if dic[k]>=fir and dic[k]<=temp:
                Tsum+=k
            if dic[k]>=fir and dic[k]<fir+amari:
                TempSum += k
        ans+=TempSum
        ans+=Tsum*(M//T-1)
    print(ans)
else:
    print(ans)

Submission status: Accepted

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

seen = {}
ans = p%m
seen[p%m]=1
T = {}
T[1] = ans
T[0] = 0
last_p = p%m

r = 0

if n==1:
  print(p%m)
  exit()
else:
  for i in range(2,m+1000):
    p = p ** 2
    p = p % m
    
    if p not in seen:
      seen[p]=i
    else:
      r = i-seen[p]
      last_p = p
      break
    
    ans += p
    T[i] = ans
    
    if i==n:
      print(ans)
      exit()
    
    
temp = T[seen[p]-1]
ans -= temp
n -= seen[p]

k = n//r
ans *= k
ans += temp

n = n % r

if n==0:
  print(ans+last_p)
  exit()

for i in range(1,m+1000):
  p = p ** 2
  p = p % m
  ans += p
  if i==n:
    print(ans+last_p)
    exit()

Submission status: Accepted

Solution code:

value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)

Submission status: Accepted

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

tmp = [0 for i in range(M+2)]
r = [0 for i in range(M)]
tmp[1] = X
r[X] = 1 # A_1 = X
flag = False
for i in range(2, N+1):
  X = (X * X) % M
  #tmp[i] = tmp[i-1] + X
  tmp[i] = X
  if r[X] == 0:
    r[X] = i
  else:
    flag = True
    p = i - r[X]
    #pt = tmp[i] - tmp[r[X]]
    pt = 0
    for j in range(r[X]+1, i+1):
      pt += tmp[j]
    tmp_rX = 0
    for j in range(1, r[X]+1):
      tmp_rX += tmp[j]
    # ans = tmp[r[X]] + pt * ((N - r[X]) // p) + (N - r[X]) % p
    p_r = (N - r[X]) % p
    #T_r = tmp[r[X] + p_r] - tmp[r[X]]
    T_r = 0
    for j in range(1,p_r+1):
      T_r += tmp[ r[X] + j ]
    #ans = tmp[r[X]] + pt * ((N - r[X]) // p) + T_r
    ans = tmp_rX + pt * ((N - r[X]) // p) + T_r
    break
    
if flag:
  print(ans)
else:
  print(sum(tmp))

Submission status: Accepted

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

    idx = [-1] * m

    i = 1
    y = x
    while not(~idx[y]):
        idx[y] = i
        y = (y * y) % m
        i += 1
    start = idx[y]
    end = i

    loop_len = end - start  # [start,end)

    ans = 0
    rep = 0

    rep_flg = False
    finish = False

    j = 1
    while j <= n:
        if finish:
            ans += x
        else:
            if j == start or j == end:
                if rep_flg:
                    k = (n - 1 - j) // loop_len
                    ans += (k + 1) * rep
                    j += k * loop_len
                    rep_flg = False
                    finish = True
                    if j == n:
                        break
                else:
                    rep_flg = True
            if rep_flg:
                rep += x
            else:
                ans += x
        x = (x * x) % m
        j += 1

    if not finish:
        ans += rep
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x,m = map (int,input().split())
next=[0] * (m+1)
memo = [-1] * (m+1)
memo[x] = 0
a = 0
now = x
unti = [x]
flag = True
b = -1
for i in range(m):

    next[now] = (now **2) % m
    #print(1,next)
    if memo[next[now]]!=-1:
        b = memo[next[now]]
        break
    elif next[now] == 0:
        flag =False
        break
    else:
        memo[next[now]] = i+1
    a += 1
    now = next[now]
    unti.append(now)
if flag:
    if b== 0:
        if (n-b)%(a-b+1) !=0:
            print(sum(unti[b:a+1]) * ((n - b) // (a - b + 1)) + sum(unti[b:b+(n - b) % (a - b + 1)]))
        else:
            print(sum(unti[b:a+1]) * ((n - b) // (a - b + 1)))
    else:
        if (n - b) % (a - b + 1) != 0:
            print(sum(unti[b:a+1]) * ((n-b)//(a-b+1)) + sum(unti[b:b+(n-b)%(a-b+1)])  + sum(unti[:b]))
        else:
            print(sum(unti[b:a + 1]) * ((n - b) // (a - b + 1)) + sum(unti[:b]))
else:
    print(sum(unti))

Submission status: Accepted

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

rec = []
s = set()
rec.append(X)
s.add(X)
r = X
idx = -1
idx1 = -1
for i in range(N+1):
    r = (r**2)%M
    if(r not in s):
        rec.append(r)
        s.add(r)
    else:
        rec.append(r)
        idx = i+1
        break
    
for i in range(len(rec)):
    if(rec[i] == rec[idx]):
        idx1 = i
        break

if(idx == -1 or idx1 == -1):
    print(sum(rec[:N]))
elif(idx1 != idx):       
    ans = sum(rec[:idx1])
    ans += sum(rec[idx1:idx])*((N-idx1)//(idx-idx1))+sum(rec[idx1:(idx1+(N-idx1)%(idx-idx1))])
    print(ans)
else:
    ans = sum(rec[:idx1])
    ans += rec[idx]*(N-idx1)
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M
    # if math.gcd(X, M) != 1:
    if False:
        for _ in range(N):
            ans += x
            x *= x
            x %= M
            if x == 0:
                break
        return ans
    else:
        x = X
        s = [X]
        u = set()
        while True:
            x *= x
            x %= M
            s.append(x)
            if x in u:
                break
            u.add(x)

        i = s.index(s[-1])
        if i + 1 >= N:
            return sum(s[:N]) % M

        N -= i
        ans += sum(s[:i])

        s = s[i:]
        s.pop()
        ss = sum(s)
        ans += (N // len(s)) * ss
        ans += sum(s[:N%len(s)])
        return ans


def main():
    N, X, M = read_int_n()
    print(slv(N, X, M))

    # N = 10**10
    # X = random.randint(1, 10**5)
    # M = random.randint(1, 10**5)
    # N, X, M = 10000000000, 82162, 79872
    # print(N, X, M)
    # print(slv(N, X, M))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 0

check = np.zeros(M+1, dtype = int)
suuretu = []

#print(check)

for i in range(N):
    if(check[X] == 1):
        detatoko = suuretu.index(X)
        loop_sum = sum(suuretu[detatoko:])
        loop_kaisu = i - detatoko
#        print(loop_sum, loop_kaisu)

        plus_kaisu = (N - i) // loop_kaisu
        mod_plus = (N - i) % loop_kaisu

#        print(plus_kaisu, mod_plus)
        ans += loop_sum * plus_kaisu
        ans += sum(suuretu[detatoko:detatoko+mod_plus])
        break


    else:
        check[X]  = 1

    ans += X
    suuretu.append(X)

#    if(X == 0):
#        break

#    if(X == 1):
#        ans += N - 1 - i
#        break
    X = (X * X) % M

#print(check)
print(ans)
#print(suuretu)

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
loop = []
loop.append(x)
looplist = [0]*m
looplist[x]=1
for i in range(1,m+1):
    x = x**2%m
    #print(x)
    if looplist[x]==0:
        looplist[x]=1
        loop.append(x)
    else:
        break

ss = loop.index(x)
amari = loop[:ss]
neoloop = loop[ss:]

lon = len(neoloop)

if n<=ss:
    print(sum(amari[:n]))
else:
    print(sum(amari)+(n-ss)//lon*sum(neoloop)+sum(neoloop[:(n-ss)%lon]))

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

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

ls = []
s = set([])

a = X
s.add(a)
ls.append(a)
ind = -1
new_ls = []

while True:
    a = pow(a, 2, M)

    if a in s:
        ind = ls.index(a)
        break
    elif len(ls) == N:
        break
    else:
        s.add(a)
        ls.append(a)

if ind != -1:
    new_ls = ls[ind:len(ls)]

ans = sum(ls)

if len(new_ls) != 0:
    ans += sum(new_ls) * (max(0, (N - len(ls))) // len(new_ls))

    tmp = max(0, (N - len(ls))) % len(new_ls)

    if tmp != 0:
        for i in range(tmp):
            ans += new_ls[i % len(new_ls)]

print(ans)

Submission status: Accepted

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().rstrip()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
# mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

def ceil(a,b):
    return (a+b-1)//b
file=1

def f():
    sys.stdout.flush()





def solve():

    # for _ in range(ii()):
   
    n,x,m = mi()  
    m1 = {}
    m1[x]=0
    a = [x]
    ans = x
    f  = 0
    for i in range(1,n):
        x = (x*x)%m
        if x in m1:
            now = i
            f = 1
            break
        m1[x] = i
        if x==0:
            print(ans)
            exit(0)
        ans += x
        a.append(x)
    if(f == 0):
        print(ans)
        exit(0)

    ans = 0
    for i in range(m1[x]):
        ans += a[i]
    b = []
    cnt = n - m1[x] 
    ans1 = 0
    x1 = cnt//(now-m1[x])
    cnt %= (now-m1[x])
    for i in range(m1[x],len(a)): 
        ans1 += a[i]
    k = m1[x]
    ans += (ans1*x1)
    for i in range(cnt):
        ans += a[k+i]
    print(ans)









        
if __name__ =="__main__":

   
    if path.exists('input.txt'):
        sys.stdin=open('input.txt', 'r')
        sys.stdout=open('output.txt','w')
    else:
        input=sys.stdin.readline
    solve()

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
A = set()
ans = []
a = X
flg = 0
while True:
    k = len(A)
    A.add(a)
    if len(A) == k:
        break
    if a == 0:
        flg =1
        ans.append(a)
        break
    ans.append(a)
    a = a**2%M

g = ans.index(a)
ans_first = ans[:g]
ans = ans[g:]
ans_cum = [ans[0]]
for i in range(len(ans)-1):
    ans_cum.append(ans_cum[i]+ans[i+1])
check = len(ans_cum)
N -= len(ans_first)
if N < 0:
    final = ans_first[:N]
    print(sum(final))
    exit()
loop = N//check
spare = N%check
res = 0
if flg == 0:
    if spare > 0:
        res=loop*ans_cum[-1]+ ans_cum[spare-1]+sum(ans_first)
    else:
        res=loop*ans_cum[-1]+sum(ans_first)
    print(res)
else:
    print(sum(ans_first))

Submission status: Accepted

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

dp = [-1 for _i in range(10**5+2)]
nums = [-1 for _i in range(10**5+2)]
nums[x] = 1

dp[x] = x
bef = x
nex = (x**2)%m
r = [0, x]
while dp[nex] < 0:
    nums[nex] = nums[bef]+1
    dp[nex] = dp[bef]+nex
    r.append(dp[nex])
    nex, bef = (nex**2)%m, nex

if nex == 0:
    print(r[min(len(r)-1, n)])
elif n <= nums[bef]:
    print(r[n])
else:
    roop = nums[bef] - nums[nex] + 1
    roop_value = r[nums[bef]] - r[nums[nex] - 1]
    plus = r[nums[nex]-1]*(n>=nums[nex]+1)
    n = max(0, n-nums[nex]+1)
    print(
        roop_value*(n//roop)+plus+
        r[n%roop + nums[nex] -1]
        -r[nums[nex] - 1]
    )

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, x, m = input_int_list()

    # 方針 循環するため、その循環を見つける。
    # 1.循環を探す
    A = []
    used = set([x])
    A.append(x)
    while True:
        a_next = ((A[-1])**2) % m
        if a_next in used:
            n_loop = a_next
            break
        A.append(a_next)
        used.add(a_next)
    # 2.ループの場所を探す
    start_ptr = A.index(n_loop)
    end_ptr = len(A) - 1
    loop_len = end_ptr - start_ptr + 1
    loop_sum = sum(A[start_ptr:])
    ans = 0
    rem = n - 1
    # 3.ループに入るまで分を足す
    if start_ptr < rem:
        ans += sum(A[:start_ptr])
        rem -= start_ptr
        if rem >= loop_len > 0:
            ans += loop_sum * (rem // loop_len)
        rem = rem % loop_len
        ans += sum(A[start_ptr:start_ptr + rem + 1])
        print(ans)
    else:
        ans = sum(A[:n])
        print(ans)
        return

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def debug():
    A = [x]
    for _ in range(n - 1):
        next_A = pow(A[-1], 2) % m
        A.append(next_A)
    print(sum(A))


def resolve():
    A = [x]
    target = 0
    for _ in range(n - 1):
        next_A = pow(A[-1], 2) % m
        if next_A == 0:
            print(sum(A))
            exit()
        if next_A in A:
            target = next_A
            break
        A.append(next_A)
    else:
        print(sum(A))
        exit()

    idx = A.index(target)
    loop_length = len(A) - idx
    q, r = divmod(n - len(A), loop_length)
    base = sum(A)
    plus = sum(A[idx:]) * q + (sum(A[idx:idx + r]) if r != 0 else 0)
    print(base + plus)


if __name__ == '__main__':
    n, x, m = map(int, input().split())
    resolve()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

def doubling(MAX, A):
    """ ダブリング """

    N = len(A)
    nxt = list2d(MAX, N, -1)
    sm = list2d(MAX, N, 0)
    for i, a in enumerate(A):
        nxt[0][i] = a
        sm[0][i] = a
    for k in range(1, MAX):
        for i in range(N):
            nxt[k][i] = nxt[k-1][nxt[k-1][i]]
            sm[k][i] = sm[k-1][i] + sm[k-1][nxt[k-1][i]]
    return (nxt, sm)

N, X, M = MAP()

MAX = 40
A = [0] * M
for i in range(M):
    A[i] = pow(i, 2, M)
nxt, sm = doubling(MAX, A)

cur = X
ans = X
N -= 1
for k in range(MAX-1, -1, -1):
    if N >> k & 1:
        ans += sm[k][cur]
        cur = nxt[k][cur]
print(ans)

Submission status: Accepted

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

arr = [x]
s = set()
s.add(x)
h = -1
r = 0
for i in range(n - 1):
	val = arr[-1]**2 % m
	if val not in s:
		arr += [arr[-1]**2 % m]
		s.add(arr[-1])
	else:
		h = i
		r = val
		break


res = sum(arr)
if h != -1:
	new_arr = arr[arr.index(r):]
	rest = n - (h + 1)
	c = len(new_arr)
	q = rest // c
	ssum = sum(new_arr) * q
	r = rest % c
	for i in range(r):
		ssum += new_arr[i]
	res += ssum	
	
print(res)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,x,m=LI()
  ans=[x]
  d={x:x}
  y=-inf
  for i in range(n-1):
    x=x*x%m
    if x in d:
      y=x
      break
    d[x]=x
    ans.append(x)

  if y==-inf:
    return sum(ans)

  # print(ans)

  for i,x in enumerate(ans):
    if x==y:
      break

  sm=sum(ans)
  n-=len(ans)
  ans2=ans[i:]
  sm+=n//len(ans2)*sum(ans2)

  n%=len(ans2)
  for i in range(i,i+n):
    sm+=ans[i]

  return sm

# main()
print(main())

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mod_value = [-1 for i in range(2*m)] #余りの値を頭から格納
mod_check = [False for i in range(m)] #余りが現れたか否か
value = x
i = 0
head = 0
while i < n:
    if not mod_check[value]:
        mod_value[i] = value
        mod_check[value] = True
        i += 1
        value = (value**2)%m
    else:
        head = mod_value.index(value)
        break
if i == n:
    print(sum(mod_value[:n]))
else:
    block_size = i - head
    block_num = (n-head)//block_size
    print(sum(mod_value[:head]) + sum(mod_value[head:i])*block_num + sum(mod_value[head:head+(n-head)%block_size]))

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
s = set([x])
t = [x]
p = 1
for i in range(n):
    x = x * x % m
    if x in s:
        break
    else:
        s.add(x)
        t.append(x)
    p += 1
if p == n:
    print(sum(s))
    exit()

q = t.index(x)
l = p - q
b = sum(t[q:p])
ans = sum(t[:q])
n -= q
ans += n // l * b + sum(t[q:q + n % l])
print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
a=set()
b=[x]
for i in range(m):
  x=pow(x,2,m)
  if x in a:break
  a.add(x)
  b+=[x]
j=b.index(x)
n-=j
c=b[j:]
ans=sum(b[:j])+sum(c)*(n//len(c))+sum(c[:n%len(c)])
print(ans)

Submission status: Accepted

Solution code:

import sys
from sys import stdin

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

db = [ [0] * 40 for i in range(mod) ]
s = [ [0] * 40 for i in range(mod) ]

for i in range(mod):

    db[i][0] = i*i%mod
    s[i][0] = i


for j in range(1,40):
    for i in range(mod):

        db[i][j] = db[db[i][j-1]][j-1]
        s[i][j] = s[i][j-1] + s[db[i][j-1]][j-1]

now = X
ans = 0

#print (db[0:10])

for i in range(39,-1,-1):

    #print (now)
    if N & (2**i) > 0:
        ans += s[now][i]
        now = db[now][i]

print (ans)

Submission status: Accepted

Solution code:
N,X,M = list(map(int,input().split()))
L = []
D = {}
L.append(X)
D[X] = D.get(X,0)+1
A = X
flag = 1
for i in range(N-1):
    A = A**2%M
    D[A] = D.get(A,0)+1
    if D[A]==2:
        flag=-1
        break
    else:
        L.append(A)
        if A==0:
            flag=0
            break
if flag==0:
    print(sum(L))
elif flag==1:
    print(sum(L))
else:
    LN = len(L)
    for i in range(LN):
        if L[i]==A:
            break
    Lu = L[i:]
    LuN = len(Lu)
    LuS = sum(Lu)
    out = 0
    if i!=0:
        out += sum(L[:i])
        N = N-i
    if N%LuN==0:
        out += LuS*(N//LuN)
        print(out)
    else:
        out += LuS*(N//LuN)
        amari = N%LuN
        out += sum(Lu[0:amari])
        print(out)

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
array = [0,X]
array2 = [X]
a = X
sum = X
valid = True
while(True):
    a = pow(a,2,M)
    if a in array2:
        y = array2.index(a)
        break
    sum += a
    array.append(sum)
    array2.append(a)
l = len(array2)
h = l - y
if N <= y:
    print(array[N])
else:
    ans = array[y] + (array[-1]-array[y])*((N-y)//h) + array[y+(N-y)%h] - array[y]
    print(ans)

Submission status: Accepted

Solution code:

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

ans_list = [X]
if N == 1:
    print(X)
else:
    for i in range(1,N):
        ans = ans_list[-1]**2%M
        if ans in ans_list:
            break
        else:
            ans_list.append(ans)

    st_index = ans_list.index(ans)

    if st_index == N-1:
        print(sum(ans_list))
    else:
        total = sum(ans_list[:st_index])
        N -= st_index
        syo = N//(i-st_index)
        mod = N%(i-st_index)

        total += sum(ans_list[st_index:])*syo
        total += sum(ans_list[st_index:st_index+mod])
        print(total)

Submission status: Accepted

Solution code:
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n, x, m = getList()

    visited = [-1] * (m+1)
    acc = [-1] * (m+1)
    tmp = x
    tmpsum = 0
    index = 0
    while True:
        # print(tmp)
        if visited[tmp] >= 0:
            cycle = index - visited[tmp]
            issyu = tmpsum - acc[tmp]
            outofcycle = index - 1
            ans = tmpsum
            cyclestart = tmp
            break

        visited[tmp] = index
        acc[tmp] = tmpsum
        tmpsum += tmp
        tmp = (tmp ** 2) % m
        index += 1
        if index == n:
            print(tmpsum)
            return

    # print("cycle ", cycle, issyu, cyclestart, outofcycle, ans)
    ans += ((n - outofcycle - 1) // cycle) * issyu


    tmp = cyclestart
    for i in range((n - outofcycle - 1) % cycle):
        ans += tmp
        tmp = (tmp ** 2) % m

    print(ans)
    # 16243 over




def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*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)]


n, x, m = sp()
arr = [x]
s = set()
while True:
    x = (x * x) % m
    if x in s or x == 0 or x == 1:
        break
    s.add(x)
    arr.append(x)
answer = 0
m = n
if x == 0:
    for i in range(min(m, len(arr))):
        answer += arr[i]
    out(answer)
    exit()
if x == 1:
    for i in range(min(m, len(arr))):
        answer += arr[i]
    out(answer + max(0, m - len(arr)))
    exit()
find = arr.index(x)
if m <= len(arr):
    out(sum(arr[:m]))
    exit()
answer = sum(arr)
m -= len(arr)
arr = arr[find:]
for i in range(m % len(arr)):
    answer += arr[i]
s = sum(arr)
answer += s * (m // len(arr))
out(answer)

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
O = [0]*M

XX = X

ans = 0
a = 1
while a <= N:
    if O[X] == 0:
        O[X] = a
    else:
        b = O[X]
        c = a - b
        d = N - (N - b) % c 
        e = N - d
        h = ((N - b) // c)
        #print(*O)
        #print(b,c,d,e,h)
        ans = 0
        X = XX
        for i in range(b):
            ans += X
            X = (X * X) % M
        for i in range(c):
            if i < e:
                ans += (h + 1) * X
            else:
                ans += h * X
            X = (X * X) % M
        print(ans)
        exit()
    ans += X
    X = (X * X) % M
    a += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # N = int(input())
    N, X, M = [int(a) for a in input().split()]
    # D = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]

    h = {X: 0}

    totals = [X]

    t = X

    c = X
    counter = 0
    while True:
        c = (c * c) % M
        if c in h:
            counter += 1
            t += c
            last_index = h[c]
            diff = t - totals[last_index]
            width = counter - last_index
            amari = last_index
            break
        counter += 1
        h[c] = counter
        t += c
        totals.append(t)

    if N <= amari:
        print(totals[N - 1])
        return

    N -= amari + 1
    rep = N // width
    mod = N % width

    k = totals[amari + mod]

    T = rep * diff + k
    print(T)


if __name__ == "__main__":
    main()