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 defaultdict
n, x, m = list(map(int, input().split()))
dp = [False]*(m+1)
a = [0]*(m+1)
d = defaultdict(lambda: set())
flag = False
for i in range(1, min(m+1, n+1)):
    if i == 1:
        a[i] = x
        dp[x] = True
    else:
        a[i] = a[i-1]**2 % m
        if not dp[a[i]]:
            d[a[i-1]] = a[i]
            dp[a[i]] = True

        else:
            startv = a[i]
            flag = True

            break
start_idx = a[1:].index(a[i])+1
loop_haba = i-start_idx
loop_sum = sum(a[start_idx:i])
if not flag:
    print(sum(a[:n+1]))
else:
    ans = sum(a[:(start_idx)])

    ans += ((n-start_idx)//loop_haba)*loop_sum
    ans += sum(a[start_idx: start_idx+((n-start_idx) % loop_haba)+1])
    print(ans)

Submission status: Accepted

Solution code:
""" E
    https://atcoder.jp/contests/abc173/tasks/abc173_e
"""
import sys
import math
from functools import reduce

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def main(N, X, M):
    A = X
    m = {A: A}
    i = -1
    for j in range(1, M):
        A = (A * A) % M if M > 0 else 0
        if A in m:
            i = list(m.keys()).index(A)
            break
        else:
            m[A] = A

    if i == -1:
        return sum(m.values())
    else:
        l = list(m.values())
        s1 = sum(l[:i])
        len_repeat = len(l) - i
        s2 = sum(l[i:])

        return s1 + int((N-i)/len_repeat) * s2 + sum(l[i:(N-i)%len_repeat+i])

if __name__ == "__main__":
    _N, _X, _M = readIntegerSet(3)

    print(main(_N, _X, _M))

Submission status: Accepted

Solution code:
n, x, m = (int(x) for x in input().split())
A = [x]
used = {x, }
while True:
    x = pow(x, 2, m)
    if x in used:
        index = A.index(x)
        break
    else:
        A.append(x)
        used.add(x)
if n <= len(A):
    print(sum(A[:n]))
else:
    ans = sum(A)
    n -= len(A)
    m = len(A) - index
    ans += (n // m) * sum(A[index:])
    ans += sum(A[index:index + (n % m)])
    print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
tab=[0 for i in range(10**5+1)]

end=False
now=x
for i in range(1,n+1):
    if tab[now]>0:
        las=tab[now]
        cyc=i-las
        break
    tab[now]=i
    now=now*now%m
else:
    end=True
    
if end:
    ans=0
    for i in range(10**5+1):
        if tab[i]>0:
            ans+=i
    print(ans)
else:
    ans=0
    head=0
    body=0
    foot=0
    lop=(n-las)//cyc
    rem=(n-las)%cyc
    for i in range(10**5+1):
        if tab[i]>=las and las+rem>=tab[i]:
            body+=i
            foot+=i
        elif tab[i]>=las:
            body+=i
        elif tab[i]>0:
            head+=i
    ans=head+body*lop+foot
    print(ans)

Submission status: Accepted

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

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

    def f(x, m):
        return x%m

    # A[i]の値は必ず mod Mの範囲に収まる
    # ということはたかだかMの周期でループする
    # ただし、ループして戻るのはA[0]とは限らず、適当なA[?]に戻る
    # 注意として、A[i]=0になったら、A[i+1]以降は必ず0
    A = [0]*(10**5+2)  # A[i]
    Ar = [0]*(10**5+2)  # Ar[i] := A[i]以下の累積和
    A[0], Ar[0] = X, X
    Adic = {X:0}  # Adic[A[i]]=i => 過去のA[i]はi番目に出現した
    stop_i = 0
    is_zero = False
    for i in range(1, N):
        A[i] = f(pow(A[i-1], 2, M), M)
        Ar[i] = Ar[i-1] + A[i]
        if A[i] == 0:
            is_zero = True
            stop_i = i
            break
        if A[i] in Adic:
            stop_i = i
            break
        Adic[A[i]] = i

    if stop_i == 0:
        print(Ar[N-1])
    elif is_zero:
        print(Ar[stop_i])
    else:
        start_i = Adic[A[stop_i]]
        t = stop_i - start_i
        restN = N - start_i
        if start_i-1 >= 0:
            ans = Ar[start_i-1]
            ans += (Ar[stop_i-1] - Ar[start_i-1]) * (restN//t)
            ans += Ar[start_i-1+(restN%t)] - Ar[start_i-1]
        else:
            ans = Ar[stop_i-1] * (restN//t)
            ans += Ar[start_i-1+(restN%t)]
        print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

def solve(n, x, m):
    if n == 1:
        return x
    arr = [x]
    for i in range(1, n):
        x = x*x % m
        if x in arr:
            rem = n-i
            break
        else:
            arr.append(x)
    else:
        rem = 0
    sa = sum(arr)
    argi = arr.index(x)
    roop = arr[argi:]
    nn, r = divmod(rem, len(roop))
    return sa + nn*sum(roop) + sum(roop[:r])

print(solve(n, x, m))

Submission status: Accepted

Solution code:
# Date [ 2020-09-19 21:46:14 ]
# Problem [ e.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, x, m = read_ints()
    query = []
    s = set([])
    while x not in s:
        s.add(x)
        query.append(x)
        x = x * x % m
    
    frm = query.index(x)
    length = len(query) - frm
    total = sum(query[frm:])
    
    ans = sum(query[:frm]) + total * ((n - frm) // length) + sum(query[frm:frm + (n - frm) % length])
    print(ans)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
A = [X]
A_dict = {X}
a = X
s = X
r = 0
r0 = 0
l = 0
amari = 0

for i in range(M+1):
  a = a ** 2 % M
  if a in A_dict:
    r0 = A.index(a)
    l = len(A[r0:])
    r = (N - i - 1) // l
    amari = (N - i - 1) % l
    s = s + sum(A[r0:])*r + sum(A[r0:r0+amari])
    break
  A.append(a)
  A_dict.add(a)
  s += A[-1]

print(s)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from sys import exit

import sys
sys.setrecursionlimit(1000000000)
mod = 998244353

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

N, X, M = getNM()
# 一つしかないなら二度と出ない
lista = [[-1, -1] for i in range(M)]

n = X
for i in range(2 * M + 1):
    if lista[n][0] == -1:
        lista[n][0] = i
    elif lista[n][1] == -1:
        lista[n][1] = i
    n *= n
    n %= M

cnt = 0
for i in range(M):
    s, e = lista[i]
    # ループする
    if s >= 0 and e >= 0:
        cnt += i * (((N - 1) - s) // (e - s) + 1)
    # 1回きり
    elif s >= 0:
        cnt += i
print(cnt)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
a=[]
mod_check_list = [False for _ in range(m)]
a.append(x*x%m)
ind=0
s=0
for i in range(m):
    t=a[i]*a[i]%m
    if mod_check_list[t]:
        ind=a.index(t)
        break
    mod_check_list[t] = True
    a.append(t)
s=sum(a[ind:])
l=len(a)-ind
loop_times = (n-1-ind)//l
answer=loop_times*s
for i in range((n-1-ind)%l):
    answer+=a[i+ind]
print(answer+x+sum(a[:ind]))

Submission status: Accepted

Solution code:
"""
何回足されるかで考えればよい。
真っ二つに切っていく。

各項は必ずM未満。
M項以内に必ずループが現れる。
"""
N,X,M = map(int,input().split())
memo1 = set()
memo2 = []
ans = 0
a = X
flag = True
rest = N
while rest > 0:
    if a in memo1 and flag:
        flag = False
        for i in range(len(memo2)):
            if memo2[i] == a:
                loopStart = i
        setSum = 0
        for i in range(loopStart,len(memo2)):
            setSum += memo2[i]**2 % M
        loopStep = len(memo2)-loopStart
        loopCount = rest // loopStep
        ans += loopCount*setSum
        rest -= loopCount*loopStep
    else:
        memo1.add(a)
        memo2.append(a)
        ans += a
        a = a**2%M
        rest -= 1

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy


def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)
class ModInt:
    def __init__(self, x, MOD=1000000007): self.x, self.MOD = x % MOD, MOD
    def __str__(self): return str(self.x)
    def __add__(self, other): return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)
    def __sub__(self, other): return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)
    def __mul__(self, other): return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)
    def __truediv__(self, other): return ModInt(self.x * other.inverse()) if isinstance(other, ModInt) else ModInt(self.x * pow(other, self.MOD - 2, self.MOD))
    def __pow__(self, other): return ModInt(pow(self.x, other.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, self.MOD))
    def __rsub__(self, other): return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)
    def __rtruediv__(self, other): return ModInt(other.x * other.inverse()) if isinstance(other, ModInt) else ModInt(other * pow(self.x, self.MOD - 2, self.MOD))
    def __rpow__(self, other): return ModInt(pow(other.x, self.x, self.MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, self.MOD))
    __repr__, __radd__, __rmul__ = __str__, __add__, __mul__
    def inverse(self): return pow(self.x, self.MOD - 2, self.MOD)

def main():
    N, X, M = LI()
    tmp = X
    s = set()
    while True:
        if tmp in s: break
        s.add(tmp)
        tmp = (tmp * tmp) % M

    f = len(s)
    s = set()

    while True:
        if tmp in s: break
        s.add(tmp)
        tmp = (tmp * tmp) % M

    mid = len(s)
    summid = sum(s)
    rest = (N - f + mid) % mid
    cnt = (N - f + mid) // mid

    first = f - mid
    tmp = X
    s = set()
    for _ in range(first):
        s.add(tmp)
        tmp = (tmp * tmp) % M
    first_res = sum(s)

    s = set()
    for _ in range(rest):
        s.add(tmp)
        tmp = (tmp * tmp) % M
    last_res = sum(s)

    print(first_res+ summid*cnt+ last_res)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

count = 0

# table2jou = []
# for mi in range(m + 1):
#     table2jou.append(pow(mi, 2))

# tablef = []
# for mi in range(m + 1):
#     # tablef.append(table2jou[mi] % m)
#     tablef.append(pow(mi, 2, m))

is_used = [0] * (m + 1)

count = x
pre_an = x
his = [x]
for ni in range(2, n + 1):
    # an = tablef[pre_an]
    an = pow(pre_an, 2, m)
    if is_used[an] == 1:
        leftnum = n - ni + 1
        start = his.index(an)
        end = leftnum % (len(his) - start) + start
        loopnum = leftnum // (len(his) - start)
        count = count + sum(his[start: end])
        count = count + sum(his[start:]) * loopnum
        break
    his.append(an)
    is_used[an] = 1
    count = count + an
    pre_an = an

print(count)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools
def main():
    N, X, M = MI()
    circle = [X]
    ans = 0
    i = 1
    num_list = [0] * (M + 1)
    a = X
    while num_list[a] == 0:
        num_list[a] = i
        a = pow(a, 2, M)
        circle.append(a)
        i += 1
    b = num_list[a]
    del circle[-1]
    sta = circle[:b - 1]
    v = len(sta)
    w = sum(sta)
    circle = circle[b - 1:]
    x = len(circle)
    y = sum(circle)
    if N <= v:
        ans = sum(sta[:N + 1])
        print(ans)
        exit()
    else:
        ans = w
        p, q = divmod(N - v, x)
        ans += y * p
        if q != 0:
            for i in range(q):
                ans += circle[i]

        print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
flag = [0]*(10**5 + 2)
lst = [X]

for i in range(N):
    X = (X**2)%M

    if flag[X] == 1:
        break

    flag[X] = 1
    lst.append(X)

preindex = lst.index(X)

preloop = lst[:preindex]
loop = lst[preindex:]

loopnum = (N - len(preloop))//len(loop)
loopafternum = (N - len(preloop))%len(loop)

ans = sum(preloop) + sum(loop)*loopnum + sum(loop[:loopafternum])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)


def li():
    return [int(x) for x in input().split()]


N, X, MOD = li()


n = X
nums = [X]
loop_start_i = -INF
for i in range(1, N):
    n = pow(n, 2, MOD)
    if n in nums:
        loop_start_i = nums.index(n)
        break
    nums.append(n)
# total %= MOD
loop_length = len(nums) - loop_start_i
loop_cnt = (N - loop_start_i) // loop_length
r = (N - loop_start_i) % loop_length
sum_per_loop = sum(nums[loop_start_i:])
ans = sum(nums[:loop_start_i]) + sum_per_loop * loop_cnt + sum(nums[loop_start_i:loop_start_i+r])
print(ans)

Submission status: Accepted

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

mod_check_list = [False for _ in range(M)]
mod_list = [(X ** 2) % M]
counter = 1
mod_sum = (X ** 2) % M
last_mod = 0
for i in range(M):
    now_mod = (mod_list[-1] ** 2) % M
    if mod_check_list[now_mod]:
        last_mod = now_mod
        break
    mod_check_list[now_mod] = True
    mod_list.append(now_mod)
    counter += 1
    mod_sum += now_mod

loop_start_idx = 0
for i in range(counter):
    if last_mod == mod_list[i]:
        loop_start_idx = i
        break

loop_list = mod_list[loop_start_idx:]
loop_num = counter - loop_start_idx
ans = 0
if (N - 1) <= counter:
    ans = X + sum(mod_list[:N - 1])
else:
    ans += X + mod_sum
    N -= (counter + 1)
    ans += sum(loop_list) * (N // loop_num) + sum(loop_list[:N % loop_num])

print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
ans = 0
prev_set = set()
prev_list = list()
ans_hist = list()
r = x

for i in range(n):
    if i == 0:
        pass
    else:
        r = (r * r) % m
    
    if r == 0:
        break
    
    if r in prev_set:
        index = prev_list.index(r)
        period = i - index
        count = (n - index) // period
        rest = (n - index) % period

        ans = sum(prev_list[:index])
        ans += sum(prev_list[index:i]) * count
        # ans += (ans - ans_hist[index - 1]) * (count - 1)

        ans += sum(prev_list[index:index+rest])
        # ans += (ans_hist[index + rest - 1] - ans_hist[index - 1])
        break
    else:
        ans += r
        prev_set.add(r)
        prev_list.append(r)
        ans_hist.append(ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################
 
def floor(a,b):
    return a//b

N,X,M = LI()

# 繰り返しの1回目が終わるまで
used = [-1]*M
end_index = -1
A = [X]
sum_ = 0
for i in range(N):
    if i == 0:
        sum_ += A[0]
    else:
        val = pow(A[i-1],2,M)
        A.append(val)
        if used[val] == -1:
            used[val] = i
            sum_ += val
        else:
            end_index = i
            start_val = val
            start_index = used[val]
            break

if end_index == -1:
    print(sum_)
    exit()
else:
    ans = sum_


# 繰り返し全体が終わるまで
n = floor(N-start_index,end_index-start_index)
sum_ = 0
A2 = [start_val]
for j in range(end_index-start_index):
    if j == 0:
        val2 = start_val
        sum_ += val2
    else:
        val2 = pow(A2[j-1],2,M)
        A2.append(val2)
        sum_ += val2

ans += (n-1)*sum_


# 残りの部分
sum_ = 0
A2 = [start_val]
for j in range(N-n*end_index+(n-1)*start_index):
    if j == 0:
        val2 = start_val
        sum_ += val2
    else:
        val2 = pow(A2[j-1],2,M)
        A2.append(val2)
        sum_ += val2

ans += sum_

print(ans)

Submission status: Accepted

Solution code:
n, x, m =  map(int, input().split())
ans = 0
loop_list = [0] * m
loop_list[x] = 1
order_list = [x]

for i in range(1, m + 1):
    x = pow(x, 2, m)
    if loop_list[x] != 1:
        loop_list[x] = 1
        order_list.append(x)
    else:
        break

index = order_list.index(x)
time = (n - index) // (len(order_list) - index)
mod = (n - index) % (len(order_list) - index)

ans += sum(order_list[:index])
ans += sum(order_list[index:]) * time
ans += sum(order_list[index:index + mod])

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

    if N == 1:
        print(X)
        return

    A = X
    steps = [0] * M
    sms = [0] * M
    steps[A] = 1
    sms[A] = A
    sm = A
    ans = A
    rest = 0
    for i in range(2, N+1):
        A = (A*A) % M
        sm += A
        ans += A
        if steps[A] != 0:
            P = i - steps[A]
            v = sm - sms[A]
            rest = N - i
            ans += v * (rest//P)
            rest %= P
            break
        steps[A] = i
        sms[A] = sm

    for i in range(rest):
        A = (A*A) % M
        ans += A

    print(ans)


solve()

Submission status: Accepted

Solution code:
def f(x, m):
    return (x**2) % m

N, X, M = map(int, input().split())
A = [X]
S = {X}
while True:
    X = f(X, M)
    if X in S:
        break
    else:
        A.append(X)
        S.add(X)


start = A.index(X)
l = len(A) - start
ans = sum(A[:start])
N -= start

ans += sum(A[start:]) * (N//l)
N %= l

ans += sum(A[start:start+N])
print(ans)

Submission status: Accepted

Solution code:
import sys
import math


def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,X,M = MI()

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

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

z = len(Z)
ans = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

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

    A = []
    seen = set()
    tmp = X
    head_idx = -1
    while True:
        A.append(tmp)
        seen.add(tmp)
        tmp = pow(tmp, 2, M)
        if tmp in seen:
            head_idx = A.index(tmp)
            break
    # print(A, head_idx)

    cnt = [0] * len(A)
    for i in range(len(A)):
        if i < head_idx:
            if i <= N:
                cnt[i] = 1
        else:
            l = len(A) - head_idx
            cnt[i] = (N - head_idx) // l
    for i in range(head_idx, head_idx + (N - head_idx) % l):
        cnt[i] += 1
    # print(cnt)

    ans = sum([a * c for a, c in zip(A, cnt)])
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,x,m=map(int,input().split())
s=[x]
g=set()
cnt=0
l=-1
g.add(x)
b=x
for i in range(1,n):
    nt=pow(b,2,m)
    b=nt
    if nt not in g:
        s.append(nt)
        g.add(nt)
    else:
        cnt=i
        l=nt
        break
if l==0:
    #s=list(s)
    ans=sum(s)
elif l==1:
    #s=list(s)
    ans=n-cnt+sum(s)
else:
    if l!=-1:
      idx=s.index(l)
      c=len(s)-idx
      r=(n-cnt)%c
      ans=((n-cnt)//c)*sum(s[idx:])+sum(s[idx:idx+r])+sum(s)
    else:
      ans=sum(s)
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
A = [0]*(M+1)
A[0] = X
ls, rs = 0, 0
m = [-1]*(M+1)
m[X] = 0
for i in range(1, M+1):
    A[i] = (A[i-1]*A[i-1]) % M
    if m[A[i]] >= 0:
        ls = m[A[i]]
        rs = i
        break
    m[A[i]] = i

if rs == 0:
    print(sum(A[:N]))
else:
    if ls > N:
        print(sum(A[:N]))
    else:
        ans = sum(A[:ls])
        N -= ls
        w = rs-ls
        ans += sum(A[ls:rs])*(N//w)
        ans += sum(A[ls:ls+N % w])
        print(ans)

Submission status: Accepted

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

amari = [0]*m
v = [x]

cnt = 0
while True:
    xn_1 = x**2%m
    cnt += 1
    if x == 0:
        break
    amari[x] = xn_1
    if amari[xn_1]:
        break
    v.append(xn_1)
    x = xn_1

#print(v)

if 0 in v:
    ans = sum(v)
else:
    ind = v.index(xn_1)
    rooplen = len(v) - ind
    ans = sum(v[0:ind])
    l = n-ind
    if rooplen:
        ans += (l//rooplen)*sum(v[ind:])
        nokori = l - rooplen*(l//rooplen)
        ans += sum(v[ind:ind+nokori])
    
#print(v)
print(ans)

Submission status: Accepted

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

import sys
input=sys.stdin.readline

n,x,m=map(int,input().split())
values=[]
s=set()
loop_start=-1
for i in range(n):
    if x in s:
        loop_start=values.index(x)
        break
    values.append(x)
    s.add(x)
    x=(x*x)%m
if loop_start==-1:
    ans=sum(values)
    print(ans)
    exit()
else:
    ans=sum(values[:loop_start])
    loops=values[loop_start:]
    loops_sum=sum(loops)
    n-=loop_start
    l=len(loops)
    ans+=n//l*loops_sum+sum(loops[:n%l])
    print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n,x,m = readInts()
lis = []
prv = None
dic = defaultdict(int)
for i in range(m):
    if i == 0:
        A = x%m
        lis.append(A)
        dic[A] = 1
    else:
        A = (A*A)%m
        if dic[A]:
            prv = A
            break
        else:
            dic[A] = 1
        lis.append(A)
cnt = None
for i in range(len(lis)):
    if lis[i] == prv:
        cnt = i
        break
if cnt == None:
    cnt = len(lis)
front_arr = lis[:cnt]
loop_arr = lis[cnt:]
if x == 0:
    print(0)
    exit()
len_loop_arr = len(loop_arr)
if n < cnt:
    ans = sum(front_arr[:n])
else:
    ans = sum(front_arr)
    sum_loop_arr = sum(loop_arr)
    n -= cnt

    loop = n//len_loop_arr
    rest = n - (loop*len_loop_arr)
    mid = loop * sum_loop_arr
    ans += mid
    ans += sum(loop_arr[:rest])
print(ans)

Submission status: Accepted

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

lst, num = set(), []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        break

ans = sum(num)
if x in lst:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)

Submission status: Accepted

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

lst, num, flag = set(), [], False
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        flag = True
        break

ans = sum(num)
if flag:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)

Submission status: Accepted

Solution code:
import sys
n, x, m = map(int, input().split())
mod_cnt = [False for _ in range(m)]
mod_cnt[x] = True
cycle = [x]
while len(cycle) < n and not mod_cnt[(x*x) % m]:
	x = (x*x) % m
	mod_cnt[x] = True
	cycle.append(x)

if len(cycle) == n:
	print(sum(cycle))
	sys.exit()

nxt = (x*x) % m
for i in range(len(cycle)):
	if cycle[i] == nxt:
		head = i
		break

ans = sum(cycle[:head])
cycle = cycle[head:]
period = len(cycle)
n -= head
for i, x in enumerate(cycle):
	if i < n % period:
		ans += (n // period + 1) * x
	else:
		ans += (n // period) * x
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int,input().split())
lst = [0 for i in range(m)]
lst2 = [x]
i = 2
lst[x] = 1
c = 0
while True:
    if (i > n):
        break
    x = x**2%m
    if (lst[x] == 0):
        lst[x] = i
        lst2.append(lst2[i - 2] + x)
        i = i + 1
    else:
        lst2.append(lst2[i - 2] + x)
        c = 1
        break
if (c == 1):
    a = i - lst[x]
    b = lst2[i - 1] - lst2[i - 1 - a]

    c = (n - i)//a
    d = (n - i)%a
    ans = lst2[i - 1] + b*c + lst2[i - 1 - a + d] - lst2[i - 1 - a]
    print(ans)

else:
    print(lst2[n - 1])

Submission status: Accepted

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

v = list(range(m))
p = [-1 for _ in range(m)]

a = x
p[a - 1] = 0
s = [x]
l, r = n, n
for i in range(n):
    a = a ** 2 % m
    if p[a - 1] >= 0:
        l, r = p[a - 1], i + 1
        break
    else:
        s.append(a)
        p[a - 1] = i + 1
ans = sum(s[:l])
if l != r:
    b = (n - 1 - i) // (r - l) + 1
    c = (n - 1 - i) % (r - l)
    ans += b * sum(s[l:r]) + sum(s[l:l + c])
print(ans)

Submission status: Accepted

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

lst_sum = [0,x]
loop = [0]*(10**5)
loop[x] = 1
s = 1
for i in range(2,n+1):
  y = ((lst_sum[-1] - lst_sum[-2])**2)%m
                          
  if loop[y] != 0:
    l = i-loop[y]
    d = (n-loop[y]+1) // l
    q = (n-loop[y]+1) % l
    sum_loop = lst_sum[-1]-lst_sum[loop[y]-1]
    sum_first = lst_sum[loop[y]-1]
    if q == 0:
      sum_rest = 0
    else:
      sum_rest = lst_sum[loop[y] + q-1] - lst_sum[loop[y]-1]
    print(sum_first+d*sum_loop+sum_rest)
    sys.exit()      
  else:
    s += 1
    loop[y] = s
    lst_sum.append(lst_sum[-1] + y)
    
print(lst_sum[-1])

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, x, m = map(int, input().split())
    ans = 0

    # pigeon hole principle
    index = [-1] * m
    now = x
    i = 0
    while index[now] == -1:
        index[now] = i
        i += 1
        ans += now
        now = now * now % m
        n -= 1
        if n == 0:
            print(ans)
            return

    l = i - index[now]
    cycle = 0
    for _ in range(l):
        cycle += now
        now = now * now % m

    q, r = divmod(n, l)
    ans += q * cycle

    for _ in range(r):
        ans += now
        now = now * now % m

    print(ans)
resolve()