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:
N, X, M = map(int, input().split())

count = X
bef = X
_sum = [bef]
dic = {}

for i in range(1, N):
    bef = pow(bef, 2, M)
    if bef in dic:
        posi = dic[bef]
        l = len(_sum) - posi
        plus = sum(_sum[posi:])
        count += plus * ((N - i) // l)
        mod = ((N - i) % l)
        count += sum(_sum[posi:posi + mod])
        break
    else:
        dic.setdefault(bef, i)
        _sum.append(bef)
    count += bef

print(count)

Submission status: Accepted

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

flag = [False]*(10**5 + 10)
A = [X]
for i in range(N):
    X = X**2 % M
    if flag[X]:
        break
    
    flag[X] = True
    A.append(X)

# return index when a appears for the first time
index = A.index(X)

# A's before loop begins
loop_bef = A[0:index]

# A's where loop exists
loop = A[index:]

# number of loops
num_loop = (N - len(loop_bef)) // len(loop)
num_aft_loop = (N - len(loop_bef)) % len(loop)

ans = sum(loop_bef) + sum(loop)*num_loop + sum(loop[:num_aft_loop])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

A = [-1] * (10 ** 5)

i = 1
A[x] = i
sum = []
sum.append(0)
sum.append(x)
while i < n:
    i += 1
    x = (x * x) % m
    if A[x] != -1:
        break
    A[x] = i
    sum.append(sum[-1] + x)

if i == n:
    print(sum[n])
    exit()

pre_i = A[x]
dis = i - pre_i
cnt = (n + 1 - pre_i) // dis
div = (n + 1 - pre_i) % dis
ans = sum[pre_i - 1]
ans += (sum[i - 1] - sum[pre_i - 1]) * cnt
if div != 0:
    ans += sum[pre_i + div - 1] - sum[pre_i - 1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, x, m = map(int, input().split())
x_set = set()
x_list = []
for i in range(n):
    if x not in x_set:
        x_set.add(x)
        x_list.append(x)
    else:
        break
    x = x**2 % m
total = 0
start = n
for i in range(n):
    if x_list[i] == x:
        start = i
        break
    else:
        total += x_list[i]
if start != n:
    m = len(x_list) - start
    k = (n - start) // m
    total += k * sum(x_list[start:])
    for i in range(0, n - k * m - start):
        total += x_list[start + i]
print(total)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
A = [0, x]
d = {x:1}
for i in range(2, n+1):
    A.append(A[i-1]**2 % m)
    if A[i] in d:
        j = d[A[i]]
        q, r = divmod(n-j+1, i-j)
        print(sum(A[:j]) + q*sum(A[j:i]) + sum(A[j:j+r]))
        break
    else:
        d[A[i]] = i
else:
    print(sum(A))

Submission status: Accepted

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

pre = X
table[pre] = 0
seq = [pre]
cnt = 0
while True:
    cnt += 1
    A = pre**2%M
    if not table[A]:
        seq.append(A)
        table[A] = cnt
        pre = A
    else:
        f = table[A]
        s = cnt
        break
    
ans = 0
for i in range(f + (N-f)%(s-f)):
    ans += seq[i]
m = (N-f)//(s-f)
for i in range(f, s):
    ans += seq[i]*m

print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int,input().split())
ans = 0
ls = [X%M] + [-1]*(M+1)
ls_app = [0]*(M+1)

for i in range(N):
    a = ls[i]
    ls_app[a] = i
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls_app[ls[i+1]] != 0:
        b = ls[i+1]
        L = ls_app[b]
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)

Submission status: Accepted

Solution code:
n,x,m = map(int, input().split())
be = x % m
ans = be
memo = [[0,0] for i in range(m)]
am = [be]
memo[be-1] = [1,0]  #len-1
for i in range(n-1):
    be = be**2 % m
    if be == 0:
        break
    elif memo[be-1][0] == 1:
        kazu = memo[be-1][1]
        l = len(am) -  kazu
        syou = (n-i-1) // l
        amari = (n-i-1)%l
        sum = 0
        for k in range(kazu, len(am)):
            sum += am[k]
        ans = ans + syou*sum
        if amari > 0:
            for j in range(kazu,kazu + amari):
                ans += am[j]
        break
    else:
        ans += be
        am.append(be)
        memo[be-1][0] = 1
        memo[be-1][1] = len(am) -1
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int,input().split())
ans = x
num = 0
l = [0]*m
lis = [-1]*m
l[0] = x
lis[x] = num
for i in range(1,n):
    x = (x*x)%m
    num += 1
    if lis[x]!=-1:
        a = (n-i)//(i-lis[x])
        b = (n-i)%(i-lis[x])
        ans += a * sum(l[lis[x]:i])
        for j in range(lis[x],lis[x]+b):
            ans += l[j]
        break
    l[i] = x
    lis[x] = i
    ans += x
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int,input().split())
ans = 0
ls = [X%M] + [-1]*(M+1)
ls_app = [0]*(M+1)

for i in range(N):
    a = ls[i]
    ls_app[a] = i
    ls[i+1] = pow(a,2,M)
    if i+1 < N and ls_app[ls[i+1]] != 0:
        b = ls[i+1]
        L = ls.index(b)
        R = i
        len_roop = R - L + 1
        p = (N - L) // len_roop
        q = (N - L) % len_roop
        break
else:
    for i in range(N):
        ans += ls[i]
    print(ans)   
    exit()
    
sum_roop = 0        
for i in range(L, R+1):
    sum_roop += ls[i]
    
sum_edge = 0
for i in range(L, L+q):
    sum_edge += ls[i] 
    
for i in range(L):
    ans += ls[i]
else:
    ans += sum_roop * p + sum_edge        
    
print(ans)

Submission status: Accepted

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

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

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

check = [False for _ in range(M)]
d = [X]
max_x = 0
for _ in range(1, N+1):
    X = f(X, M)
    if check[X]:
        break
    else:
        check[X] = True
    d.append(X)

idx = d.index(X)
ans = sum(d[:idx])
N -= idx
d = d[idx:]

sumd = sum(d)
ans += N//len(d) * sumd

ans += sum(d[:N%len(d)])

print(ans)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
t=[]
t.append(X)
temp=X
ans=X
for i in range(10**5+100):
    temp=temp**2%M
    if temp in t:
        firstindex=t.index(temp)
        currentindex=len(t)
        firstsum=0
        for i in range(firstindex):
            firstsum+=t[i]
        repeatsum=0
        for i in range(firstindex,currentindex):
            repeatsum+=t[i]
        repetition=(N-firstindex)//(currentindex-firstindex)
        lastrep=        (N-firstindex)%(currentindex-firstindex)
        lastsum=0
        for i in range(firstindex,firstindex+lastrep):
            lastsum+=t[i]
        print(firstsum+repetition*repeatsum+lastsum)
        exit()

    else:
        t.append(temp)

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

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)
else:
    ans = sum(num)
print(ans)

Submission status: Accepted

Solution code:


def main():
    n,x,m = map(int,input().split())
    a = [0] * m
    b = [x]
    ans = x
    i = 1
    while i < n:
        x = (x*x) % m
        if x == 0:
            print(ans)
            exit()

        if a[x] == 0:
            a[x] = i
            b.append(x)
            ans += x
            i += 1
        else :
            q = len(b) - a[x]
            qq = (n-len(b)) // q
            qqq = (n-len(b)) % q
            ans += sum(b[a[x]:]) * qq
            ans += sum(b[a[x]:a[x]+qqq])
            #print(b + b[a:] * qq + b[a:a+qqq])
            print(ans)
            exit()

    print(ans)

if __name__ == '__main__':
    main()

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 mod_list[-1] == 0:
    ans = X + sum(mod_list[:min(counter, N - 1)])
else:
    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())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
d,m=divmod(n-l[x],T)
print(S*d+s[l.index(l[x]+m)])

Submission status: Accepted

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

def main():
    N, X, M = map(int, input().split())
    pre = set()
    pre.add(X)
    cnt = 1
    while cnt < N:
        X = f(X, M)
        if X in pre: break
        cnt += 1
        pre.add(X)
    if cnt == N:
        return sum(pre)
    ans = sum(pre)
    N -= cnt
    loop = set()
    loop.add(X)
    while cnt < N:
        X = f(X, M)
        if X in loop: break
        loop.add(X)
    
    left = N % len(loop)
    ans += sum(loop) * (N // len(loop))
    for i in range(left):
        ans += X
        X = f(X, M)
    return ans

print(main())

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
A = X
P = set([A])
cnt, cnt2 = -1, -1
S = A
S2 = 0
off = -1
for i in range(N-1):
    A = A**2%M
    if A in P and cnt == -1:
        cnt = i
        off = A
    elif A ==off:
        cnt2 = i
        break
    S += A
    if cnt != -1:
        S2 += A
    P.add(A)
l = max(cnt2-cnt,1)
if cnt2==-1:
    res = S
else:
    res = 0
    for i in range((N-cnt-1)%l):
        res += off
        off = off**2%M
    res += S + ((N-cnt2-1)//l)*S2
print(res)
"""
9 4 7
"""

Submission status: Accepted

Solution code:
def resolve():
    N, X, M = map(int,input().split())
    A_list = [X]
    preA = X
    A_set = set(A_list)
    for i in range(N-1):
        A = preA**2%M

        if A == 0:
            answer = sum(A_list)
            break
        elif A in A_set:
            finished_count = len(A_list)
            # 何番目か確認
            same_A_index = A_list.index(A)
            one_loop = A_list[same_A_index:]
            loop_count, part_loop = divmod(N-finished_count, len(one_loop))
            answer = sum(A_list) + sum(one_loop)*loop_count + sum(one_loop[:part_loop])
            break

        A_list.append(A)
        A_set.add(A)
        preA = A
    else:
        answer = sum(A_list)
    print(answer)
resolve()

Submission status: Accepted

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


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M
    s = [x]
    u = set()
    while True:
        x *= x
        x %= M
        s.append(x)
        if x in u:
            break
        u.add(x)

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

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

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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, X, M):
    ans = 0
    x = X
    x %= M

    x = X
    s = [X]
    u = set()
    while True:
        x *= x
        x %= M
        s.append(x)
        if x in u:
            break
        u.add(x)

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

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

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


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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N, X, M = map(int, input().split())
A = [X]
visited = set()
visited.add(X)

idx = defaultdict()
idx[X] = 0

iii = -1

for i in range(1, M):
    tmp = (A[-1]**2) % M
    if tmp not in visited:
        A.append(tmp)
        visited.add(tmp)
        idx[tmp] = i
    else:
        iii = idx[tmp]

# print(A)
# print(len(A))
# print(iii)

ans = 0

ans += sum(A[:iii])
N -= iii

l = len(A) - iii

ans += (N // l) * sum(A[iii:])
N -= N // l * l

ans += sum(A[iii:iii + N])

print(ans)
exit()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
l=[0]*m
s=[0]*m
t=p=0
while l[x]<1:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
print(S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)])

Submission status: Accepted

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

i=1
A=[X]
seen=[-1]*M
seen[X]=0
while(i<N):
    T=A[-1]**2%M
    #seen[T]~i-1までがループになっている
    if seen[T]!=-1:
        Roop=i-seen[T]
        Left,Right=seen[T],i
        break
    seen[T]=i
    A.append(T)
    i+=1

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

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

Rest=N-len(A)

ans+=Rest//Roop*RoopSum

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

Submission status: Accepted

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

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

a = x
a_set = {a}
a_array = [a]
a_index = 0
while(True):
    a = f(a ** 2, m)
    if a in a_set:
        a_index = a_array.index(a)
        break
    a_set.add(a)
    a_array.append(a)


a_iter_array = a_array[a_index:]
div, mod = divmod(n - a_index, len(a_iter_array))
ans = sum(a_array[:a_index]) + sum(a_iter_array) * div + sum(a_iter_array[:mod])
print(ans)

Submission status: Accepted

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

ans = []
flag = False
for i in range(n):
    if x in ans:
        v = x
        flag = True
        break
    ans.append(x)
    x = x**2 % m
if flag:
    p = ans.index(v)
    l = len(ans) - p
    d, e = divmod(n-p, l)
    print(sum(ans[:p]) + d*sum(ans[p:]) + sum(ans[p:p+e]))
else:
    print(sum(ans))

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
A = X%M
Ans = A
Modset = set()
Modset.add(A)
i = 1
for _ in range(10**6):
    A = pow(A,2,M)
    if A not in Modset:
        Modset.add(A)
        Ans += A
        i += 1
    else:
        break
if 0 in Modset:
    print(Ans)
else:
    S = A
    B = A
    j = 1
    for _ in range(10**6):
        B = pow(B,2,M)
        if A != B:
            S += B
            j += 1
        else:
            break
    rep = (N-i)//j
    Ans += S*rep
    i += j*rep
    if i < N:
        i += 1
        Ans += A
        for _ in range(10**10):
            if i == N:
                break
            else:
                i += 1
                A = pow(A,2,M)
                Ans += A
    print(Ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
l=[-1]*m
s=[0]*m
t=p=0
while l[x]<0:
  t+=1
  l[x]=t
  s[x]=s[p]+x
  p=x
  x=pow(p,2,m)
T=t+1-l[x]
S=s[p]+x-s[x]
if n<l[x]:
  print(s[l.index(n)])
else:
  print(S*((n-l[x])//T)+s[l.index(l[x]+(n-l[x])%T)])

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
ans=0
if n<=10**6:
    for i in range(n):
        ans+=x%m
        x*=x
        x%=m
    print(ans)
else:
    lis=[x]
    s={x}
    while 1:
        x*=x
        x%=m
        if x in s:
            num=x
            break
        lis.append(x)
        s.add(x)
    for i in range(len(lis)):
        if lis[i]==num:
            idx=i
    cnt=(n-idx)//(len(lis)-idx)
    idx2=(n-idx)%(len(lis)-idx)
    #print(lis)
    suma=0
    sumb=0
    for i in range(len(lis)):
        if i<idx:
            suma+=lis[i]
        else:
            sumb+=lis[i]
    ans+=suma+sumb*cnt
    for i in range(idx2):
        ans+=lis[idx+i]
    print(ans)

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


cnt=1
now=x
ans=x
jisyo=defaultdict(list)
jisyo[now]=[ans,cnt]
while cnt<n:
    nex=now**2%m
    cnt+=1
    ans+=nex
    now=nex
    if nex in jisyo:
        tmp=jisyo[nex]
        # print(tmp)
        ans+=(ans-tmp[0])*((n-cnt)//(cnt-tmp[1]))
        cnt=n-(n-cnt)%(cnt-tmp[1])
        break
    else:
        jisyo[now]=[ans,cnt]
    # print(ans,cnt,now)
for i in range(n-cnt):
    now=now**2%m
    ans+=now
print(ans)

Submission status: Accepted

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

s=set()

while True:
    if X==0:
        print(sum(s))
        exit()
    if X in s:
        break
    else:
        s.add(X)
        X=X**2%M
    
loop=set()
while True:
    if X in loop:
        break
    else:
        loop.add(X)
        X=X**2%M

bef_loop=[]
X=_X
while True:
    if  X in loop:
        break
    else:
        bef_loop.append(X)
        X=X**2%M

if N<=len(bef_loop):
    print(sum(bef_loop[:N]))
else:
    ans=sum(bef_loop)
    R=N-len(bef_loop)

    ans+=R//len(loop)*sum(loop)
    r=R%len(loop)

    X=_X
    for _ in range(len(bef_loop)):
        X=X**2%M
    for _ in range(r):
        ans+=X
        X=X**2%M
    print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
g = x * 1
ans = x
arr = []
res = set([])
roop = (0, 0)
k = 0
for i in range(m + 1):
	tmp = x ** 2 % m
	if tmp in res:
		roop = (i, tmp)
		break
	res.add(tmp)
	arr.append(tmp)
	ans += tmp
	x = tmp

for i, y in enumerate(arr):
	if y == roop[1]:
		k = i
		break

ini = sum(arr[:k])
mul = ans - ini - g
t, v = divmod(n - k - 1, roop[0] - k)
print(g + ini + mul * t + sum(arr[k:k + v]))

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
# 一定回数を経ると循環するので最後にかければよい
a_i = x
log = [x]
app=[-1]*m
app[x]=0
last = x
for i in range(1,n):
  a_i = (a_i**2)%m
  if app[a_i] > -1:
    last = a_i
    break
  app[a_i] = i
  log.append(a_i)

# ループの手前(or最後)まで足し合わせる
ans = sum(log[:min(n, app[last])])
if n > app[last]:
  # ループ中合計
  ans += sum(log[app[last]:]) * ((n-app[last]) // (len(log) - app[last]))
  # 末端合計
  ans += sum(log[app[last]:app[last] + (n-app[last]) % (len(log) - app[last])])
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
ans = x
if n <= m:
    for i in range(1, n):
        x = (x * x) % m
        ans += x
    print(ans)
    exit()
cnt = [0] * m
loop = []
start = -1
for i in range(4 * m):
    x = (x * x) % m
    if cnt[x] == 1:
        loop.append(x)
        if start == -1:
            start = i
    cnt[x] += 1
for i in range(m):
    if cnt[i] > 0:
        ans +=  i
l = len(loop)
if l > 0 and start != -1:
    ans += sum(loop) * ((n-1-start) // l)
    ans += sum(loop[:(n-1-start)%l])
print(ans)

Submission status: Accepted

Solution code:
n,x,m=map(int,raw_input().split())
i=0
v=[x]
t={x:0}
p=0 
start=0
while True: 
    i+=1
    y=(x*x)%m 
    if y in t: 
        p+=(i-t[y]) 
        start+=t[y]
        break 
    t[y]=i
    v.append(y) 
    x=y 
ans=0 

if n<(len(v)): 
    for i in range(n): 
        ans+=v[i] 
    print ans 
else: 
    for i in range(start): 
        ans+=v[i] 
    n-=(start) 
    g=n%p+start
    l=n/p 
    for i in range(start,len(v)): 
        ans+=(l*v[i]) 
        if i<g: 
            ans+=v[i] 
    print ans

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, x, m = map(int, args[0].split())

    a = x
    ret = 0
    D = [-1]*(m+1)
    for i in range(n):
        if 0 <= D[a]:
            j = a
            L = []
            while D[j] != a:
                L.append(j)
                j = D[j]
            L.append(j)
            d, r = divmod(n-i-1, len(L))
            ret += d*sum(L)+sum(L[:r+1])
            break
        ret += a
        p = a
        a = pow(a, 2, m)
        D[p] = a

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
def main():
    n,x,m = map(int,input().split())
    amari = [0 for i in range(m)]
    x = x%m
    amari[x] = 1
    loop = [x]
    while True:
        x = x**2 % m
        if amari[x]==0:
            loop.append(x)
            amari[x] = 1
        elif x==0:
            loop.append(0)
            if len(loop)>n:
                print(sum(loop))
            else:
                print(sum(loop[0:n]))
            return
        else:
            st = loop[0:loop.index(x)]
            loop = loop[loop.index(x):]
            break
    ans = 0
    if len(st)>=n:
        ans = sum(st[0:n])
        print(ans)
        return
    ans = sum(st)
    l = (n-len(st))//len(loop)
    ans += l*sum(loop)
    for i in range(n-len(st)-l*len(loop)):
        ans += loop[i]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if x == 0:
    ans = 0
else:
    ans = x % m
dicNum = dict()
dicSum = dict()
dicNum[x] = 1
dicSum[1] = x
dicSum[0] = 0

for i in range(2,n+1):
    b = x
    x = x**2 % m
    if x in dicNum.keys():
        t = i - dicNum[x]
        zan = n - i + 1
        k = zan // t
        ans += (dicSum[i-1] - dicSum[dicNum[x]-1]) * k
        if zan% t != 0:
            zan = zan % t
            ans += dicSum[dicNum[x] - 1 + zan] - dicSum[dicNum[x]-1]
        break
    else:
        ans += x
        dicSum[i] = ans
        dicNum[x] = i

print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
d = dict()
L = []
for i in range(M+1):
    if X not in d:
        d[X] = i
        L.append(X)
    else:
        j = d[X]
        k = i
        break
    X = X*X%M
s=k-j
kk, zz = divmod((N-j), s)
print(sum(L[:j])+sum(L[j:])*kk+sum(L[j:j+zz]))

Submission status: Accepted

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

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

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

result = sum(a[:j])
a = a[j:]
N -= j
x = N // len(a)
y = N % len(a)
result += sum(a) * x + sum(a[:y])
print(result)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,X,M=map(int,input().split())
cnt=0
index=[X]
d=defaultdict(int)
i=1
while True:
	X=pow(X,2,M)
	if d[X]!=0:
		z=d[X]
		break
	d[X]=i
	i+=1
	index.append(X)
target=len(index)-z
total=0
for i in range(z,len(index)):
	total+=index[i]
for i in range(z):
	cnt+=index[i]
total2=0
for i in range(z,z+(N-z)%target):
	total2+=index[i]
cnt+=total*((N-z)//target)+total2
print(cnt)

Submission status: Accepted

Solution code:
import sys

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

    S = [0] * M  # 何回目に来たか
    C = [0] * M  # 最初にたどり着いたときの値

    _sum = 0
    cycle_sum = 0
    cycle_count = 0
    for i in range(1, N+1):
        _sum += X
        if S[X] == 0:
            C[X] = _sum
            S[X] = i
        else:
            cycle_sum = _sum - C[X]
            cycle_length = i - S[X]
            break
        X = X**2 % M
    else:
        print(_sum)
        return        

    # print(X, S[X], C[X], i, _sum)
    first_sum = C[X]
    cycle_n = (N - S[X]) // cycle_length
    _sum = first_sum + cycle_n * cycle_sum
    rest = N - (S[X] + cycle_n * cycle_length)
    # print(first_sum, cycle_length, cycle_sum, _sum, rest)
    # print(X, X**2  % M)

    for i in range(rest):
        X = X**2 % M
        _sum += X
    
    print(_sum)


main()

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
check = [False] * (10**5 + 10)
check_list = [x]
a = x
# ループを見つける
for i in range(n):
    a = (a * a) % m
    if check[a]:
        break
    check[a] = True
    check_list.append(a)

# ループの長さを算出
index = check_list.index(a)
# ループはいる前のやつ
roop_bef = check_list[0:index]
# ループのやつ
roop = check_list[index:]
# print(roop_bef, roop)

# ループが何周あるのかと，ループ終わりがいくつ要素あるかを計算
roop_num = (n - len(roop_bef)) // len(roop)
roop_after_num = (n - len(roop_bef)) % len(roop)

# ループ前+ループのsum*ループ数+ループ後のsumが答え
ans = sum(roop_bef) + sum(roop) * roop_num + sum(roop[:roop_after_num])

print(ans)

Submission status: Accepted

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

h = [0 for i in range(M + 1)]
r = [0 for i in range(M + 1)]

A = X
result = A
h[A] = 1
i = 2
f = True
while i < N + 1:
    r[A] = result

    A = (A * A) % M
    if A == 0:
        break
    result = result + A
    if f and h[A] > 0:
        f = False
        d = i - h[A]
        result = (result - r[A]) * int((N - i) / d) + result
        i = N - (N - i) % d
    h[A] = i
    i = i + 1
print(result)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
# init = x
# 二乗してあまりが x となる個数
amari = [0] * (m + 1)
for i in range(m + 1):
    y = pow(i, 2, m)
    amari[y] += 1 

visited = [0] * (m + 1)
now = x
loop = 1
while True:
    y = pow(now, 2, m)
    if visited[y] == 1:
        last = y
        break
    visited[y] += 1
    now = pow(now, 2, m)
    loop += 1

# print(visited)
# print(loop)
# print(last, 'last')

res = x

# 循環する手前まで
cnt_init = 1
now = x
while True:
    y = pow(now, 2, m)
    # print(y)
    if y == last:
        break
    res += pow(now, 2, m)
    now = pow(now, 2, m)
    cnt_init += 1

# print(loop)
loop = loop - cnt_init
# print(cnt_init)
# print(loop)

# 循環
cnt = (n - cnt_init) // loop
tmp = last # 最初足し込む
now = last
while True:
    y = pow(now, 2, m)
    if y == last:
        break
    tmp += pow(now, 2, m)
    # print('y', y)
    now = pow(now, 2, m)

res += tmp * cnt

# 残り
nokori = (n - cnt_init) % loop

if nokori == 0:
    print(res)
    exit()

now = last
res += last
for _ in range(nokori-1):
    res += pow(now, 2, m)
    now = pow(now, 2, m)

print(res)

Submission status: Accepted

Solution code:
def main(N, X, M):
    kurikaesi = []
    shoki = [X]
    st_shoki = {X}

    now = X
    for n in range(1, N):
        next = (now ** 2) % M
        if next in st_shoki:
            i = shoki.index(next)
            kurikaesi = shoki[i:]
            shoki = shoki[:i]
            break
        else:
            shoki.append(next)
            st_shoki.add(next)
            now = next
    else:
        print(sum(shoki))
        exit()

    shou = (N - len(shoki)) // len(kurikaesi)
    amari = (N - len(shoki)) % len(kurikaesi)

    print(sum(shoki) + sum(kurikaesi) * shou + sum(kurikaesi[:amari]))
    
if __name__ == '__main__':
    N, X, M = list(map(int, input().split()))
    main(N, X, M)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, x, m = map(int, input().split())
now = x
ans = x
d = defaultdict(int)
repeat = []

for i in range(n):
    now = (now**2)%m
    d[now] += 1
    repeat.append(now)
    if d[now] > 1:
        break

for g in range(len(repeat)):
    if repeat[g] == now:
        break
    else:
        ans += repeat[g]
        n -= 1

repeat = repeat[g:-1] 
n -= 1
if len(repeat) != 0:
    ans += sum(repeat)*(n//len(repeat)) + sum(repeat[:n%len(repeat)])
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
check = [False] * (10**5 + 10)
check_list = [x]
a = x
check[a] = True
# ループを見つける
for i in range(n):
    # print('A' + str(i + 1), a)
    a = (a * a) % m
    if check[a]:
        break
    check[a] = True
    check_list.append(a)
# print(ans)

# ループの長さを算出
index = check_list.index(a)
# print(index)
roop_bef = check_list[0:index]
roop = check_list[index:]

# print(roop_bef, roop)

roop_bef_num = len(roop_bef)
roop_num = (n - len(roop_bef)) // len(roop)
roop_after_num = (n - len(roop_bef)) % len(roop)

ans = sum(roop_bef) + sum(roop) * roop_num + sum(roop[:roop_after_num])
# print(roop[:roop_after_num])

# print(rooplen)
print(ans)