Chokudai Contest002 解法
問題概要
109以下の整数を100個出力しろ。出力した数の約数の集合(重複は除く)の数が多いほど良い。
コメント
本番では高度合成数を適当にいくつか出力するくらいしか分からなかった。
のでTLに流れてた回答を見て解いた。解法1を本番中に思いつきたかった...
コンテストページ
Chokudai Contest 002 - Chokudai Contest 002 | AtCoder
解法
解法1:高度合成数×素数
約数が多い高度合成数に異なる素数をかけて結果が109を超えないものを出力。
すると250-1000個程度の約数をもつ高度合成数が選ばれるので35000-40000くらいの点数が出る
提出コード:Submission #965609 - Chokudai Contest 002 | AtCoder
ヒント2:
— chokudai(高橋 直大) (@chokudai) November 3, 2016
高度合成数、ってすごい約数が多い数があるらしいぞ!
例えば720720とかあったとしよう。これに適当な素数を掛けた場合、29を掛けた数、31を掛けた数、37を掛けた数……とかを考えたら、約数はいくつ出来るかな?和集合は?
#chokudai_002
解法2:約数が多い数を10000個ほど挙げて焼きなまし
色々調べながらやってみた
コード:https://gist.github.com/SoichiSumi/34fb428b9b07a2f6d8df209f35087d36
9e8 以上の整数を約数の個数が多い順に1万個くらい列挙して、焼きなました#chokudai_002
— えいたほ (@eitaho) November 3, 2016