結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2019-05-08 09:02:04 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 892 bytes |
コンパイル時間 | 14,430 ms |
コンパイル使用メモリ | 229,312 KB |
実行使用メモリ | 27,136 KB |
最終ジャッジ日時 | 2024-07-02 00:25:55 |
合計ジャッジ時間 | 14,950 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
package mainimport ("fmt""math")func main() {var n, k int_, _ = fmt.Scan(&n, &k)// nまでの数字の素因数分解の結果pns := make([]map[int]int, n+1)for i := 2; i <= n; i++ {if pns[i] == nil {pns[i] = map[int]int{i: 1}for j := i * 2; j <= n; j += i {if pns[j] == nil {pns[j] = make(map[int]int)}m := jfor m%i == 0 {m /= ipns[j][i]++}}}// fmt.Println(i, pns[i])}// fmt.Println("n未満のkを満たした最大を探す")ans := 0maxDivisor := 0for i := n - 1; i >= 2; i-- {var l, d int // 約数の数のうちnと一致する個数, 約数の数for p, q := range pns[i] {l += int(math.Min(float64(pns[n][p]), float64(q)))d += q * (d + 1)}// fmt.Println(i, d, maxDivisor, pns[i])if k <= l && maxDivisor <= d {ans, maxDivisor = i, d}}fmt.Println(ans)}