結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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])