結果

問題 No.2318 Phys Bone Maker
コンテスト
ユーザー yupooh
提出日時 2023-05-26 22:16:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 820 ms / 3,000 ms
コード長 1,046 bytes
コンパイル時間 926 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,468 KB
最終ジャッジ日時 2024-12-25 07:36:20
合計ジャッジ時間 9,669 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
n=int(input())
mod=998244353
l=[]
sn=int(n**0.5)+5
for i in range(1,sn):
  if i*i>n:
    break
  if n%i==0:
    l.append(i)
    if n//i!=i:
      l.append(n//i)
l.sort()
dp=[1]*len(l)
import math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
fac=factorization(n)
f=[]
for i,j in fac:
  f.append(i)
yaku=[[] for _ in range(len(l))]
for i in range(1,len(l)):
  now=l[i]
  for j in f:
    num=0
    while now%j==0:
      num+=1
      now//=j
    yaku[i].append(num)
for i in range(1,len(l)):
  for j in range(i+1,len(l)):
    if l[j]%l[i]==0:
      val=1
      for k in range(len(f)):
        if yaku[i][k]==yaku[j][k]:
          val*=(1+yaku[j][k])
      dp[j]+=(dp[i]*val)
      dp[j]%=mod
print(dp[-1])
0