結果

問題 No.2318 Phys Bone Maker
ユーザー ynm3nynm3n
提出日時 2023-06-01 02:30:04
言語 Go
(1.23.4)
結果
AC  
実行時間 651 ms / 3,000 ms
コード長 1,343 bytes
コンパイル時間 17,495 ms
コンパイル使用メモリ 233,568 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-28 14:27:29
合計ジャッジ時間 23,918 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
"fmt"
"sort"
)
func main() {
m := 998244353
var n int
fmt.Scan(&n)
ps := enumPrimeFactor(n)
divs := enumDivs(n)
x := len(divs)
cnts := make([][]int, x)
for i, d := range divs {
cnts[i] = make([]int, len(ps))
cnt := primeFactorization(d)
for j, p := range ps {
cnts[i][j] = cnt[p]
}
}
dp := make([]int, x)
dp[0] = 1
for i := 0; i < x; i++ {
for j := i + 1; j < x; j++ {
tmp := dp[i]
for k := range ps {
a := cnts[i][k]
b := cnts[j][k]
if a > b {
tmp = 0
break
}
if a == b {
tmp *= (b + 1)
if tmp > m {
tmp %= m
}
}
}
dp[j] += tmp
if dp[j] > m {
dp[j] %= m
}
}
}
ans := dp[x-1]
fmt.Println(ans)
}
func enumPrimeFactor(n int) []int {
ps := primeFactorization(n)
res := make([]int, 0, len(ps))
for p := range ps {
res = append(res, p)
}
sort.Ints(res)
return res
}
func primeFactorization(n int) map[int]int {
m := make(map[int]int)
for n%2 == 0 {
n /= 2
m[2]++
}
for i := 3; i*i <= n; i += 2 {
for n%i == 0 {
n /= i
m[i]++
}
}
if n != 1 {
m[n]++
}
return m
}
func enumDivs(n int) []int {
res := []int{}
for i := 1; i*i <= n; i++ {
if n%i > 0 {
continue
}
res = append(res, i)
if j := n / i; j != i {
res = append(res, j)
}
}
sort.Ints(res)
return res
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0