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())

nxt = X
lst = []
dic = {}

for i in range(M + 1):
    if nxt in dic:
        loop_st = dic[nxt]
        loop_ed = i - 1
        break

    lst.append(nxt)
    dic[nxt] = i

    nxt = (nxt ** 2) % M


v = N - loop_st
q, r = divmod(v, loop_ed - loop_st + 1)

pre_sum = sum(lst[:loop_st])
loop_sum = q * sum(lst[loop_st:])
post_sum = sum(lst[loop_st:loop_st + r])
print(pre_sum + loop_sum + post_sum)

Submission status: Accepted

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

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

SeqToNum = []
NumToSeq = {}

while not X in NumToSeq:
    NumToSeq[X] = len(SeqToNum)
    SeqToNum.append(X)
    X = X * X % M

if N <= NumToSeq[X]:
    ans = 0
    for i in range(N):
        ans += SeqToNum[i]
else:
    ans = 0
    for i in range(NumToSeq[X]):
        ans += SeqToNum[i]
    N -= NumToSeq[X]
    # cycle
    cycleScore = 0
    cycle = len(NumToSeq) - NumToSeq[X]
    for i in range(NumToSeq[X], len(NumToSeq)):
        cycleScore += SeqToNum[i]
    ans += cycleScore*(N//cycle)
    N %= cycle
    
    for i in range(NumToSeq[X], NumToSeq[X] + N):
        ans += SeqToNum[i]

print(ans)

Submission status: Accepted

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

# ループを検索して計算量圧縮
# 0->1->...->st->st+1->...->st+lp-1-┐
#             └─────────────────────┘
#                       lp

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

def next(x):
    ret = pow(x,2,m)
    return ret

seen = set([])
seqs = []
for i in range(m+1):
    seen.add(x)
    seqs.append(x)
    x = next(x)
    if x in seen:
        break
start = seqs.index(x)
lp = len(seqs) - start

lpsum = sum(seqs[start:])
lptimes = (n-(start+lp)+(lp-1))//lp
ret_sum = lpsum * lptimes
n -= lp * lptimes
ret_sum += sum(seqs[:n])
ret_val = seqs[n-1]

print(ret_sum)
#print(ret_val)

Submission status: Accepted

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

# ループを検索して計算量圧縮
# 0->1->...->st->st+1->...->st+lp-1-┐
#             └─────────────────────┘
#                       lp


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

seen = set([])
seqs = []
for i in range(m+1):
    seen.add(x)
    seqs.append(x)
    x = pow(x,2,m)
    if x in seen:
        break
start = seqs.index(x)
lp = len(seqs) - start

lpsum = sum(seqs[start:])
lptimes = (n-(start+lp)+(lp-1))//lp
ret_sum = lpsum * lptimes
n -= lp * lptimes
ret_sum += sum(seqs[:n])
ret_val = seqs[n-1]

print(ret_sum)
#print(ret_val)

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
# -1はまだ来てない
order=[-1 for i in range(m)]
index=0
#0,1,2,...　番目の数字を配列で記憶高々mこ
a=[]
while(order[x]==-1):
    order[x]=index
    a.append(x)
    x=(x**2)%m
    index+=1
#1周期の和
tmp=sum(a[order[x]:index])
T=index-order[x]
if(n-1<order[x]):
    print(sum(a[:n]))
else:
    #ループ前の和
    sum1=sum(a[:order[x]])
    #ループ前を全体から引いた数
    x1=n-order[x]
    #ループ回数
    n1=x1//T
    n2=x1%T
    print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
# -1はまだ来てない
order=[-1 for i in range(m)]
index=0
#0,1,2,...　番目の数字を配列で記憶高々mこ
a=[]
while(order[x]==-1):
    order[x]=index
    a.append(x)
    x=(x**2)%m
    index+=1
#1周期の和
tmp=sum(a[order[x]:index])
T=index-order[x]
if(n-1<order[x]):
    print(sum(a[:n]))
else:
    #ループ前の和
    sum1=sum(a[:order[x]])
    #ループ前を全体から引いた数
    x1=n-order[x]
    #ループ回数
    n1=x1//T
    n2=x1%T
    print(sum1+n1*tmp+sum(a[order[x]:order[x]+n2]))

Submission status: Accepted

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

ans = []
c = [0]*m
flag = False
for i in range(n):
    if c[x] == 1:
        flag = True
        break
    ans.append(x)
    c[x] = 1
    x = x**2 % m
if flag:
    p = ans.index(x)
    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:

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

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

    # サイクルのスタートを探索
    loop_start = 0
    for i in range(len(A)):
        if A[i] == X:
            loop_start = i
            break

    # サイクル前の和
    ans = sum(A[:loop_start])
    N -= loop_start

    # サイクルの要素
    A = A[loop_start:]

    loops = N // len(A)
    rest = N % len(A)
    
    ans += sum(A) * loops + sum(A[:rest])

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
n,x,m=MI()
stock=[]
for _ in range(1,n+1):
    if x not in stock:
        stock.append(x)
        x=(x**2)%m
        continue
    else:
        start=stock.index(x)
        repeat=stock[start:]
        l=len(repeat)
        n-=start
        sho=n//l
        amari=n%l
        s=sum(repeat)
        rest=0
        if amari!=0:
            for j in range(amari):
                rest+=repeat[j]
        print(s*sho+rest+sum(stock[:start]))
        sys.exit()
print(sum(stock))

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
count_memo = [-1] * 10**6 # 回数のメモ
num_memo = [0] #1インデックスるにする

a = X
count = 1
count_memo[a] = count
num_memo.append(a)
for i in range(1, N):
    a = a**2 % M
    if count_memo[a] == -1:
        count += 1
        count_memo[a] = count
        num_memo.append(a)
    else:
        break

if count == N:
    answer = sum(num_memo)
else:
    # 周期に入るまでの回数と合計
    count_before_cycle = count_memo[a] - 1
    sum_before_cycle = sum(num_memo[:count_before_cycle+1])
    # 1周期の数と合計
    count_cycle = count - count_before_cycle
    sum_cycle = sum(num_memo[count_before_cycle+1:])
    # 残りのサイクルの数と合計
    cycle_count = (N - count) // count_cycle
    sum_after_cycle = sum_cycle * cycle_count
    # あまりの数と合計
    remain_count =  (N - count) % count_cycle
    sum_remain = sum(num_memo[count_before_cycle+1:count_before_cycle+1 + remain_count])

    answer = sum_before_cycle + sum_cycle + sum_after_cycle + sum_remain

print(answer)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
sup = 10**11
db = [[0]*M for _ in range(sup.bit_length())]
dbcum = [[0]*M for _ in range(sup.bit_length())]
db[0] = [i**2 %M for i in range(M)]
dbcum[0] = [i**2 %M for i in range(M)]
for i in range(1,sup.bit_length()):
  for j in range(M):
    db[i][j] = db[i-1][db[i-1][j]]
    dbcum[i][j] = dbcum[i-1][j]+dbcum[i-1][db[i-1][j]]
ans = X
p = 0
N -= 1
while N:
  if N%2:
    ans += dbcum[p][X]
    X = db[p][X]
  p += 1
  N >>= 1
print(ans)

Submission status: Accepted

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

ans = 0
C = [0]
Xd = [-1] * (M+1)

for i in range(N):
    x = X if i==0 else x**2 % M
    
    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

Submission status: Accepted

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

ans = 0
C = [0]
Xd = [-1] * (M+1)

for i in range(N):
    if i == 0:
        x = X
    else:
        x = x**2 % M
    
    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

Submission status: Accepted

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

ans = X
x = X

C = [0, x]
Xd = [-1] * (M+1)
Xd[x] = 0
i = 1

for i in range(1, N):
    x = x**2 % M

    if Xd[x] > -1:
        break
    Xd[x] = i
    ans += x
    C.append(ans)

loop_len = i - Xd[x]
if loop_len > 0:
    S = C[i] - C[Xd[x]]
    loop_num = (N - i) // loop_len
    ans += loop_num * S
    m = N - loop_num * loop_len - i
    ans += C[Xd[x]+m] - C[Xd[x]]

print(ans)

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import base64
import subprocess
import zlib


exe_bin = "c%1E9eQ*@VmGAu!T98;RSl|V0So>t3WXxI%0wiqCT7AGQtU!lE%mu@++FhY7_CwyC1wmXfiGX;rY|JI86!%$N?k?w0m4NT6E-qi?EQ~>LAF&|0#Ff|%mx}LpjX6Y!v9N)?_j<ZlGou+h<+^{ail$a?-mm+;e*OA&&rHwbxz6AktHnZiv5`L@$X%ML@U09#=Pfq@teH%QzYEFzWE${xRXaVMuxP2H+>avHY*lzYy^m<AMMW!!d096{O9}Cm<<Qpp`xUhQevgKZvwpW!XyvR-u9eBPvi6+1m>j2ke0KKhWw@Sp5G}Pc+WoE+!RuqQ6<$xDCR)nn{t)D*k>9<z7~RDBGxN)v%wA6UJUkYU^{r@nEFM`Bk0rB1ONN?PELqXy&7{0bsZB1{cI}4Ev^~zZRb_K6!?3<8acJY>eNR*!kNopr%{cV3<?u7E)!23pnVdKDumvRfwALQ2ZqIzHlB=9j3h<k4fWKjaJ1oZdIlvz@z%wR#Hk;u8WTM|<f^Rj!kDK66n&2T5{AVWkBPRGF!dHa0{IN;<Uz*@96FrZc;6EV7diH|;S!5n*^(ay<7MR~B3clk31$Xm+g?P<Kk?`Wh7^5qQDDF(8l43>*r6o}$VxYH6j6~DXow1A*P4{-S$5Y8@Z>TRGRqBjuKHnoPZ4^amAf4JH#-qud(tsFEr&H<f^<i4u6ir6rfpCxH^MwaOX;DgtVp1j$?(EzI*s{J*CKeV`87UnNB?7%-Z==}RvqGez%fhiFTx{r(nq#Sq2u-6+fn-eT@OAE{c&bJ05@X3sG%W>&P+_W9k@T(PCiR6PVkjO@g;63B@7}Fb=v$uIn+%J4VqiCTCzk5$L(dEiiG$H}CY21uW71x6cOw;x`5K|a=n#w{%zBJ%qFpBUB#bO=S1biDgi~1wXJBVIEM{;5d_>%w+!ISi#7)smHW9_jFrOKil<+PwJg`gb55?jDgoi?6NQw@{B*yf|(6oI~l87b}sogLWA}V0hnFxXB*0#5c%e;+bZ7|T*E-v*pm9Lh1my`A_Tl{SS(dS*Jz+1LJ<0fy5nj^Sl+2Ch~AOBmy5Zse0+3stl|CC~Zf5Vo^IPZRVZxyz@X5sZ#a*WkC!ml<Kn~8U{n+(g&k4?uN(pKJYZFCRh`}L1c?5e;WvBs)k@^cMV+)3v%UTXNd11+j&@_ZlX_oYitg*NK&lk9%qtizA7_70C0=ls|rh4SYBUfxvUH7fj)3ZJFI3o2Z_-p5t=Jt}-ch1aTZ7qbg}=2YQ)pTOJu92L&@3B>2B@Bya3l1$$7unekj_04BUh1*p4eig2MZh2mXtMA)KRCuKdKdQnVD*TuVpRU4RRN*sJ_(>IBrNUoU;nga9M1{{(;pbGiON9%=?>mHCMShNl2nR<bYiUdve%*1pTwhxLt6C2!J@jk%TeGMYu8<$Vs^X;*l!tzfJi5F%M)`}#qpOP}l>Zmx(Z$7+lz$C*487tp%D;j<y1ICT@_&y!y12NX^2d=!vx|e2|2FdI(&7%v|0(k5%3?R=zm7b*u-HoZuOg4GD>hR8%gCe4iXO`E1HS(VAFux@|L1%q|7L&h<{sfo?;iyyBIN83)uXTE19i^>^^FwffTWO@>fAzp^?CH&XvKHtDjqJxSe*yzz6W)MEexm^<k7-<U|tm-nMMi^Q1}R53-aljMf*{Dl%P?<@Q7V#c`bYG)g!&tpuD55kxmv|H1msA+Syxos1n*t9u;J0DagHbtu>1dDDykYrg_AH3de;UwWGJLS;+N*i3e{Cb@|R;_Lke%oVX~+W5S;ZAKnr2_HX3shi{j%aY3$qLv{$mrz}FtwdWQH2haQEf6HE^fPC+${To!a<=PkD6>`sl2?tA3MWGRGlYd#L2kILUa(_;}7ZH}-N8MR-@JA^0rPtBPTetb2_HXlV_lu{6Tt}Td7{2Xqcs~%n6$Hn1qxTwv4HIZqDJXv!kpBaR>L}zPu!gT#P-Fnyz3?6nY0LL6vH0`BM=e75q7XhW<eJ8W#o(3Sz}2~Ri<>5}wF3rvR>(KG3af6Tm7|4CKtXlks}Re@6*vj<8P#CIx0S(crSxjyAC%_MsIUbjF8>6sF27TF8sPpT{geL8uf~AKWmedMqPf++*}&)LtfFN3-_Y9E9mU_=LP_71fP7)QApc4j{`GiwZ!ll6&yHGV+9+9#`b%?uI?F?TTeGNxLKaZ8S;$x11W;(15af5Id9b99&r+83%x$GhllE*ojjLE=->F&DkXL4*nua?dFPyq#6XbE>RN+a%a#px-M{<M0XPCljRA{De|LO}c2PFHLFuZyZ2!Kkkry7R64!A-d23Zhb2xlw43+*i1c-&t<-A~7Z&9@c%p@qWt2=d25?m4$I3GaN29(){`X<Lh9z->J}**97O0WGx)xs9-?t#t_v=K}IM;najpXc<p8VF<|Q6us(oG5nq-dliEHnjo)rFgv(CxE~0wl$5dv_XSuTur<j4D##xM<XbSY?qKf8V8h1&`JDjxE!Z$Fw4AN^%G;nl*m5HXZmelP8?=nqeEB3@BV#pR`8&KgI8t-qI5x^ZdIn7iLQpwjL|qu2UAZUf0`jSV<xEh1E!gl;Aa9>1$i@C68oP^NcUQ}(v@R&W5tQ!~YCs&Mf-*#A5LU;Dk03^KaJ4QkEhk-abzPSnuXBO2YXMw75O;3X!bAUcfom^Z{$Y831EXgqVC2Q^bV2;Q(|4uQcfOdQTi5FA5cq{hpp(ftfPK?<zDLL<9XN4|y#e{R!f2(k6RmYHN^d}dT%a=p5w&pA!_+_jNvp3GN;k37Q-bB+1-VL)*MrVot^oQckZY>L_1W+N%&g=T<TnKQy+X}LO8dOMK{$2W)(M-A{6E5IyIbkE-J`hfEbLkB4&ZSYBCn!V*{6h-a{<M-(i1{%mXLo2Hq7yW-0hGa1qNaX*MkkVj5BEd%MKcFM6lI@w%ST%gB{OaMSq@Fudgq-3p;VI$hE^Ff^KtFf&7r;@(YERCNP-4;Kp&#=q5MI(OprvKB4S0>u;*vdj#V#ApZ;lF_?d7ZWUenOBMp{@yoXZ@{M4_yY!w8<1Z{i9S5&S9^Wsxf}s3SP`=S2U-g%2-x7vT!+!pD_C4HyRDqz{zpkHV&j{?P0H23<N5fJoy=s++uVDS5Y+MpUgM;wqg!Kz-kK<Vf-hjtGER|jadJ@bS13CiqMSO0CFuet|73dJ)-MA^>-T@Tf>j~U1B%pYIcf*qeK3D8u4{!Y0(Xww7u?)E^3#uy}M=X^t#PRHD1VUgjnJmWb38`c4Jz(P{Y~XaQak|&lRPAx>Cr{3Q{E=mK4{~`t^LZ26sh{Ie7RR{*#y}hTovvZ)=Vv$_omGCPg9rdU3%^0A-;HCkZgRR_u(mnfU$X_Bp1i%yS%0{q!`XOfn%~(xT-oL9w*GL2v)S)#^gHX@oE~V|=5)28zVeyczV09$MdhDOulA4yd@T5Efa5s;{@V<^{W>rpeAw!Dx)0gfot|O4_0|lh+fNm)$A_VA_-%oo3&zy}zO`ReWSEH^WfT2n6W2P&EVih{&`3Y(#AP-J{Z~WC(&NYVPS<v);x+W)VVrYV3Q?lztFzpffPD#yJ6h95{m^IEpMahL(4&5yFO@7cL3oP%rnTaPl^nM&rqF_i1B9HgRJ>v*-?vrd?Btql=J)L6Mf)cmN!~4Y%iVIf+%0#@-SYpm@N-jsPRh?k)!!x6bl9ThkFg7Ww${xK<@lMJ#11{@F`l2>E?_)AW1G(?Kd0r-a{O8HgFB@Z(xdEQhCi4T*x@WcYaC(q{A{p^@%&8C&8YgU6bnDw>}KbG{F$kljgLPc^Rvr)xxVRI{8FXXZZ6NyFnRwAiMAa){?hST7<7m6-ArGJ@!ZaF#^1;4Z!%teR{eij_;+D_Im8_OEk?h?=sz-gmeHRw`d^IRV00Rrn7NET%;*Y6*QgJ3KSSZ?`Mj)cZ(rr9-`tl?N?FfJ?{aVBl4V)S`M&6D_BJ*(DCqB^8^2&Q8+@t7FDbo-xQ$4LxV;?LTD+nh&suz1IqtQ1WjP+SxT73LT6}srUbXm)a$IZis`C2Q;?-o(5T8l94d%~AoMeX~UQ^yLw784xH^gU^^9Qu}Z0$#tGJX$n>lZ%7Ys>qR7N1kzkF@w)!}VZ;U4ic(S{zor#|WSN&a1`ePr+~-f!DH<9>;yj3jXB#H&17&r!w=%-UmHpc`PeU^t3TOE~ggnV0gC<e~RJ9ba;aGJEZIPS$aLypMTBtT+-<|LEBHA7c={RMBC3MwFdKR)c!5{cWV4xrFy2$?*#o@JH`I#76sSad7lOKOpS-7H1EPmJnZA)Zswq;>332$aqHqC%-SDgH_FYdeaeR4VW-B`3p9UVa=q|v;xA3|7G5{O-#5V*SdH^Weve@L$#vbq_N|pxV?EEA;Ku=<Wpz*4w|@Zm1Az1Ip!~jh$c}oZ?i)Wg(SOAR&)5|Ed43o_8?)Gq+t-@l)zqG;`(&d{8JB*3pRgI{d-T|pc^_x%g8MvSQ{qHF?{*qL^T_@OwfH_0JO9>Z99I`?iXOe4Z=2|`+7-X?$|%EU+l|}*z6mbajq_w8ChebP{SLB9ew#dOH_ns!wuzooCjE|?;P2Uu=LJv7jP#REu_yXWHku4a#hz@!8y*}a;@aTGHh)kQGub{dprmzRI!Ulu6l1AaGA5C5TFOY-{(f(mOlI$hQbG)4mQIF<Vk9N*jHmiSaWNvL(it(79U|dWVlW<+q7m=P6)nxijWEX~CWg}K&|Wc`l+t@ie>#+iijiz0u@^*CoQS4qnu_9@P5!P<v2#NQCKrioH*6L=1qKQon~2!)M;rWIfp)0V2uHL4&1Wh5VdI)LJ)ON`ufHwWDJls!E0nYIz)(*JGje<@r<|d8CWsh~grpD(_?ES26WMr3itUbqmqDa`Y3HW(Q}hrqu#qMNCB<we8Zpf(YHd~L%a|o4X<B((K0OCXr&g2l!|GTb&u7oE(wqJXnOu5vBAJvp5Q0vlq~j@XI@<3w&Y4o>E$OYsTr9l>$vp{uPufhVNhMg<+ttqFi>FvknU1OR-LVvNvP29B9$n_CT?P|p5J5iU2on1;8C4esxncUz(iE<6CQDZUPwmoq&cM;Ft*UIUPfX;~q@00bmLjI=85eyy`_9n5$rQ6GmQ6`0G)WpXniihaXOQftHG_CFdlOQq52%z@=m5WpC84uH;!UQcs24o4L<;R>+|Fdy+n0^SBTHftLb-uZW`KAjdy}9~p;B6@*$wWErIH#(gt~Mz9>Rv~YA`NgmoQa$>D`%v3kY`jOTFk#r|7ohjSjHQav+kP<Uo5k3?Ube4oad#J>#9+`4k=e8u|<+Vqv(T3L&tF7xwT3Y_>+XlFw4`oP~Z?W4u{DIxiL-kI!}LoG^X9w@24r|61zP$@BMLPU}8J9^XH1lu9Ws&)<_dt!Fqt4^n@7#Ik`XXFpt?zfW_@^9k|%$fA<x=QN)q+8l5G-py%~?)_ZvzwJahyW!3F`#GoleU001)zMu<ISb-Ee~;&sCuB`ycIwB!k0?In^89_DQ+__B_a7hs0VdzZ@#$KsmcQ3P{%b^?>ppot$SFTZ<3&IJvQD0#GjMuI*WRV0-_-YCrKNg*Idt?dbn^WDhSS-)^AnerrSG?DdH$Zlss5NnKmP9$?fT{Kb(}8Lwb#qPq?0%Me-~!*uj=H>=PHc4b@8wF=XsqxKY!tLsjj_#{rrL``L6ujbMpUjD7@a^`uY2BqU7mvdH(+1e7~{1dU;F{;A;!Z<o}al{j2s5wH&wWC>xXhe7Sp(!k_$<{%`5z%kO=R@O7q_=f%nnl*{%rc{h`9)y-e4PQKEj^she<<?;<W+~~W3(SK$Uc>l~`ybpQF)cs?+%64^mo^AXMx(o$<{LC_ue`$$AT{;21{Qm-&(b$v"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
#from bisect import bisect_left as bl                #c++ lowerbound bl(array,element)
#from bisect import bisect_right as br               #c++ upperbound br(array,element)
#from __future__ import print_function, division    #while using python2
# from itertools import accumulate
# from collections import defaultdict, Counter

def modinv(n,p):
    return pow(n,p-2,p)

def main():
    #sys.stdin = open('input.txt', 'r')
    # sys.stdout = open('output.txt', 'w')

    n, x, m = [int(x) for x in input().split()]
    series = []
    prev = set()
    repeat = []
    ans = 0
    y = x
    repeat_key = -1
    while True:
        if y not in prev:
            prev.add(y)
            series.append(y)
            y = (y * y) % m
        else:
            break

    repeat_key = y
    while True:
        repeat.append(y)
        y = (y * y) % m
        if y == repeat_key:
            break
    # print(series)
    # print(repeat)

    if n <= len(series):
        print(sum(series[:n]))
    else:
        n -= len(series)
        s1 = sum(series)
        s2 = sum(repeat) * (n//len(repeat))

        n %= len(repeat)
        print(s1 + s2 + sum(repeat[:n]))



#------------------ Python 2 and 3 footer by Pajenegod and c1729-----------------------------------------
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
n,x,m=map(int,input().split())
visited=set()
visited_l=[]
loop=set()
loop_l=[]
visited.add(x)
visited_l.append(x)
xc=x
for i in range(m):
    xc=(xc**2)%m
    if xc in visited and not(xc in loop):
        loop.add(xc)
        loop_l.append(xc)
    elif xc in visited and xc in loop:
        break
    else:
        visited.add(xc)
        visited_l.append(xc)
s=len(visited_l)
t=len(loop_l)



if n<=s:
    

    print(sum(visited_l[:n]))
elif n<=s+t:
    print(sum(visited_l)+sum(loop_l[:n-s-t]))

else:
    ans=sum(visited)
    n=n-s
    ans+=(sum(loop_l)*(n//t))
    ans+=sum(loop_l[:n%t])
    print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

numlist = [-1] * M

num = X
ans = num
roop_start = -1
for i in range(N-1):
    new_num = (num * num) % M
    if numlist[num] == -1:
        numlist[num] = new_num
        ans += new_num
        num = new_num
    else:
        roop_start = num
        break

num = roop_start
if roop_start == -1:
    print(ans)
else:
    roop_sum = [num]
    for i in range(N-1):
        new_num = numlist[num]
        numlist[num] = -1
        if numlist[new_num] == -1:
            break
        else:
            roop_sum.append(roop_sum[-1] + new_num)
            num = new_num
        
    if numlist[X] != -1:
        count = 0
        ans = 0
        for i in range(M):
            if numlist[i] != -1:
                ans += i
                count += 1
        N -= count
    else:
        ans = 0

    size = len(roop_sum)
    div = N // size
    rest = N % size
    ans += div * roop_sum[-1]
    if rest != 0:
        ans += roop_sum[rest-1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


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


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


# X%M + X^(2)%M + X^(4)%M + X^(8)%M ...
# 重要な性質X^(k)%M for k=[0,M-1]は循環する
# X^(k) = X^(c*M+k) (mod M)
# = X^(k%M)

# X(0%M)%M + X^(2%M)%M + X^(4%M)%M + X^(8%M)%M ...

# あまりの循環テーブルT
# T[0%M] + T[2%M] + T[4%M] ...
# T[2^(0)%M] + T[2^(1)%M] + T[2^(2)%M] ...(M)  ... (循環するので×だけ) (N%M) ...
# N//M回循環する
# 2のべき乗をMで割ったテーブル
# 正確には違ったね

# (X^2*k) = (X^2)^k
# (X^2)^kが循環する

N, X, M = ints()
A = [X]
for i in range(M):
    A.append(pow(A[-1], 2, M))  # 循環は単純ではないのか

# 早期終了
if N < M:
    exit(sum(A[:N]))

if M == 1:
    exit(0)

# 非ループ部分とそれ以外の検出
visited = set()
for i in range(M):
    if A[i] in visited:
        len_total = i
        break
    visited.add(A[i])
# i番目の要素が初めて出てくるところを改めて探す
s = A.index(A[len_total])
cut = A[:s]
loop = A[s:len_total]
# print(cut)
# print(loop)
# print(A) #ok
ans = sum(cut)
N -= len(cut)

ans += sum(loop) * (N // len(loop))
ans += sum(loop[:N % len(loop)])
print(ans)

Submission status: Accepted

Solution code:
N,X,M = map(int,input().split())
ans = X
N -= 1
divs,loop = [],[]
x = X**2%M
for _ in range(M):
    if x%M != 0:
        if x%M in divs:
            loop = divs[divs.index(x%M):]
            start = divs[:divs.index(x%M)]
            break
        else:
            divs.append(x%M)
            x = x**2
            x %= M
    else:
        start = divs
        break
if N >= len(start):
    ans += sum(start)
    if loop:
        cycle = (N-len(start))//len(loop)
        remain = (N-len(start))%len(loop)
        ans += sum(loop)*cycle + sum(loop[:remain])
else:
    ans += sum(start[:N])
print(ans)

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
list = [0] * M
a = []
A = X
for i in range(N):
    if list[A] != 0:
        break
    list[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:
#周期m以下

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

used = [0]*(m+1)
used_list=[]
pre=x

flag0=False
s=-1;t=-1
for i in range(m+1):
    if pre==0:
        flag0=True
        break
    now=(pre*pre)%m
    if used[pre]:
        s=used[pre]
        break
    used[pre]=i
    used_list.append(pre)
    pre=now
    
l=len(used_list[s:])
try:
    ans=sum(used_list[:s])+sum(used_list[s:])*((n-s)//l)+sum(used_list[s:s+(n-s)%l])
    if not flag0:
        print(ans)
    else:
        print(sum(used_list))
except:
    print(sum(used_list))

Submission status: Accepted

Solution code:
N,X,M=map(int,input().split())
a=X
ls=[X]
point=N
for i in range(N):
  a=a*a%M
  if a in ls:
    point=ls.index(a)
    break
  else:
  	ls.append(a)
initial=len(ls[:point])
cycle_len=len(ls[point:])
cycle_sum=sum(ls[point:])
cycles=(N-initial)//cycle_len
cycles_rem=(N-initial)%cycle_len
print(sum(ls[:point])+cycles*cycle_sum+sum(ls[point:point+cycles_rem]))

Submission status: Accepted

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

id = [-1] * M
a = []
l = 0
tot = 0
while id[X] == -1:
    a.append(X)
    id[X] = l
    l += 1
    tot += X
    X = X ** 2 % M

c = l - id[X]
s = 0
for i in range(id[X], l):
    s += a[i]

ans = 0
if N <= l:
    for i in range(N):
        ans += a[i]
else:
    ans += tot
    N -= l
    ans += s * (N // c)
    N %= c
    for i in range(N):
        ans += a[id[X] + i]

print(ans)

Submission status: Accepted

Solution code:
# happendはsetで保持しておき，roopはlistで保持しておく
N, X, M = map(int, input().split())  # modMは10**5以下が与えられる
happend = set()
A = [X]
MOD = M
# 第1~N項まで計N項の和をもとめる
start = 0
for _ in range(N-1):
    if A[-1]**2 % MOD not in happend:
        happend.add(A[-1]**2 % MOD)
        A.append(A[-1]**2 % MOD)
    else:
        start = A.index(A[-1]**2 % MOD)
        break

roop_count = (N-start)//len(A[start:])

ans = sum(A[:start]) + sum(A[start:])*roop_count + sum(A[start:start+(N-start) % len(A[start:])])
# print(A[:start], A[start:], A[start:start+(N-start) % len(A[start:])])
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N, X, M = map(int, input().split())
NN = N
li = []
isused = [False] * M
while isused[X] == False and N != 0:
    li.append(X)
    isused[X] = True
    X = (X ** 2) % M
    N -= 1
    
if N == 0:
    print(sum(li))

elif N != 0 and X in li:
    l = len(li)
    s = li.index(X)
    T = l - s
    q = (NN - s) // T
    r = (NN - s) % T
    print(sum(li) + sum(li[i] for i in range(s, len(li))) * (q-1) + sum(li[i] for i in range(s, s + r)))

Submission status: Accepted

Solution code:
n, x, m = map(int, input().split())
s = x
a = x
note = [0] * m
note[a] += 1
seq = []
for i in range(n-1):
    seq.append(a)
    a = a**2 % m
    if note[a] > 0:
        ind = seq.index(a)
        l = len(seq[ind:])
        n -= len(seq[:ind])
        syo, r = divmod(n, l)
        s = s + sum(seq[ind:]) * (syo-1)
        if r != 0:
            for j in range(ind, ind+r):
                s += seq[j]
        print(s)
        exit()
    if a == 0:
        print(s)
        exit()
    note[a] += 1
    s += a
print(s)

Submission status: Accepted

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

l = [X]
a = X
k = 0
for i in range(M):
    if a**2%M not in l:
        l.append(a**2%M)
        a = a**2%M
    else:
        k = l.index(a**2%M)
        break
sum = 0
for i in range(k,len(l)):
    sum += l[i]

ans = 0

ans += ((N-k)//(len(l)-k))*sum

for i in range(min(k,N)):
    ans += l[i]

for i in range(1,(N-k)%(len(l)-k)+1):
    ans += l[k+i-1]

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import collections
import copy
import decimal
from collections import deque 
from functools import reduce
from itertools import product
from itertools import combinations
N, X, M = map(int, input().split())
# X^2がMより大きい場合はMで割った余り、小さければそのままを返却
def f(X, M):
    if X**2 >= M:
        return X**2 % M
    else:
        return X**2
appear = np.full(M, -1)
seq = []
fx = X
appear[fx] = 0
seq.append(fx)
for i in range(1, N):
    fx = f(fx, M)
#     print(fx, appear[fx])
    if appear[fx] != -1:
        loop_st = appear[fx]
        loop_en = i
        break
    seq.append(fx)
    appear[fx] = i
seq.insert(0, 0)
seq_sum = np.cumsum(seq)

if N <= len(seq)-1 :
    print(seq_sum[N])
else:
    # ループの前まで
    lp_b = seq_sum[loop_st-1]
    # ループしている個数
    loop_num = (len(seq_sum)-1) - loop_st
    qu = (N-(loop_st)) // loop_num
    mo = (N-(loop_st)) % loop_num
    lp_sum = (seq_sum[-1] - seq_sum[loop_st]) * qu
    lp_en = seq_sum[loop_st+mo] - seq_sum[loop_st-1]
    print(lp_b+lp_sum+lp_en)

Submission status: Accepted

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

pt = [[0] * (M+100) for i in range(70)]
to = [[0] * (M+100) for i in range(70)]
for i in range(M+1):
    to[0][i] = (i*i) % M
    pt[0][i] = i

for i in range(65):
    for j in range(M+1):
        to[i+1][j] = to[i][to[i][j]]
        pt[i+1][j] = pt[i][j] + pt[i][to[i][j]]

ans = 0
for i in range(60):
    if (N>>i)&1:
        ans += pt[i][X]
        X = to[i][X]

print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
def solve(N,X,M):
    seen=set()
    order_seen=[]
    while X not in seen:
        seen.add(X)
        order_seen.append(X)
        X=f(X,M)
    pos=order_seen.index(X)  # Find position of when the cycle begins
    if pos>N:  # If position is greater than N, then we know we are not going to include any values from the cycle.
        return sum(order_seen[:N])
    terms_before_cycle=order_seen[:pos]
    sum_terms_before_cycle=sum(terms_before_cycle)
    ans=sum_terms_before_cycle
    terms_in_cycle=order_seen[pos:]
    sum_cycle=sum(terms_in_cycle)
    length_cycle=len(terms_in_cycle)
    number_remaining_terms=N-pos
    mult_factor=(number_remaining_terms)//length_cycle
    ans+=(sum_cycle*mult_factor)
    numb_remain=(number_remaining_terms)%length_cycle
    ans+=sum(terms_in_cycle[:numb_remain])
    return ans

# The function for the recurrence relation.  A_n+1=A_n^2%M
def f(A,M):
    return pow(A,2,M)

N,X,M=readMap()
print(solve(N,X,M))