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:
def main():
    n,x,m=map(int,input().split())
    A=[]
    s=set()
    while True:
        A.append(x)
        s.add(x)
        x**=2
        x%=m
        if x==0:
            A.append(0)
            break
        if x in s:
            break
    #print(A)
    if n<=len(A):
        return sum(A[:n])
    if A[-1]==0:
        return sum(A)
    for idx,a in enumerate(A):
        if a==x:
            break
    l=len(A)-idx
    cycles=(n-idx)//l
    remain=(n-idx)%l
    #print(idx,l,cycles)
    s=sum(A[idx:])
    ans=sum(A[:idx])
    ans+=s*cycles
    ans+=sum(A[idx:idx+remain])
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, x, m = MI()
    a = x
    flag = [False]*(m+1)
    t = 0
    s = []
    idx = 0
    for _ in range(m+1):
        if flag[a]:
            idx = s.index(a)
            break
        flag[a] = True
        s.append(a)
        t += a
        a = (a*a) % m
        if a == 0:
            print(t)
            sys.exit()
    ans = sum(s[0:idx])
    ans += sum(s[idx:])*((n-idx)//(len(s)-idx))
    ans += sum(s[idx:idx+(n-idx)%(len(s)-idx)])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, sX, mod = mapint()

X = sX
s = set()
s.add(X)
s_loop = set()
ans = X
loop = 0
loops = []
i = -1
for i in range(min(10**5*2+10, N-1)):
    X = pow(X, 2, mod)
    if X in s:
        if X in s_loop:
            loops.append(X)
            break
        loop += X
        s_loop.add(X)
        loops.append(X)
    s.add(X)
    ans += X

rest = N-i-2
if rest:
    ans += (rest//len(s_loop))*loop
    amari = rest%len(s_loop)+1
    for i in range(amari):
        ans += loops[i]
    print(ans)
else:
    print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
def am(a, b):
    return (a * a) % b
l = [x]
u = []
now = x
for i in range(n):
    s = am(now, m)
    if(s in l):
        break
    l.append(s)
    now = s
c = l.index(s)
k = 0
if(0 in l):
    print(sum(l))
else:
    for i in range(c):
        u.append(l.pop(0))
    a = (n-len(u)) // len(l)
    b = (n-len(u)) % len(l)
    print(sum(u) + a * sum(l) + sum(l[:b]))

Submission status: Accepted

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

List = [X]

for i in range(N-1):
    X = X**2 % M
    if X in List:
        #配列の何番目か
        num = i + 1
        #同じ数字
        key = List.index(X)
        break
    List.append(X)

ans = sum(List)
if len(List) == N:
    print(ans)

else:
    loop = (N - len(List)) // (num - key)
    add = (N - len(List)) % (num - key)

    ans += (N - len(List)) // (num - key) * sum(List[key:num])
    ans += sum(List[key:key+((N - len(List)) % (num - key))])

    print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n, x, m = map(int, input().split())
    a = [None] * m
    s = [x]
    a[x] = 0
    ans = x
    for i in range(1, n):
        x = pow(x, 2, m)
        if a[x] is None:
            ans += x
            a[x] = i
            s.append(ans)
        else:
            past = a[x]
            d = i - past
            ans += x
            s.append(ans)
            diff = s[i] - s[past]
            ans += ((n - i - 1) // d) * diff
            ans += s[past + ((n - i - 1) % d)] - s[past]
            break
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, x, mod = map(int, input().split())
lst = [0, x]
num_set = set([x])
num_lst = [0, x]
flag = False

for i in range(mod - 1):
  x = (x * x) % mod
  s = x + lst[-1]
  if x == 0:
    lst.append(s)
    break
  if x in num_set:
    flag = True
    break
  lst.append(s)
  num_set.add(x)
  num_lst.append(x)
  if i + 2 == n:
    break

#print(lst)
if flag:
  for i, ele in enumerate(num_lst):
    if x == ele:
      loop_s = i
      break

l = len(lst)
if lst[l - 1] == lst[l - 2]:
  print(lst[l - 1])
else:
  if not flag:
    print(lst[-1])
  else:
    loop = len(lst) - loop_s
    n -= loop_s - 1
    c = n // loop
    r = n % loop
    ans = lst[l - 1] + (c - 1) * (lst[l - 1] - lst[loop_s - 1]) + lst[loop_s + r - 1] - lst[loop_s - 1]
    print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int,input().split())
if N==1:
  print(X)
  exit()
a = [X]
sa = set([X])
for i in range(1,N):
  X = (X**2)%M
  if X in sa:
    break
  else:
    a.append(X)
    sa.add(X)

if i==N-1:
  print(sum(a))
  exit()
start = a.index(X)
ans = sum(a[:start])
base = sum(a[start:])
rep = i-start
sets = (N-start)//rep
more = (N-start)%rep
ans += base*sets + sum(a[start:start+more])
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
MAXM = 101010
visited = [-1 for _ in range(MAXM)]
a = x
loop = [a]
visited[a] = 0
ans = 0
for i in range(1, n):
    a = a**2%m
    if visited[a] < 0:
        visited[a] = i
        loop.append(a)
    else:
        ii = visited[a]
        l = sum(loop[ii:i]) # ループの和
        ll = i-ii # ループの長さ
        ans += sum(loop[:ii]) # ループに入るまでの和
        l_n = (n-ii)//ll # ループの回数
        ans += l*l_n
        rem = n-ii-ll*l_n # 残りの長さ
        ans += sum(loop[ii:rem+ii])
        break
if ans == 0:
    ans = sum(loop)
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
a = [-1 for _ in range(10 ** 5 + 2)]
memo = [-1 for _ in range(m)]
a[1] = x
for i in range(2, 10 ** 5 + 2):
    a[i] = a[i-1] ** 2 % m
    if memo[a[i]] == -1:
        memo[a[i]] = i
    else:
        one_loop = i - memo[a[i]]
        start_loop = memo[a[i]]
        break


if start_loop >= n:
    print(sum(a[1:n+1]))
else:
    ans = sum(a[1:start_loop])
    loop, res = divmod(n - start_loop + 1, one_loop)
    ans += sum(a[start_loop: start_loop + one_loop]) * loop
    ans += sum(a[start_loop: start_loop + res])   
    print(ans)

Submission status: Accepted

Solution code:
def solve(N,X,M):
    Loop = [X]
    Loop_set = set(Loop)

    for i in range(N):
        X = X**2 % M
        if X not in Loop_set:
            Loop.append(X)
            Loop_set.add(X)
        else:
            break

    loop_st = 0
    for i in range(len(Loop)):
        if Loop[i] == (Loop[-1]**2 % M):
            loop_st = i
            break

    loop_len = len(Loop) - loop_st
    ans = sum(Loop[:loop_st])
    N -= loop_st
    ans += (sum(Loop[loop_st:]) * (N // loop_len) + sum(Loop[loop_st:loop_st + (N % loop_len)]))
    return ans

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

    print(solve(N,X,M))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
x = X
nums = []
isSearched = [False] * (M+1)
isSearchedNums = [-1] * (M+1)
n = 0
looped = 0
while True:
    x = (x*x) % M
    if isSearched[x]:
        looped = isSearchedNums[x]
        break
    isSearched[x] = True
    isSearchedNums[x] = n
    nums.append(x)
    n+=1
if (isSearched[0]):
    ans = X
    for i in range(min((N-1), len(nums))):
        ans += nums[i]

    print(ans)
else:
    ans = X
    al = 0
    d = len(nums) - looped
    for i in range(looped, len(nums)):
        al += nums[i]
    if N - 1 > len(nums):
        N -= len(nums)
        ans += sum(nums)
        ans += al * ((N-1) // d)
        for i in range(looped, ((N-1) % d) + looped):
            ans += nums[i]
    else:
        for i in range(N - 1):
            ans += nums[i]

    print(ans)

Submission status: Accepted

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

lst = set()
num = []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i, num.index(x)
        div, mod = divmod(n - cnt, len(num) - idx)
        ans = sum(num[:idx + mod])
        ans += sum(num[idx:]) * (div + 1)
        break
else:
    ans = sum(num)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N,X,M = map(int,input().split())
    dict = {key:0 for key in range(M)}
    #print(dict)
    if N==1:
        return X
    dict[X] += 1
    cnt = 1
    A = [0]*(M+1)
    A[1] = X
    ans = X
    tmp = X
    for i in range(1,N,1):
        tmp = (tmp**2)%M
        if dict[tmp] != 0:
            break
        ans += tmp
        A[i+1] = A[i]+tmp
        cnt += 1
        dict[tmp] += cnt

    num = N - cnt#残り足す回数
    roop_num = cnt - dict[tmp] + 1
    syo = num//roop_num
    amari = num%roop_num
    ans += syo*(A[cnt]-A[dict[tmp]-1])
    ans += (A[dict[tmp]+amari-1]-A[dict[tmp]-1])
    return ans

print(main())

Submission status: Accepted

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

seen=[-2]*M
seen[X]
A=[X]
i=1
while(i<N):
    T=A[-1]**2%M
    if seen[T]!=-2:
        Roop=i-seen[T]
        Left,Right=seen[T],i
        break
    A.append(T)
    seen[T]=i
    i+=1

if i==N:
    print(sum(A))
    exit()

Roopsum=0
for i in range(Left,Right):
    Roopsum+=A[i]

Rest=N-len(A)

ans=sum(A)

ans+=Rest//Roop*Roopsum

for i in range(Rest%Roop):
    ans+=T
    T=T**2%M
print(ans)

Submission status: Accepted

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


def read():
    N, X, M = map(int, input().strip().split())
    return N, X, M


def solve(N, X, M):
    S = [-1 for i in range(M)]
    A = [0 for i in range(M+2)]
    na = X
    # i=1の時にA1=Xとなることを記録
    i = 1
    S[na] = i
    A[i] = X
    for i in range(2, min(N+1, M+1)):
        # i=kの時にAk=a*a%Mとなることを記録
        A[i] = A[i-1] * A[i-1] % M
        a = A[i-1]
        na = A[i]

        if S[na] == -1:
            S[na] = i
        else:
            # 再出現したとき、周期[S[na], S[a]]となる
            period_start = S[na]
            period_end = S[a]
            period_length = S[a] - S[na] + 1
            # 何周するかと、余りを求める
            n_loop, left = divmod(N - S[na] + 1, period_length)
            # 一周当たりの加算
            loop_sum = sum(A[S[na]:i])
            left_sum = sum(A[S[na]:S[na]+left])
            ans = sum(A[:S[na]]) + n_loop * loop_sum + left_sum
            return ans
        if na == 0:
            break
    return sum(A)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,x,m=nii()

ans=x
x_list=[x]
zan=0
for i in range(n-1):
  a=(x**2)%m
  ans+=a
  x=a
  if x in x_list:
    inx=x_list.index(x)
    zan=(n-1)-i-1

    inx=x_list.index(x)+1
    nx_list=x_list[inx:]+[x_list[inx-1]]

    if zan<=len(nx_list):
      ans+=sum(nx_list[:zan])
    else:
      num=zan//len(nx_list)
      q=zan%len(nx_list)
      ans+=sum(nx_list)*num
      ans+=sum(nx_list[:q])
    break
  else:
    x_list.append(x)

print(ans)

Submission status: Accepted

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

used=[0]*m
used[x]=1
cnt=1
y=x
while True:
    y=y**2
    y%=m
    cnt+=1

    if used[y]>0:
        loopst=used[y]
        loopend=cnt-1
        break
    
    used[y]=cnt

ans=0
loopsum=0
beforesum=0
for i in range(m):
    if loopst<=used[i]<=loopend:
        loopsum+=i
    if 0<used[i]<loopst:
        beforesum+=i

if n>loopend:
    n-=loopst-1
    ans+=beforesum
    ans+=n//(loopend-loopst+1)*loopsum
    n%=(loopend-loopst+1)
    
    for i in range(m):
        if used[i]==loopst:
            x=i
            break

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

print(ans)

Submission status: Accepted

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

l = []
ans = 0
for i in range(n):
    if x in l:
      
        d = l.index(x)
        ans += sum(l[:d])
        le = len(l)-d
        
        count = sum(l[d:])
        #print(count)
        n -= d
        #print(n)
        ans += count*(n//le)
        n %= le
        #print(n,ans)
        for k in range(d,d+n):
            ans += l[k]

        print(ans)
        exit()
        break
    l.append(x)
    x = (x**2)%m

print(sum(l))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

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

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

ans = x

num = x
data[x] = (1, 0)
count = 2

flag = 0
while(count <= n):
    # print(count)
    num_new = (num**2) % m
    if data[num_new] == -1 or flag == 1:
        data[num_new] = (count, ans)
        ans += num_new
        num = num_new
    else:
        diff = ans-data[num_new][1]
        frec = count - data[num_new][0]

        kaisuu = (n-(count-1))//frec

        if kaisuu > 0:
            count = count-1 + frec*kaisuu
            ans += kaisuu*diff
        else:
            ans += num
            num = num_new
        flag = 1
    count += 1

# print(count, n)
# print(flag, ans)
print(ans)

Submission status: Accepted

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

s = set()
idx = {i: -1 for i in range(m)}
cumsum = [0]
val = x
idx[val] = 0
for i in range(n):
    cumsum.append(cumsum[-1] + val)
    val = pow(val, 2, m)
    if idx[val] != -1:
        break
    idx[val] = i + 1

if len(cumsum) > n:
    print(cumsum[n])
else:
    loop_len = i + 1 - idx[val]
    print((cumsum[i+1]-cumsum[idx[val]]) * ((n-idx[val])//loop_len) + cumsum[idx[val]+(n-idx[val])%loop_len])

Submission status: Accepted

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

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

li = [-1] * (m+1)
v = [False] * (m+1)
v2 = [False] * (m+1)
v[x] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = (i ** 2) % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[n-1])
else:
    n -= len(ans_li)
    if len(loop_li) == 0:
        print(ans_li[-1])
    else:
        if n % len(loop_li) == 0:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
        else:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
ans = 0
al = set([x])
for i in range(n):
  ans += x
  x = (x**2)%m
  if x==0:
    break
  if x in al:
    ind = list(al).index(x)
    loop = i-ind+1
    l = list(al)
    ans += sum(l[ind:i+1])*((n-i-1)//loop)
    for j in range((n-i-1)%loop):
      ans += l[ind+j]
    break
  al.add(x)
print(ans)

Submission status: Accepted

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

ans, tmp = X, X
s = set()
s.add(X)
for i in range(1, N):
  tmp = (tmp**2) % M
  if tmp == 0:
    break
  if tmp == 1:
    ans += N-i
    break
  if tmp not in s:
    s.add(tmp)
    ans += tmp
  else:
    s = list(s)
    idx = s.index(tmp)
    ans += sum(s[idx:]) * ((N-i)//(len(s)-idx))
    ans += sum(s[idx:idx+(N-i)%(len(s)-idx)])
    break
print(ans)

Submission status: Accepted

Solution code:
N, X, M = [int(x) for x in input().split()]
s = [0] * (M+10)
s[1] = X
d = {X: 0}
tmp = X
for i in range(M):
    tmp = tmp * tmp % M
    if tmp == 0:
        print(s[i+1])
        exit()
    elif tmp in d:
        l, r = d[tmp], i+1
        sl = s[r] - s[l]
        loop = r-l
        ans = sl*((N-l)//loop) + s[l+(N-l)%loop]
        print(ans)
        exit()
    else:
        d[tmp] = i+1
        s[i+2] = s[i+1] + tmp
print(d)

Submission status: Accepted

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


def main():
    n, x, m = map(int, input().split())
    lst = [[False, 0] for _ in range((m + 1))]
    lst[x] = [True, 1]
    res = [x]
    loop = 0

    for i in range(2, m + 1):
        x = f(x, m)
        if lst[x][0] == False:
            lst[x][0] = True
            lst[x][1] = i
            res.append(x)
        else:
            loop = i - lst[x][1]
            non_loop = lst[x][1] - 1
            break
    if loop == 0:
        print(sum(res[:n]))
        exit()
    ans = sum(res[:non_loop])
    ans += (n - non_loop) // loop * sum(res[non_loop:])
    ans += sum(res[non_loop:non_loop + (n - non_loop) % loop])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
set_ = set()
l = []
cnt =0
dic = {}
while x not in set_ and cnt<n:
    set_.add(x)
    l.append(x)
    dic[x]= cnt
    cnt += 1
    x = (x**2)%m
    if x==0:
        l.append(0)
        break
if l[-1]==0:
    print(sum(l));exit()
if cnt==n:
    print(sum(l));exit()

ans = sum(l[:dic[x]])
l = l[dic[x]:]

L = l+ l
cnt  = len(l)
n-=dic[x]
s = sum(l)
ans += (n//cnt)*s + sum(l[:n%cnt])

print(ans)

Submission status: Accepted

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

A = []
temp = X

while Flag[temp]:
  A.append(temp)
  Flag[temp] = False
  temp = (temp**2)%M
  last = temp

I = A.index(last)
looplen = len(A) - I
loop, cnt = divmod(max(N-I, 0), looplen)

ans = 0
if N <= I+1:
  ans += sum(A[:N])
else:
  ans += sum(A[:I])
  ans += loop*sum(A[I:])
  ans += sum(A[I:I+cnt])

print(ans)

Submission status: Accepted

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

A = X
i = 1
sigma = X
A_list = [None, X]
A_sigma = [None, X]
A_index = {X: 1}
cycled = False
while i < N:
    A = A*A % M
    i += 1
    sigma += A

    if cycled: continue

    A_list.append(A)
    A_sigma.append(sigma)
    if A not in A_index:
        A_index[A] = i
    else:
        cycle_len = i - A_index[A]
        cycles = (N-i) // cycle_len
        sigma += (sigma - A_sigma[A_index[A]]) * cycles
        i += cycles * cycle_len
        cycled = True

print(sigma)

Submission status: Accepted

Solution code:
n,X,m=map(int,input().split())
if m==1:
    print(0)
else:
    x=[0]*m
    y=[0]*m
    y[0]=X
    z=[0]*(m+1)
    z[X]+=1
    for i in range(1,m):
        x[i]=(i**2)%m
    for i in range(1,m):
        y[i]=x[y[i-1]]
        z[y[i]]+=1
        if z[y[i]]==2:
            e=i
            q=y[i]
            break
    for i in range(len(y)):
        if y[i]==q:
            b=i
            break
    l=y[b:e]
    L=len(l)
    s=sum(l)
    #print(x)
    #print(y)
    #print(z)
    #print(b,e)
    #print(l)
    #print(sum(y[:b]))
    #print(((n-b)//L)*s)
    #print(sum(l[:(n-b)%L]))
    if n>=b:
        ans=sum(y[:b])+((n-b)//L)*s+sum(l[:(n-b)%L])
    else:
        ans=sum(y[:n])
    print(ans)

Submission status: Accepted

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

p = x
seen = {}
total = 0
done = False

for i in range(min(n, m)):
    total += p

    if p in seen:
        #print(p, "already seen!")
        cycleTotal = total - seen[p][1]
        cycleLength = i - seen[p][0]
        #print("total", cycleTotal, "length", cycleLength)

        iterationsLeft = (n-(i+1))
        total += (iterationsLeft//cycleLength) * cycleTotal

        iterationsLeft %= cycleLength

        for j in range(iterationsLeft):
            p = (p**2)%m
            total += p

        print(total)
        done = True
        break
    else:
        seen[p] = (i, total)

    p = (p**2)%m

if not done:
    print(total)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ans=x
rp=[x]
if n<=m:
    for i in range(n-1):
        x=pow(x,2,m)
        ans+=x
    print(ans)
    exit()
for i in range(m+1):
    x=pow(x,2,m)
    if x in rp:
        tt=rp.index(x)
        t=len(rp)-tt
        break
    else:
        rp.append(x)
tmp=sum(rp[tt:])
wari=(n-tt)//t
amari=(n-tt)%t
ans=sum(rp[:tt])+tmp*wari+sum(rp[tt:tt+amari])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n, x, m = map(int, input().split())
seen = [-1] * m
is_done = True
ans = 0
for i in range(n):
    if i == 0:
        val = x
    else:
        val = val * val % m
    if seen[val] != -1:
        loop_len = i - seen[val]
        loop_val = val
        is_done = False
        cnt = i
        break
    else:
        seen[val] = i
        ans += val
if is_done:
    print(ans)
    exit()
n -= (cnt + 1)

val = loop_val
loop_sum = 0
for i in range(loop_len):
    val = val * val % m
    loop_sum += val
ans += (n // loop_len) * loop_sum

val = loop_val
for i in range(n % loop_len):
    val = val * val % m
    ans += val

print(ans + loop_val)

Submission status: Accepted

Solution code:
n, x, m = map(int,input().split())
k = (x ** 2) % m
l = [0] * (m+1)
l[(x ** 2) % m] == 0
a = [x]
flag = True
for i in range(n-1):
    x = (x ** 2) % m
    a.append(x)
    if l[x] != 0:
        flag = False
        break
    else:
        l[x] += 1
    
    

if not flag:
    p = i+1
    ku = n - p 
    f = False
    loops = []
    for i in range(len(a)-1):
        if f:
            loops.append(a[i])
        else:
            if (a[i]) == a[-1]:
                loops.append(a[i])
                p = len(a) - (i+1)
                f = True
    k = max(1, len(loops))
    w = (ku) // k
    x = (ku) % k


if flag:
    ans = sum(a)
else:
    sss = 0
    for i in range(x):
        sss += loops[i]
    ans = sum(a) - a[-1] + sum(loops) * w + sss
print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ans=x
a=x
res=[x]
res2=0
r=0
for i in range(1,m+1):
    a=(a*a)%m
    if a==0:
        break
    if a in res:
        r=res.index(a)
        res2=i-r
        break
    else:
        ans+=a
        res.append(a)
b=[0]*m
for i in range(res2):
    b[i+1]=b[i]+res[r+i]
if res2==0:
    print(ans)
else:
    k=(n-r)//res2;l=(n-r)%res2
    ans+=b[res2]*(k-1)+b[l]
    print(ans)

Submission status: Accepted

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

lis=[0]*m

ans=x
ai=x
lis[ai]=[1,ans]
flg=0

for i in range(2,n+1):
    ai=(ai**2)%m
    if lis[ai]!=0:
        start=lis[ai][0]
        goal=i-1
        span=goal-start+1
        sumspan=ans-lis[ai][1]+ai
        flg=1
        break
    ans+=ai
    lis[ai]=[i,ans]

if flg:
    times=(n-goal)//span
    last=(n-goal)%span
    ans+=sumspan*times
    #print(last)
    #print(sumspan*times)
    if last==1:
        ans+=ai
    for i in range(0,last-1):
        ans+=ai
        #print(i)
        ai=(ai**2)%m
        if i == last-2:
            ans+=ai
    print(ans)
else:
    print(ans)

Submission status: Accepted

Solution code:
def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

import heapq

n,x,mod = map(int,input().split())
c = [x]
heapq.heapify(c)
cc = [x]
num = x
count = 1
while True:
    num = pow(num, 2, mod)
    if binary_search(c, num) != -1:
        b = cc.index(num)
        l = count - b
        cycle = cc[b:]
        startl = b
        start = cc[:b]
        break
    count += 1
    heapq.heappush(c, num)
    cc.append(num)

# print(cc)
# print(cycle,l)
# print(start,startl)
ans = 0
if n <= startl:
    for i in range(n):
        ans += start[i]
    print(ans)
else:
    ans += sum(start)
    n -= startl
    # print(n)
    syo = n // l
    amari = n % l
    s = [0]*(l+1)
    for i in range(1,l+1):
        s[i] = s[i-1] + cycle[i-1]
    ans += s[l]*syo + s[amari]
    print(ans)

Submission status: Accepted

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

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

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

d = [-1] * (M + 1)
out = [0]
a = X
ans = 0
for i in range(1, N + 1):
    ans += a
    d[a] = i
    out.append(a)
    a = a ** 2 % M
    if a == 0:
        print(ans)
        exit()

    if d[a] != -1:
        loop_num = i + 1 - d[a]
        remain = N - i
        ans += sum(out[d[a]:d[a] + loop_num]) * (remain // loop_num)
        ans += sum(out[d[a]:d[a] + (remain % loop_num)])
        break
print(ans)

Submission status: Accepted

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

count = [0 for _ in range(M)]
cumsum = [0]
now = X%M
nowcount = 1
while count[now] == 0:
  count[now] = nowcount
  cumsum.append(now + cumsum[-1])
  now = pow(now, 2, M)
  #print(now)
  nowcount += 1
#print(cumsum)
#print(nowcount)
#print(nowcount,count[now])
#print(len(cumsum), cumsum)
loop = cumsum[nowcount-1]-cumsum[count[now]-1]
#print(loop)
if N < nowcount:
  print(cumsum[N])
else:
  ans = cumsum[nowcount-1]
 # print("preans 1", ans)
  N -= (nowcount-1)
  f = nowcount - count[now]
  r = N%f
  q = N//f
 # print("preans 1",N, f, r, q)
  ans += q*loop + cumsum[count[now]-1+r] - cumsum[count[now]-1]
  print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import collections
#import itertools
#import heapq
#from collections import deque
#d = deque()

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    cnt=collections.Counter()
    n,x,m=map(int, readline().rstrip().split())
    a=x
    if n==1:
        print(a)
        return
    t=-1
    i=2
    stock=0
    nnn=0
    ans=a
    gogo=False
    b=a
    f=-1
    while i <= n:
        a=(a*a)%m
        ans+=a
        cnt[a]+=1
        if gogo==False:
            if cnt[a] == 2:
                stock+=a
                if f<0:
                    f=i
            if cnt[a] == 3:
                ans-=a
                hani=i-f
                nokori=n-i+1
                ddd=nokori//hani
                ans+=stock*ddd
                i+=ddd*hani
                i-=1
                gogo=True
                a=b
        i+=1
        b=a
    print(ans)
    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

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

mods = [0 for _ in range(M)]

x = X
f = False
res = 0
for i in range(N):
    if mods[x]:
        k = i
        l = i + 1 - mods[x]
        f = True
        break
    res += x
    mods[x] = i + 1
    x **= 2
    x %= M

if not f:
    res = 0
    for i in range(M):
        if mods[i]:
            res += i
    print(res)

else:
    x2 = x
    lsm = 0
    for i in range(k):
        if k - l <= i <= k - 1:
            lsm += x
        x **= 2
        x %= M
    loop, r = divmod(N - k, l)
    res += loop * lsm
    for i in range(r):
        res += x2
        x2 **= 2
        x2 %= M

    print(res)

Submission status: Accepted

Solution code:
import sys
import numpy as np

readline = sys.stdin.readline

n, x, m = map(int, input().split())
l = np.full(m+1,-1)
l[0] = x
s = set()
s.add(x)
lsum = [-1 for i in range(m+1)]
lsum[0] = x
for i in range(1,m+1):
    a = pow(int(l[i-1]),2,m)
    if a in s:
        if n <= i:
            print(lsum[n-1])
            sys.exit()
        j = np.where(l==a)[0][0]
        if j == 0:
            ans = lsum[i-1]
            n -= i
            ans += (lsum[i-1]) * (n//(i-j))
            if n % (i-j) == 0:
                print(ans)
                sys.exit()
            else:
                d = n % (i-j)
                ans += lsum[d-1]
                print(ans)
                sys.exit()
        else:
            ans = lsum[i-1]
            n -= i
            ans += (lsum[i-1] - lsum[j-1]) * (n//(i-j))
            if n % (i-j) == 0:
                print(ans)
                sys.exit()
            else:
                d = n % (i-j)
                ans += lsum[j+d-1] - lsum[j-1]
                print(ans)
                sys.exit()
    else:
        s.add(a)
        l[i] = a
        lsum[i] = lsum[i-1] + a

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
l=[0 for i in range(m)]
ans=0
y=[]
i=1
flag=0
ys=n
while i<n+1:
    if flag==0:
        ans+=x
    l[x]+=1
    x=x*x%m
    i+=1
    if l[x]==2 and flag==0:
        flag=1
        ys=i
    if flag:
        if l[x]==3:
            break
        y.append(x)
if len(y):
    p,pp=divmod(n-ys,len(y))
    print(ans+p*sum(y)+sum(y[:pp+1]))
    #print(ans,p*sum(y),sum(y[:pp+1]))
else:
    print(ans)

Submission status: Accepted

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

S = {X : 1}

path = [X]

cnt = 1
ans = X
a = X
for i in range(2, N + 1):
    a = a * a % M
    if a in S:
        cnt = i - S[a]
        break
    S[a] = i

    ans += a
    path.append(a)

pre_len = S[a] - 1

Q, R = divmod(N - pre_len - 1, len(path) - pre_len)

pre = sum(path[:pre_len])
cycle = sum(path) - pre

ans = a
for _ in range(R):
    a = a * a % M
    ans += a

print(pre + Q * cycle + ans)

Submission status: Accepted

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

F=[0 for i in range(10**5+1)]
for i in range(10**5+1):
    F[i]=pow(i,2,M)
    
Flag=[False for i in range(10**5+1)]
A_i=X
while True:
    A_i=F[A_i]
    if Flag[A_i]:
        st=A_i
        break
    Flag[A_i]=True

A_i=X
Sum_1=0
cnt=0
while True:
    if A_i==st:
        break
    cnt+=1
    Sum_1+=A_i
    A_i=F[A_i]

roop=1
A_i=st
Sum_2=0
while True:
    Sum_2+=A_i
    A_i=F[A_i]
    if A_i==st:
        break
    roop+=1

    
A_i=st
Sum_3=0
for i in range((N-cnt)%roop):
    Sum_3+=A_i
    A_i=F[A_i]
    
    
if N-cnt>roop:
    ans=Sum_1+Sum_2*((N-cnt)//roop)+Sum_3
elif N<=cnt:
    ans=0
    A_i=X
    for i in range(N):
        ans+=A_i
        A_i=F[A_i]

else:
    ans=Sum_1
    A_i=st
    for i in range(N-cnt):
        ans+=A_i
        A_i=F[A_i]

print(ans)