結果
問題 | No.2318 Phys Bone Maker |
ユーザー |
|
提出日時 | 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 |
ソースコード
package mainimport ("fmt""sort")func main() {m := 998244353var n intfmt.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] = 1for 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 = 0break}if a == b {tmp *= (b + 1)if tmp > m {tmp %= m}}}dp[j] += tmpif 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 /= 2m[2]++}for i := 3; i*i <= n; i += 2 {for n%i == 0 {n /= im[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}