Problem:


Score : 500 points

Problem Statement

Let us denote by f(x, m) the remainder of the Euclidean division of x by m.

Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M).
Find \displaystyle{\sum_{i=1}^N A_i}.

Constraints

1 \leq N \leq 10^{10}

0 \leq X < M \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X M

Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Sample Input 1

6 2 1001

Sample Output 1

1369

The sequence A begins 2,4,16,256,471,620,\ldots Therefore, the answer is 2+4+16+256+471+620=1369.

Sample Input 2

1000 2 16

Sample Output 2

6

The sequence A begins 2,4,0,0,\ldots Therefore, the answer is 6.

Sample Input 3

10000000000 10 99959

Sample Output 3

492443256176507



Sample input:
6 2 1001


Sample output:
1369

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def loop():
    xs = [3, 1, 2, 1]
    ret = []
    N = 6
    visited = [0] * 100
    for i, a in enumerate(xs):
        if visited[a]:
            debug("ret", ret)
            debug("visited", visited)
            s = sum(ret)
            loop_start = visited[a] - 1
            debug("a, visited[a], i", a, visited[a], i)
            loop_end = i
            loop_sum = sum(ret[loop_start:loop_end])
            debug("loop_sum", loop_sum)
            loop_length = loop_end - loop_start
            loop_count = (N - i) // loop_length
            debug("loop_count", loop_count)
            debug("(N - i) % loop_length", (N - i) % loop_length)
            loop_left = (N - i) % loop_length
            loop_tail = sum(ret[loop_start:loop_start + loop_left])
            debug("loop_tail", loop_tail)
            return s + (N - i) // loop_length * loop_sum + loop_tail
        ret.append(a)
        visited[a] = (i + 1)


def solve(N, X, M):
    visited = [0] * M
    a = X
    ret = []
    for i in range(N):
        if visited[a]:
            # debug("ret", ret)
            s = sum(ret)
            loop_start = visited[a] - 1
            # debug("a, visited[a], i", a, visited[a], i)
            loop_end = i
            loop_sum = sum(ret[loop_start:loop_end])
            # debug("loop_sum", loop_sum)
            loop_length = loop_end - loop_start
            loop_count = (N - i) // loop_length
            # debug("loop_count", loop_count)
            # debug("(N - i) % loop_length", (N - i) % loop_length)
            loop_left = (N - i) % loop_length
            loop_tail = sum(ret[loop_start:loop_start + loop_left])
            # debug("loop_tail", loop_tail)
            return s + loop_count * loop_sum + loop_tail
        ret.append(a)
        visited[a] = (i + 1)
        a = (a * a) % M

    return sum(ret)


def main():
    # parse input
    N, X, M = map(int, input().split())
    print(solve(N, X, M))


# tests
T1 = """
6 2 1001
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1369
"""

T2 = """
1000 2 16
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
6
"""

T3 = """
10000000000 10 99959
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
492443256176507
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

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

a = X
S = [0, a]
lasts = [None] * (10 ** 5)
for i in range(1, N):
    a = (a * a) % M
    if a == 0:
        break
    if lasts[a] is not None:
        LA = lasts[a]
        T = i - LA
        print(S[-1] + (S[-1]-S[-T-1])*((N-i)//T) + S[-T-1+(N-i)%T] - S[-T-1])
        exit()
    S.append(S[-1] + a)
    lasts[a] = i

print(S[-1])

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
l=[X]
p=[-1]*(M+1)
p[X]=0
x=0
for i in range(N-1):
    x=(l[-1]**2)%M
    if p[x]>=0:
        break
    l.append(x)
    p[x]=i+1
x=p[x]
y=len(l)-x
print(sum(l[:x])+(N-x)//y*sum(l[x:])+sum(l[x:x+(N-x)%y]))

Submission status: Accepted

Solution code:
N, X, M = map(int,input().split())
i = X % M
L = [i]
S = set([i])
i = i ** 2 % M
while not i in S:
    L.append(i)
    S.add(i)
    i = i ** 2 % M
index = L.index(i)
k = (N - index) // len(L[index:])
l = (N - index) % len(L[index:])

ans = sum(L[:index]) + (k * sum(L[index:]) + sum(L[index:index + l]))
print(ans)

Submission status: Accepted

Solution code:
N,X,MOD = map(int,input().split())
L = [X%MOD]
S = set(L)
for i in range(1000000):
  X = pow(X,2,MOD)
  if X not in S:
    L.append(X)
    S.add(X)
  else:
    loop = X
    break
ans = 0
#print(L,loop)
k = len(L)
if k >= N: #ループよりもNが短い
  for i in range(N):
    ans += L[i]
  print(ans);exit()
for i in range(k):
  if L[i] != loop:
    ans += L[i]
    if i+1 == N:
      print(ans);exit()
  else: #ループに戻ってきた
    #print(i)
    loop_syuki = k-i
    saisyo = i
    loop_kosu = (N-saisyo)//loop_syuki
    amari = (N-saisyo)%loop_syuki
    nokori = loop_kosu*sum(L[saisyo:]) + sum(L[saisyo:saisyo+amari])
    ans += nokori
    #print(loop_syuki,saisyo,amari)
    print(ans);exit()

Submission status: Accepted

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

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

F=(N-1).bit_length()

A=[[0]*M for _ in range(F)]

for x in range(M):
    A[0][x]=(x*x)%M

for d in range(1,F):
    for x in range(M):
        A[d][x]=A[d-1][A[d-1][x]]

S=[[0]*M for _ in range(F)]
for x in range(M):
    S[0][x]=A[0][x]

for d in range(1,F):
    for x in range(M):
        S[d][x]=S[d-1][x]+S[d-1][A[d-1][x]]

Ans=0
depth=0
N-=1
Y=X
while N>0:
    if N%2:
        Ans+=S[depth][X]
        X=A[depth][X]
    depth+=1
    N>>=1
print(Ans+Y)

Submission status: Accepted

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

Submission status: Accepted

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

    sum_a = x
    rem = [None] * m
    n -= 1
    rem[x] = (x, n)
    while n > 0:
        x = x * x % m
        sum_a += x
        n -= 1
        if rem[x] is None:
            rem[x] = (sum_a, n)
        else:
            unit = rem[x][1] - n
            unit_sum = sum_a - rem[x][0]
            ans = sum_a + (n // unit) * unit_sum
            n = n % unit
            while n > 0:
                x = x * x % m
                ans += x
                n -= 1
            print(ans)
            exit()


    print(sum_a)

main()

Submission status: Accepted

Solution code:
def resolve():
    N, X, M = map(int, input().split())
    x = X
    mod = [x]
    while x**2 % M not in mod:
        mod.append(x**2%M)
        x = x**2%M

    ans = 0
    if N <= len(mod):
        for i in range(N):
            ans += mod[i]
    else:
        if mod[-1] == 1:
            ans = sum(mod) + N-len(mod)
        elif mod[-1] == 0:
            ans = sum(mod)
        else:
            first = mod.index(mod[-1]**2%M)
            head = mod[:first]
            loop = mod[first:]

            mo = (N-first)%len(loop)
            div = (N-first)//len(loop)
            ans += sum(head)+ div*sum(loop)
            for i in range(mo):
                ans += loop[i]
    print(ans)
resolve()

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
T = []
K = [0]*M
p = X
for i in range(N):
    if K[p] == 1:
        break
    else:
        T.append(p)
    K[p] = 1
    p *= p
    p %= M

for i in range(N):
    if T[i] == p:
        break
ans = 0
ans += sum(T)
if N > len(T):
    L = sum(T[i:])
    q = len(T[i:])
    ans += L*((N-len(T))//q)
    ans += sum(T[i:i+(N-len(T)) % q])
print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
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)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,x,m = lr()
a = []
judge = [False for i in range(m)]
tmp = x%m
while judge[tmp-1] == False:
    a.append(tmp)
    judge[tmp-1] = True
    tmp = (tmp*tmp)%m

b = []
c = []
bflag = True
for num in a:
    if bflag:
        if num != tmp:
            b.append(num)
        else:
            c.append(num)
            bflag = False
    else:
        c.append(num)


nb = len(b)
nc = len(c)
ans = 0
if n <= nb:
    ans += sum(b[:n])
else:
    ans += sum(b)
    n-=nb
    t = sum(c)
    ans += (n//nc)*t
    ans += (sum(c[:n%nc]))

print(ans)

Submission status: Accepted

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

now = X
used = [X]
i = 1
T = True
while T:
  if i == N:
    print(sum(used))
    quit()
  else:
    next_ = (now * now) % M
    if next_ in used:
      T = False
    else:
      used.append(next_)
      now = next_
    i += 1  

count = used.index(next_)
ans = sum(used[:count])
#print(ans)
roop = len(used) - count
roop_ans = sum(used[count:])
#print(roop, roop_ans)
index = (N - count) % roop
#print(index)
ans += roop_ans * int((N - count) // roop)
#print(ans)
#if index == 0:
#  index = roop
  
ans += sum(used[count:count + index]) 
  
print(ans)
#print(used)

Submission status: Accepted

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

am=[]

d={}

ch=0

for i in range(m):
  y=x%m
  
  if y==0:
    ch+=1
    break
  if y not in d:
    d[y]=0
    
    am.append(y)
    
    x=y*y
    
  else:
    stop=y
    break
    
if ch>0:
  st=0
  ans=0
  while st<=n-1 and st<=len(am)-1:
    ans+=am[st]
    st+=1
    
  print(ans)

else:
  for i in range(len(am)):
    if am[i]==y:
      now=i
      
  new_am=am[now:]
  s_new=sum(new_am)
  l=len(new_am)
  if n<i:
    print(sum(am[:n]))
    
  else:
    s=sum(am[:now])
    rest=n-now
    x=rest//l
    y=rest%l
    print(s+x*s_new+sum(new_am[:y]))

Submission status: Accepted

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

st = D[X]
loop = A[st:-1]

if N<=st:
    ans = sum(A[:N])
else:
    Nl = N-st
    ans = sum(A[:st]) + sum(loop)*(Nl//len(loop)) + sum(loop[:Nl%len(loop)])
print(ans)

Submission status: Accepted

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

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

a = [x]
end = 0
for i in range(1, n):
    tmp = f(a[i-1], m)
    if tmp in a:
        end = i
        break
    a.append(tmp)
if end == 0:
    print(sum(a[:n]))
    exit()
start = -1
for idx, v in enumerate(a):
    if v == tmp:
        start = idx
# print(end-start)
# print(a, start, end)
length = end - start
set_sum = sum(a[start:end+1])
# print(set_sum)
if n-1 < start:
    print(sum(a[:n]))
    exit()
else:
    ans = sum(a[:start])
    plus = n - start
    num = plus // length
    yozyo = plus % length
    ans += (set_sum*num)
    ans += sum(a[start:start+yozyo])
    print(ans)
    exit()

Submission status: Accepted

Solution code:
N, X, M = list(map(int, input().split()))
loop = []
A_set = set()
# find loop
while not X in A_set:
    loop.append(X)
    A_set.add(X)
    X = (X*X)%M

if loop[-1] == 0:
    print(sum(loop))
else:
    ans = 0

    # ループになる前の部分
    loop_L = loop.index(X)
    ans += sum(loop[0:loop_L])
    N -= loop_L

    # ループ部
    loop = loop[loop_L:]
    loop_size = len(loop)
    loop_S = sum(loop)
    ans += loop_S*(N//loop_size)

    # 端数
    ans += sum(loop[:N%loop_size])

    print(ans)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
d={}
x=X
A=[]
init=0
loop=0
S=[0]
while x not in d:
    d[x]=1
    A.append(x)
    S.append(S[-1]+A[-1])
    x=x*x%M

init=A.index(x)
loop=len(A)-init

if N<=init+loop:
    print(S[N])
else:
    l=(N-init)//loop
    r=(N-init)%loop
    print((S[-1]-S[init])*l+S[init+r])

Submission status: Accepted

Solution code:
from collections import Counter
import sys
import math
from functools import cmp_to_key

sys.setrecursionlimit(10 ** 6)

mod = 1000000007
inf = int(1e18)


def main():
    n, x, m = map(int, input().split())
    s = [0] * int(1e5 + 10)
    dp = [x]
    s[x] = 1
    a = x
    for i in range(int(1e5+10)):
        a = a * a % m
        if s[a]:
            first = dp[:dp.index(a)]
            dp = dp[dp.index(a):]
            break
        else:
            dp.append(a)
            s[a] = 1
    ans = sum(first[:n])
    n -= len(first)
    if n <= 0:
        print(ans)
        return
    cyc = sum(dp)
    if a == 0:
        print(ans + sum(dp[:n]))
        return
    ans += cyc * (n // len(dp))
    for i in range(n % len(dp)):
        ans += dp[i]
    print(ans)


main()

Submission status: Accepted

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

lst=[]
ans=0
gg=0
while True:
    gg+=1
    if x==0:
        print(sum(lst))
        exit()

    elif x in lst:
        break

    else:
        lst.append(x)
        x=(x**2)%mod
    
    if gg==n:
        print(sum(lst))
        exit()


log=[]
for i,v in enumerate(lst):
    if v==x:
        log.append(i)


ans+=sum(lst)
n-=len(lst)

newlst=lst[log[0]:]
ans+=sum(newlst)*(n//len(newlst))
if n%len(newlst)!=0:
  ans+=sum(newlst[:n%len(newlst)])

print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,x,m = ma()
idx = [[] for i in range(m)]
tmp=[]
ans = 0
l=0
r=0
for i in range(m+3):
    x = x%m
    tmp.append(x)
    #print(tmp)
    if idx[x]==[]:
        idx[x].append(i)
    else:
        l = idx[x][0]
        r=i
        break
    ans+=x
    x*=x
    if i==n-1:
        print(ans)
        exit()
#print(l,r)
s =sum(tmp[l:r])
d = r-l
p,q = divmod(n-r,d)
ans+=s*p
for i in range(l,l+q):
    ans+=tmp[i]
print(ans)

Submission status: Accepted

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

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

l=[x]
check=[False]*m
check[x]=True
a=x

while True:
    a=a**2%m
    if check[a]:
        last=a
        break
    l.append(a)
    check[a]=True

for i in range(len(l)):
    if l[i]==last:
        index=i

start=l[0:index]
cycle=l[index:]

if n<len(start):
    ans=sum(start[0:n])
else:
    ans=sum(start)
    cn=(n-len(start))//len(cycle)
    cq=(n-len(start))%len(cycle)
    ans+=sum(cycle)*cn
    ans+=sum(cycle[0:cq])

print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
num = {x}
num2 = [x]
while True:
    temp = num2[-1] ** 2 % m
    if temp in num:
        break
    else:
        num.add(temp)
        num2.append(temp)
temp2 = num2.index(temp)
num3 = num2[:temp2]
num4 = num2[temp2:]
ans = sum(num3) + sum(num4) * ((n - len(num3)) // len(num4)) + sum(num4[:(n - len(num3)) % len(num4)])
print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ans=x
a=[x]
d={}
d[x]=1
if n==1:
  print(ans)
else:
  for i in range(2,n+1):
    tmp=a[-1]**2%m
    if d.get(tmp,0)==0:
      a.append(tmp)
      d[tmp]=1
      ans+=tmp
    else:
      t=a.index(tmp)
      if len(a)-t>=n-i+1:
        ans+=sum(a[t:t+n-i+1])
        break
      else:
        t=a.index(tmp)
        tmp_a=(n-i+1)//(len(a)-t)
        tmp_b=(n-i+1)-(len(a)-t)*tmp_a
        ans+=sum(a[t:])*tmp_a+sum(a[t:t+tmp_b])
        break
  print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, X, M = in_nn()

    num_set = set()
    num_set.add(X)

    nums = [0] * (10**6)
    nums[0] = X

    now = X
    roop = -1
    for i in range(1, N):
        now = (now**2) % M
        if now in num_set:
            start = nums.index(now)
            pre_sum = sum(nums[:start])
            roop = i - start
            roop_sum = sum(nums[start:])
            break
        else:
            nums[i] = now
            num_set.add(now)
    else:
        print(sum(nums))
        exit()

    ans = pre_sum
    N -= start
    ans += roop_sum * (N // roop)

    N -= roop * (N // roop)
    ans += sum(nums[start:start + N])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def f(X, M):
  return X % M

appr = defaultdict(int)
appr[x] = 0
cnt = 0
fs = [x]

ans = x
for i in range(1, n):
  x = f(x ** 2, m)
  fs.append(x)
  if x not in appr:
    appr[x] = i
  else:
    span = i - appr[x]
    start = appr[x]
    end = i - 1
    spanSum = sum([i for i in fs[start:end+1]])
    d, m = divmod(n - i - 1, span)
    ans += spanSum * d + sum([i for i in fs[start:start + m + 1]])
    break
  ans += x

print(ans)

Submission status: Accepted

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

used = [0] * M
a = []

A = X
for i in range(N):
    if used[A] != 0:
        break
    used[A] = 1
    a.append(A)
    A = A * A % M

for i in range(len(a)):
    if a[i] == A:
        break
j = i

if a[-1] != 0:
    result = sum(a[:j])
    a = a[j:]
    l = len(a)
    x = (N - j) // l
    y = (N - j) - x * l
    s = sum(a)
    result += s * x
    result += sum(a[:y])
    print(result)
else:
    s = sum(a)
    print(s)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

s = set([])
v = []
for i in range(m+1):
    s.add(x)
    v.append(x)
    x = pow(x,2,m)
    if x in s:
        break
st = v.index(x)
lp = len(v)-st
lps = sum(v[st:])

k = (n-(st+lp)+(lp-1))//lp
ret = lps * k
n -= lp * k
ret += sum(v[:n])

print(ret)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, X, M = map(int, readline().split())

    a = X
    ans = 0

    A = []
    index = [-1] * M
    n = 0

    while index[a] == -1 and n < N:
        index[a] = n
        A.append(a)
        n += 1
        a = (a * a) % M

    if n == N - 1:
        print(sum(A))
        return

    ans = sum(A[: index[a]])
    rest = N - index[a]
    cycle = sum(A[index[a] : n])
    remainder = sum(A[index[a] : index[a] + rest % (n - index[a])])

    ans += cycle * (rest // (n - index[a])) + remainder
    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, x, m = rli()
    if x == 0:
        print(0)
        return
    if x == 1:
        print(n)
        return
    l = 0
    memo = {}
    a = x
    nums = []
    while a not in memo:
        # print(l, a)
        nums.append(a)
        memo[a] = l
        l += 1
        a = a*a % m
    st = memo[a]
    k = len(nums)
    if n <= k:
        print(sum(nums[:n]))
        return
    su = sum(nums)
    n -= k
    su2 = sum(nums[st:])
    n2 = n//(k-st)
    ans = su
    ans += n2*su2
    n3 = n%(k-st)
    ans += sum(nums[st:st+n3])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
s=x
t={x}
u=[x]
for i in range(1,n):
    x=pow(x,2,m)
    if x==0:break
    if x==1:
        s+=n-i
        break
    if x in t:
        j=u.index(x)
        s=sum(u[:j])
        u=u[j:]
        s+=(n-j)//len(u)*sum(u)
        s+=sum(u[:(n-j)%len(u)])
        break
    s+=x
    t|={x}
    u+=x,
print(s)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    N, X, M = map(int, readline().split())
    rem = N

    if X == 0:
        return print(0)

    seq = [0] * 200001
    seq[1] = X
    visited = set()
    visited.add(X)

    cur = X
    cnt = 1

    while cnt < N:
        cur = cur ** 2 % M
        cnt += 1
        if cur in visited:
            break
        elif cur == 0:
            return print(sum(seq))
        else:
            seq[cnt] = cur
            visited.add(cur)
    else:
        return print(sum(seq))

    first = seq.index(cur)
    l = cnt - first

    rem -= first
    p = rem // l
    q = rem % l

    ans = 0
    ans += sum(seq[:first])
    ans += p * sum(seq[first:])

    rem = q
    i = 0
    while i <= rem:
        x = seq[first + i]
        ans += x
        i += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

d = {}
l = []
for i in range(N):
    if X in d:
        break
    d[X] = i
    l.append(X)
    X = X*X%M
else:
    print(sum(l))
    exit()

s = d[X]

q, r = divmod(N-s,i-s)
ans = sum(l[:s])+q*sum(l[s:i])+sum(l[s:s+r])
print(ans)

Submission status: Accepted

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

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

table = [0]*M
for x in range(M):
    table[x] = x*x%M

if N <= M:
    ans = 0
    x = X
    for _ in range(N):
        ans += x
        x = table[x]
    
else:
    ans = 0
    x = X
    for _ in range(M):
        ans += x
        x = table[x]
    N -= M
    res = 0
    vx = x
    st = []
    for loop in range(1, M+1):
        st.append(x)
        x = table[x]
        if x == vx:
            break
    
    ans += sum(st)*(N//loop) + sum(st[:N%loop])
print(ans)

Submission status: Accepted

Solution code:
def main():
    examE()

def examA():
    S = SI()
    if S[-1]=="s":
        ans = S+"es"
    else:
        ans = S+"s"
    print(ans)
    return

def examB():
    N = I()
    D = [LI()for _ in range(N)]
    current = 0
    for d1,d2 in D:
        if d1==d2:
            current += 1
        else:
            current = 0
        if current==3:
            print("Yes")
            return
    print("No")
    return

def examC():
    N = I()
    cnt = 0
    for i in range(1,N):
        for j in range(1,1+N//i-(N%i==0)):
            cnt += 1
    ans = cnt
    print(ans)
    return

def examD():
    N, K = LI()
    LR = [LI()for _ in range(K)]
    dp = [0]*N
    S = [0]*N
    dp[0] = 1
    S[0] = 1
    for i in range(1,N):
        cur = 0
        for l,r in LR:
            if i<l:
                continue
            cur += S[i-l]
            if i<r+1:
                continue
            cur -= S[i-r-1]
            cur += mod2
            cur %= mod2

        dp[i] = cur
        S[i] = S[i-1] + cur
        S[i] %= mod2

    ans = dp[-1]
    print(ans)
    return

def examE():
    N, X, M = LI()
    cnt = 0
    L = []
    used = [-1]*(M+1)

    for i in range(N):
        used[X] = i
        L.append(X)
        cnt += X
        X = pow(X,2,M)
        if X==1 or X==0:
            cnt += (N-i-1)*X
            break
        if used[X]>=0:
            loop = i - used[X] + 1
            S = sum(L[used[X]:i+1])
            rest = N-i-1
            cnt += (rest//loop) * S + sum(L[used[X]:used[X]+rest%loop])
            break
    #print(L)
    #print(used)
    ans = cnt
    print(ans)
    return
def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
10 4 6 
"""

Submission status: Accepted

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

N,X,M = map(int,readline().split())
route = [X]
dic = {}
first = []
loop = []
for i in range(1, N):
  X = (X ** 2) % M
  if X in dic:
    first = route[:dic[X]]
    loop = route[dic[X]:]
    break
  route.append(X)
  dic[X] = i
  
if len(first) == 0:
  print(sum(route[:N]))
  exit(0)

if N == len(first):
  print(sum(first))
elif N < len(first):
  print(sum(first[:N]))
else:
  ans = sum(first)
  one_loop = sum(loop)
  N -= len(first)
  loop_cnt = N // len(loop)
  rest = N % len(loop)
  ans += loop_cnt * (sum(loop))
  ans += sum(loop[:rest])

  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
# from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
# import math
# from itertools import product, accumulate, combinations, product
# import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def next_val(An, M):
    return (An * An) % M

def run():
    N, X, M = mapline()
    arr = [X]
    valset = {}
    valset[X] = 0
    while True:
        an = arr[-1]
        next_a = next_val(an, M)
        if not next_a in valset.keys():
            arr.append(next_a)
            valset[next_a] = len(arr) - 1
        else:
            break
    idx1 = valset[next_a]
    K = len(arr)
    ans = 0
    if N > idx1:
        ans += sum(arr[:idx1])
    else:
        ans += sum(arr[:N])
        print(ans)
        return

    N -= idx1
    l = K - idx1
    sums = sum(arr[idx1:])
    cycle = N // l
    ans += sums * cycle
    N %= l
    ans += sum(arr[idx1:idx1+N])
    print(ans)






if __name__ == "__main__":
    run()