結果
問題 |
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 main import ( "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 := j for m%i == 0 { m /= i pns[j][i]++ } } } // fmt.Println(i, pns[i]) } // fmt.Println("n未満のkを満たした最大を探す") ans := 0 maxDivisor := 0 for 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) }