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:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000


def main():
    N, X, M = list(map(int, input().split()))     # スペース区切り連続数字

    dp = [0]
    dp.append(X)
    rp = 0
    rps = 0
    rps2 = 0
    for i in range(2, N+1):
        dp.append(dp[i-1]**2 % M)
        for j in range(1, i):
            if dp[i] == dp[j]:
                rp = 1
                rps = j
                rps2 = i
                break
        if rp != 0:
            break

    result = 0
    if rps > 0:
        for i in range(1, rps):
            result += dp[i]

        rc = (N - rps + 1) // (rps2 - rps)
        rpSum = 0
        for i in range(rps, rps2):
            rpSum += dp[i]
        result += rpSum * rc

        rca = (N - rps + 1) % (rps2 - rps)
        for i in range(rps, rps+rca):
            result += dp[i]
    else:
        for i in range(1, N+1):
            result += dp[i]

    # ------ 出力 ------#
    print("{}".format(result))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#xに何番目にきたかを記録していく。-1じゃなければ一回以上きている
table = [-1] * m
extra = []
l = 0
total = 0
#table[x]は周期が始まる点
while table[x] == -1:
    
    extra.append(x)
    table[x] = l
    l += 1
    total += x
    x = (x*x) % m 

#周期の長さ
c = l - table[x]

#周期の和
s = 0
for i in range(table[x], l):
    s += extra[i]

ans = 0

#周期がnより長い場合
if n <= l:
    for i in range(n):
        ans += extra[i]
else:
    #最初の一週目を足す
    ans += total
    n -= l
    #残りの周期の周の和を足す
    ans += s*(n//c)
    n %= c

    for i in range(n):
        ans += extra[table[x]+i]

print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        cyc = (sum_p - P[X[x]]) * ((n - X[x]) // cyc_len)
        remain = P[X[x] + (n - X[x]) % cyc_len] 
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # pre_sum
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check & pre_len
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(pre + cyc + nxt)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x] + (n - X[x]) % cyc_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

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

p=[0]*(M+2)
sum=[0]*(M+2)
p[X]=1
sum[1]=X
f=0
for i in range(2,N+1):
    X=(X**2)%M  
    if p[X]!=0:
        j=p[X]
        f=i
        break
    else:
        sum[i]=X+sum[i-1]
        p[X]+=i

if f==0:
    print(sum[N])
else:
    d,mod=divmod(N-j+1,i-j)
    print(d*(sum[i-1]-sum[j-1])+sum[j+mod-1])

Submission status: Accepted

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

A = X
ans = A

visited = [0]*M
tmp = []

i = 2
while i <= N:
    A = (A*A) % M
    if visited[A] == 0:
        visited[A] = i
        tmp.append(A)
        ans += A
    else:
        ans += A
        loop_length = i-visited[A]
        loop_val = tmp[-1*loop_length:]
        loop_count = (N-i) // loop_length
        ans += sum(loop_val) * loop_count
        visited = [0]*M
        i += loop_length * loop_count

    i += 1

print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
record_sum = [0, ]
flag = [False for _ in range(M)]
An = X

# n=1
record_sum.append(An)
flag[An] = 1

for i in range(2, M + 2):
    An = pow(An, 2, M)  # 　(An ** 2) % Mと等価
    record_sum.append(record_sum[-1] + An)

    if flag[An]:
        start_index = flag[An]
        initial_cost = record_sum[start_index - 1]
        cycle_cost = record_sum[-1] - record_sum[start_index]
        cycle_length = i - start_index
    else:
        flag[An] = i

if start_index >= N:
    print(record_sum[N])

else:
    ans = 0
    ans += ((N - start_index) // cycle_length) * cycle_cost
    ans += record_sum[(N - start_index) % cycle_length + start_index]

    print(ans)

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
A=[X]
x=(A[0]**2)%M
i=0
while not x in A:
    A.append(x)
    i+=1
    x=(x**2)%M

loopid=A.index(x)
looplen=i-loopid+1
loopsum=sum(A[loopid:])
startsum=sum(A[:loopid])

ans=0
if N-1<loopid:
    ans=sum(A[:N])
else:
    loopnum=(N-1-loopid+1)//looplen if looplen else N-1-loopid
    rest=N-1-(loopid+looplen*loopnum)+1
    ans+=startsum
    ans+=loopnum*loopsum
    ans+=sum(A[loopid:loopid+rest])
print(ans)

Submission status: Accepted

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

A,color=[x],["white" for _ in range(m)]
color[x]="gray"
while 1:
    num=A[-1]**2%m
    if color[num]=="gray":
        A.append(num)
        break
    else:
        color[num]="gray"
        A.append(num)

fixed,loop=[],[]
point=A[-1]
flag=0
for i in A[:-1]:
    if i==point:flag=1

    if flag:loop.append(i)
    else:fixed.append(i)

ans=0
if n<=len(fixed):print(sum(fixed[:n]))
else:
    ans +=sum(fixed)
    div,mod=divmod(n-len(fixed),len(loop))
    ans +=div*sum(loop)
    ans +=sum(loop[:mod])
    print(ans)

Submission status: Accepted

Solution code:
class RhoSequence:
    """
    A_1 = start, A_{i+1} = f(A_i) で、かつA_i が一定の整数の範囲内に収まるような数列に対するクエリを処理するクラス

    例：A_1=3, f(x)=x*x%7 -> A_2=2, A_3=4, A_4=2, A_5=4, ...
    """

    def __init__(self, f, start, val_max, val_min=0):
        self.f = f
        self.start = start
        self.val_max = val_max
        self.val_min = 0

        width = val_max - val_min + 1
        n = [-1] * width
        n[start-val_min] = 1
        route = [start] # A_1 からループが見つかるまでA_iの値を格納するリスト
        loop_start_n = -1 # ループがどこから始まったか
        x = start
        for i in range(2, width):
            fx = f(x)
            if n[fx] != -1:
                loop_start_n = n[fx]
                break
            route.append(fx)
            n[fx] = i
            x = fx
        self.route = route
        self.route_before_loop = route[:loop_start_n-1]
        self.loop_start_n = loop_start_n
        self.cycle = self.route[loop_start_n-1:]
        self.cycle_length = len(self.cycle)
    
    def get_nth_value(self, n):
        """
        n番目の数 A_n を返す
        """
        if n < self.loop_start_n:
            # nがループ開始より前の場合
            return self.route_before_loop[n-1]
        
        n -= self.loop_start_n
        return self.cycle[n%self.cycle_length]

    def sum_until_n(self, n):
        """
        A_1 から A_n までの合計を返す
        """
        if n < self.loop_start_n:
            # nがループ開始より前の場合
            return sum(self.route_before_loop[:n])

        ret = sum(self.route_before_loop)
        n -= self.loop_start_n - 1
        n_loop = n // self.cycle_length
        ret += n_loop * sum(self.cycle)
        n -= n_loop * self.cycle_length
        ret += sum(self.cycle[:n])
        return ret

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

    rs = RhoSequence(lambda x: x*x%M, X, M-1, 0)

    # print(rs.get_nth_value(N))
    print(rs.sum_until_n(N))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
a=[0]*(M)
A=X%M
a[A]=1
ans=A
Ans=[A]
flag=0
for i in range(N-1):
    A=A*A%M
    if A==0:
        break
    if a[A]==1:
        flag=1
        break
    a[A]=1
    ans+=A
    Ans.append(A)
if flag==1:
    for num in range(len(Ans)):
        if A==Ans[num]:
            break
    n=len(Ans)-num
    b=sum(Ans[:num])
    x=(N-num)//n
    y=(N-num)%n
    Sum=b+(ans-b)*(x)+sum(Ans[num:y+num])
else:
    Sum=sum(Ans)
print(Sum)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x]+nxt_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
P = [] # (x,pre_sum)
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(n):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = P[X[x]][1]
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = P[X[x]+nxt_len][1] - P[X[x]][1]
        print(pre + cyc + nxt)
        exit()
    P.append([x, sum_p])
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)

Submission status: Accepted

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        asum00[icnt]=asum
        if chk[ai]!=-1:
            icnt0=chk[ai]
            asum0=asum00[icnt0]
            break
        chk[ai]=icnt
        asum+=ai
        ai=f(ai,m)
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Submission status: Accepted

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for icnt in range(m):
        asum00[icnt]=asum
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        chk[ai]=icnt
#        asum00[icnt]=asum
        asum+=ai
        ai=f(ai,m)
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
#    if icntk!=1:
    nk=n0//icntk
    nr=n0%icntk
#    else:
#        nk=n0
#        nr=-1
    asumk=asum-asum0
       
    ans=asum00[icnt0+nr+1]+asumk*nk
    print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(n):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = sum(P[:X[x]])
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = sum(P[X[x]: X[x] + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        nxt_len = (n - X[x]) % cyc_len
        pre = sum(P[:X[x]])
        cyc = (sum_p - pre) * ((n - X[x]) // cyc_len)
        nxt = sum(P[X[x]: X[x] + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Submission status: Accepted

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

flag = [False]*m
a = []
while not flag[x]:
    flag[x] = True
    a.append(x)
    x = pow(x, 2, m)
loop_start_idx = a.index(x)
loop_len = len(a) - loop_start_idx
loop_count = (n - loop_start_idx)//loop_len
loop_amari = (n-loop_start_idx)%loop_len
ans = sum(a[:loop_start_idx])
ans += sum(a[loop_start_idx:])*loop_count
ans += sum(a[loop_start_idx: loop_start_idx + loop_amari])
print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
ans = 0
if x == 0:
    print(0)
    exit()
elif x == 1:
    print(n)
    exit()

flag = [False]*m
a = []
while not flag[x]:
    flag[x] = True
    a.append(x)
    x = pow(x, 2, m)
loop_start_idx = a.index(x)
loop_len = len(a) - loop_start_idx
loop_count = (n - loop_start_idx)//loop_len
loop_amari = (n-loop_start_idx)%loop_len
ans = sum(a[:loop_start_idx])
ans += sum(a[loop_start_idx:])*loop_count
ans += sum(a[loop_start_idx: loop_start_idx + loop_amari])
print(ans)

Submission status: Accepted

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
#elif n<=m*2:
#    asum=x
#    ai=x
#    for i in range(1,n):
#        ai=f(ai,m)
#        asum+=ai
#    print(asum)   
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [-1] * m # for cycle check
for i in range(mn):
    if X[x] > -1:
        pre_len = X[x]
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        pre = sum(P[:pre_len])
        cyc = (sum_p - pre) * ((n - pre_len) // cyc_len)
        nxt = sum(P[pre_len: pre_len + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = i
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Submission status: Accepted

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    chk=[-1]*m
    asum00=[0]*m
    ai,asum=x,0
    for i in range(m):
        if chk[ai]!=-1:
            icnt0=chk[ai]
            break
        else:
            chk[ai]=i
            asum00[i]=asum
        asum+=ai
        ai=f(ai,m)
    icnt=i
    asum0=asum00[icnt0]
        
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0

    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
mod = M
A = [X]
AS = set()
AS.add(X)
cnt = 0
loop = -1
tail = -1
loop_sum = X
tail_sum = 0
while True:
    cnt += 1
    nex = pow(A[-1], 2, mod)
    if nex in AS:
        break
    A.append(nex)
    loop_sum += nex
    AS.add(nex)

for i, a in enumerate(A):
    if a == nex:
        tail = i
        loop = cnt - tail
        A = A[i:]
        break
    tail_sum += a
    loop_sum -= a

ans = tail_sum + (N - tail)//loop * loop_sum
N -= tail
N %= loop

for i in range(N):
    ans += A[i]

print(ans)

Submission status: Accepted

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai,icnt,asum=x,0,0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=f(ai,m)
        icnt+=1
    ai0,icnt0,asum0=x,0,0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=f(ai0,m)
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
#    print("1:",ai,asum,icnt,ai0,asum0,icnt0)
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    air,asumr=ai,0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Accepted

Solution code:

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

def f(ai,m):
    return (ai*ai)%m

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=f(ai,m)
#        ai=(ai*ai)%m
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai,icnt,asum=x,0,0
#    icnt=0
#    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=f(ai,m)
#        ai=(ai*ai)%m
        icnt+=1
    ai0,icnt0,asum0=x,0,0
#    icnt0=0
#    asum0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=f(ai0,m)
#            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
#    print("1:",ai,asum,icnt,ai0,asum0,icnt0)
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    air,asumr=ai,0
#    asumr=0
    for i in range(nr):
        asumr+=air
        air=f(air,m)
#        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)

Submission status: Accepted

Solution code:

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)   
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:
        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Accepted

Solution code:

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

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [False] * m # for cycle check
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        pre = sum(P[:pre_len])
        cyc = (sum_p - pre) * ((n - pre_len) // cyc_len)
        nxt = sum(P[pre_len: pre_len + nxt_len])
        print(pre + cyc + nxt)
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [False] * m # for cycle check
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        cyc = sum(P[pre_len:]) * ((n - pre_len) // cyc_len)
        remain = sum(P[:pre_len + nxt_len])
        print(cyc + remain)
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [False] * m # for cycle check
for _ in range(mn):
    if X[x]:
        pre_len = P.index(x)
        cyc_len = len(P) - pre_len
        nxt_len = (n - pre_len) % cyc_len
        cyc_num = (n - pre_len) // cyc_len
        cyc = sum(P[pre_len:])
        remain = sum(P[:pre_len + nxt_len])
        print(cyc * cyc_num + remain)
        exit()
    X[x] = True
    P.append(x)
    sum_p += x
    x = x*x % m
print(sum_p)

Submission status: Accepted

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

mn = min(n, m)
P = [] # value of pre & cycle
sum_p = 0 # sum of pre + cycle
X = [False] * m # for cycle check

for _ in range(mn):
    if X[x]: break
    X[x]  = True
    P.append(x)
    sum_p += x
    x = x*x % m

if len(P) >= mn:
    print(sum_p)
    exit()

pre_len = P.index(x)
cyc_len = len(P) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

cyc = sum(P[pre_len:])
remain = sum(P[:pre_len + nxt_len])

print(cyc * cyc_num + remain)

Submission status: Accepted

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

mn = min(n, m)
P = [] # value of pre + cycle
sum_p = 0 # sum of pre + cycle
X = [False] * m

for i in range(mn):
    if X[x]: break
    X[x]  = True
    P.append(x)
    sum_p += x
    x = x*x % m

if len(P) >= mn:
    print(sum_p)
    exit()

pre_len = P.index(x)
cyc_len = len(P) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(P[:pre_len])
cyc = sum_p - pre
nxt = sum(P[pre_len: pre_len + nxt_len])

print(pre + cyc * cyc_num + nxt)

Submission status: Accepted

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

a = X
path = [a]  # path: 数列Ai
done = set([a])  # done: 既に登場したAiの項
while True:
    na = pow(a, 2, M)
    if na in done:
        s = path.index(na)  # 繰り返しが始まる箇所
        break
    else:
        path.append(na)
        done.add(na)
        a = na

if N < s + 1:  # N項目がループが始まる箇所よりも前の場合
    ans = sum(path[:N])
else:
    rest = N - s  # rest: ループに入った後の項目数
    x, y = divmod(rest, len(path) - s)  # x: ループを回る回数, y: 最後の1週に満たない項数

    ans = sum(path[:s])  # ループに入る前の和
    ans += sum(path[s:]) * x  # ループを繰り返す部分の和
    ans += sum(path[s: s + y])  # ループの最後の1週に満たない部分の和
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
ls = [False]*M
ls_mod = []
x = X
for m in range(M+1):
  if ls[x] == False:
    ls_mod.append(x)
    ls[x] = m
    x = (x**2)%M
  else:
    last = m
    fast = ls[x]
    diff = last - fast
    break
if M == 1:
  print(0)
else:
  if last > N:
    print(sum(ls_mod[:N]))
  else:
    shou = (N-fast) // diff
    amari = (N-fast) % diff
    print(sum(ls_mod[:fast])+sum(ls_mod[fast:])*shou+sum(ls_mod[fast:fast+amari]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): 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()
    rep = []
    rep_set = set([])
    i = 1

    rep.append(X)
    rep_set.add(X)
    flag = True

    while flag and i < N:
        x = rep[i-1] ** 2 % M
        if x in rep_set:
            rep.append(x)
            break
        rep.append(x)
        rep_set.add(x)
        i += 1

    if i == N:
        print(sum(rep))
    else:
        l = rep.index(rep[-1])
        rep_leng = i - l
        rep_sum = sum(rep[l:i])
        ans = 0
        ans += sum(rep[:l])
        N -= l
        rep_num = N // rep_leng
        rep_amari = N % rep_leng
        ans += rep_sum * rep_num
        ans += sum(rep[l:l+rep_amari])
        print(ans)


main()

Submission status: Accepted

Solution code:
n,x,m = map(int,input().split())
k_1 = set()
k_2 = set()
tmp = list()
loop_number = 0
loop_sum = 0
while x not in k_1:
	k_1.add(x)
	x = x*x%m
while x not in k_2:
	k_2.add(x)
	tmp.append(x)
	loop_number+=1
	loop_sum+=x 
	x = x*x%m
ans = 0
k_1 = list(k_1)
for i in range(len(k_1)):
	ans +=  k_1[i]
ans = ans + loop_sum * ((n-len(k_1))//loop_number)
for i in range((n-len(k_1))%loop_number):
	ans += tmp[i]
print(ans)

Submission status: Accepted

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

a = X
path = [a]
done = set([a])
while True:
    na = pow(a, 2, M)
    if na in done:
        s = path.index(na)  # 繰り返しが始まる箇所
        break
    else:
        path.append(na)
        done.add(na)
        a = na

if N < s + 1:  # N項目がループが始まる箇所よりも前の場合
    ans = sum(path[:N])
else:
    rest = N - s  # ループに入った後の項目数
    x, y = divmod(rest, len(path) - s)  # x: ループを回る回数, y: 最後の1週に満たない項数

    ans = sum(path[:s])  # ループに入る前の和
    ans += sum(path[s:]) * x  # ループを繰り返す部分の和
    ans += sum(path[s: s + y])  # ループの最後の1週に満たない部分の和
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline


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

    P = N.bit_length()
    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()

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
MOD = 1000000007


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

    P = N.bit_length()
    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()

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
MOD = 1000000007


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

    n = 1
    P = 1
    while n < N:
        n *= 2
        P += 1

    pos = [[0] * M for _ in range(P)]
    value = [[0] * M for _ in range(P)]

    for r in range(M):
        pos[0][r] = r * r % M
        value[0][r] = r

    for p in range(P - 1):
        for r in range(M):
            pos[p + 1][r] = pos[p][pos[p][r]]
            value[p + 1][r] = value[p][r] + value[p][pos[p][r]]

    ans = 0
    cur = X % M
    for p in range(P):
        if N & (1 << p):
            ans += value[p][cur]
            cur = pos[p][cur]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

mn = min(n, m)
S = set()
A = []
sum_9 = 0 # sum of pre + cycle

for _ in range(mn):
    if x in S: break
    S.add(x)
    A.append(x)
    sum_9 += x
    x = x*x % m

if len(A) >= mn:
    print(sum_9)
    exit()

pre_len = A.index(x)
cyc_len = len(A) - pre_len
nxt_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(A[:pre_len])
cyc = sum_9 - pre
nxt = sum(A[pre_len: pre_len + nxt_len])

print(pre + cyc * cyc_num + nxt)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
S = [0]
F = [None] * m
for j in range(m + 1):
    S.append(S[-1] + x)
    if F[x] is not None:
        i = F[x]
        q, r = (n - i) // (j - i), (n - i) % (j - i)
        print((S[j] - S[i]) * q + S[i + r])
        exit()
    F[x] = j
    x = pow(x, 2, m)

Submission status: Accepted

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

mn = min(n, m)
S = set()
A = []
a = x
sum_9 = 0 # sum of pre + cycle

for _ in range(mn):
    if a in S: break
    S.add(a)
    A.append(a)
    sum_9 += a
    a = a*a % m

if len(A) >= mn:
    print(sum_9)
    exit()

pre_len = A.index(a)
cyc_len = len(A) - pre_len
btm_len = (n - pre_len) % cyc_len

cyc_num = (n - pre_len) // cyc_len

pre = sum(A[:pre_len])
cyc = sum_9 - pre
btm = sum(A[pre_len: pre_len + btm_len])

print(pre + cyc * cyc_num + btm)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
S = [0]
F = [None] * m
for i in range(m + 1):
    S.append(S[-1] + x)
    if F[x] is not None:
        j = F[x]
        q, r = (n - j) // (i - j), (n - j) % (i - j)
        print((S[i] - S[j]) * q + S[j + r])
        exit()
    F[x] = i
    x = pow(x, 2, m)

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
S = [0]
F = [None] * m
for i in range(m + 1):
    S.append(S[-1] + x)
    if F[x] is not None:
        j = F[x]
        q, r = (n - j) // (i - j), (n - j) % (i - j)
        print((S[i] - S[j]) * q + S[j + r])
        exit()
    F[x] = i
    x = pow(x, 2, m)
print(0)