AtCoder Beginner Contest 180 C – Cream puff を解いた記録

問題の概要

シュークリームが\(N\)個ある．シュークリームを分割せずに同じ個数だけ分配できるような人数としてあり得るものをすべて求め，答えを昇順に出力せよ．

問題へのリンク

制約

• \(1 \leq N \leq 10^{12}\)
• \(N\)は整数

解法

人数が\(N\)を割り切るような数字（約数）であれば，シュークリームを各人に同じ個数だけ分配できます．よって\(N\)の約数を全列挙し，それを昇順に出力すればOKです．

とはいえ，\(1 \leq N \leq 10^{12}\)ですから\(1\)から\(N\)までの全ての整数で試し割りしたらTLEとなります．

ここで，「ある整数\(x\)が\(N\)の約数であるとき，\(N/x\)も\(N\)の約数である」という性質を使います．
\(\sqrt(N)\)より大きい約数は\(\sqrt{N}\)より小さい約数とセットで登場するので，\(1\)から\(\sqrt{N}\)までの整数で試し割りすれば全ての約数を列挙できます．
例えば\(N=18\)とすると，\(18\)は\(1\)と，\(9\)は\(2\)と，\(6\)は\(3\)とセットで登場します．

約数の全列挙ができたら，列挙した約数を昇順で出力するだけです．C++の場合はsetやmapで約数を記録しておくと楽です．

実装例

mapを使って約数を記録した場合は，このコードのように範囲for文を使うとキーの昇順で要素を取り出せます．

感想

私は様々な場面でmapを使って問題を解きます．今回もmapのお世話になりました．