結果

問題 No.1781 LCM
コンテスト
ユーザー vwxyz
提出日時 2025-05-05 19:30:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,167 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 376 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 77,568 KB
最終ジャッジ日時 2025-05-05 19:30:58
合計ジャッジ時間 10,142 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 21 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Prime:
    def __init__(self,N):
        assert N<=10**8
        self.smallest_prime_factor=[None]*(N+1)
        for i in range(2,N+1,2):
            self.smallest_prime_factor[i]=2
        n=int(N**.5)+1
        for p in range(3,n,2):
            if self.smallest_prime_factor[p]==None:
                self.smallest_prime_factor[p]=p
                for i in range(p**2,N+1,2*p):
                    if self.smallest_prime_factor[i]==None:
                        self.smallest_prime_factor[i]=p
        for p in range(n,N+1):
            if self.smallest_prime_factor[p]==None:
                self.smallest_prime_factor[p]=p
        self.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]]

    def Factorize(self,N):
        assert N>=1
        factors=defaultdict(int)
        if N<=len(self.smallest_prime_factor)-1:
            while N!=1:
                factors[self.smallest_prime_factor[N]]+=1
                N//=self.smallest_prime_factor[N]
        else:
            for p in self.primes:
                while N%p==0:
                    N//=p
                    factors[p]+=1
                if N<p*p:
                    if N!=1:
                        factors[N]+=1
                    break
                if N<=len(self.smallest_prime_factor)-1:
                    while N!=1:
                        factors[self.smallest_prime_factor[N]]+=1
                        N//=self.smallest_prime_factor[N]
                    break
            else:
                if N!=1:
                    factors[N]+=1
        return factors

    def Divisors(self,N):
        assert N>0
        divisors=[1]
        for p,e in self.Factorize(N).items():
            pow_p=[1]
            for _ in range(e):
                pow_p.append(pow_p[-1]*p)
            divisors=[i*j for i in divisors for j in pow_p]
        return divisors

    def Is_Prime(self,N):
        return N==self.smallest_prime_factor[N]

    def Totient(self,N):
        for p in self.Factorize(N).keys():
            N*=p-1
            N//=p
        return N

    def Mebius(self,N):
        fact=self.Factorize(N)
        for e in fact.values():
            if e>=2:
                return 0
        else:
            if len(fact)%2==0:
                return 1
            else:
                return -1

def Multiplicative_Prefix_Sum(N,F,f,mod=0):
    Pr=Prime(int(N**.5))
    def Lucy_DP(N,F):
        f_1=F(2)-F(1)
        if mod:
            f_1%=mod
            inv_f_1=pow(f_1,mod-2,mod)
        dp={}
        Qn=[N]
        while Qn[-1]:
            Qn.append(N//(N//Qn[-1]+1))
        if f_1:
            for x in Qn:
                if x>1:
                    dp[x+1]=F(x+1)-F(2)
                    if mod:
                        dp[x+1]%=mod
                else:
                    dp[x+1]=0
            for p in Pr.primes:
                f_p=F(p+1)-F(p)
                if mod:
                    f_p%=mod
                for x in Qn:
                    if p*p>x:
                        break
                    if mod:
                        dp[x+1]-=(dp[x//p+1]-dp[p])*f_p%mod*inv_f_1%mod
                        dp[x+1]%=mod
                    else:
                        dp[x+1]-=(dp[x//p+1]-dp[p])*f_p//f_1
        else:
            for x in Qn:
                dp[x+1]=0
        return dp
    def Black_Algorithm(N,f,F_prime):
        P=[]
        x=1
        f_x=[[f(2,0,1)]]
        retu=f_x[-1][0]+F_prime[N+1]
        if mod:
            retu%=mod
        queue=[]
        for i,p in enumerate(Pr.primes):
            queue.append((p,i,1))
            queue.append((p,i,0))
        while queue:
            p,ip,t=queue.pop()
            if t==0:
                x*=p
                if P and P[-1][0]==p:
                    P[-1][1]+=1
                    P[-1][2]*=p
                    f_x[-1].append(f_x[-2][-1]*f(*P[-1]))
                else:
                    P.append([p,1,p])
                    f_x.append([f_x[-1][-1]*f(p,1,p)])
                if mod:
                    f_x[-1][-1]%=mod
                p,e,pe=P[-1]
                if mod:
                    retu+=f_x[-2][-1]*f(p,e+1,pe*p)%mod
                    retu+=f_x[-1][-1]*(F_prime[N//x+1]-F_prime[p+1])%mod
                    retu%=mod
                else:
                    retu+=f_x[-2][-1]*f(p,e+1,pe*p)
                    retu+=f_x[-1][-1]*(F_prime[N//x+1]-F_prime[p+1])
                for i in range(ip,len(Pr.primes)):
                    q=Pr.primes[i]
                    if x*q*q>N:
                        break
                    queue.append((q,i,1))
                    queue.append((q,i,0))
            else:
                x//=P[-1][0]
                P[-1][1]-=1
                P[-1][2]//=p
                f_x[-1].pop()
                if P[-1][1]==0:
                    P.pop()
                    f_x.pop()
        return retu
    F_prime=Lucy_DP(N,F)
    return Black_Algorithm(N,f,F_prime)

N,M=map(int,input().split())
mod=998244353
pow2N=pow(2,N,mod)
def F(x):
    return (x-1)*pow2N
pow_N=[pow(i,N,mod) for i in range(100)]
def f(p,e,pe):
    return pow_N[e+1]
ans=Multiplicative_Prefix_Sum(M,F,f,mod)
print(ans)
0