結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー titia
提出日時 2023-05-26 23:15:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,071 ms / 3,000 ms
コード長 898 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 76,964 KB
最終ジャッジ日時 2024-12-25 10:43:55
合計ジャッジ時間 17,338 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N=int(input())

mod=998244353

x=N
import math 
L=int(math.sqrt(x))

FACT=dict()

for i in range(2,L+2):
    while x%i==0:
        FACT[i]=FACT.get(i,0)+1
        x=x//i

if x!=1:
    FACT[x]=FACT.get(x,0)+1

Y=[]
for i in range(1,L+2):
    if N%i==0:
        Y.append(i)
        Y.append(N//i)

Y=sorted(set(Y))

DP=[0]*len(Y)
DP[0]=1

SET=set(FACT)

def fact2(x):
    F=dict()
    for s in SET:
        while x%s==0:
            F[s]=F.get(s,0)+1
            x=x//s
    return F

for i in range(1,len(Y)):
    x=Y[i]
    FX=fact2(x)
    for j in range(i):
        y=Y[j]
        if x%y!=0:
            continue
        FY=fact2(y)

        score=1
        for f in FY:
            if f in FX and FX[f]==FY[f]:
                score=score*(FX[f]+1)%mod

        #print(x,y,score,FX,FY)

        DP[i]=(DP[i]+DP[j]*score)%mod

print(DP[-1])
0