問題概要
正整数 $N$ が与えられる.$N$ の約数を昇順に列挙せよ.
制約
- $1 \leq N \leq 10^{ 12 }$
解法
$N$ の約数 $p$ が存在したとします.このとき,$N = pq$ と書ける $q$ が存在し,変形して,$q$ は $q = \frac N p$ と求まります.更にこのとき,$\min( p, q ) \leq \sqrt N$ であることが確かめられます(そうではないと仮定すると,$pq > N$ になってしまいます).よって,$p, q$ の内の大きくない方になり得る値,すなわち,$\sqrt N$ 以下の整数をすべて試し,いわゆる素数判定のように試し割りを行っていくことで,調べるべき候補を $\Theta( \sqrt N )$ 個に減らせます.
そうして集まった約数たちを昇順にして重複を排除するのには,C++ であれば std::set を使うと楽かと思います.この場合は,求まった約数たちを set に突っ込んでから出すだけでよいことになります.操作回数が $O( \sqrt N )$ ですから,全体では $O( \sqrt N \log \sqrt N )$ 時間となります.
コード
int main() { IN( LL, N ); set< LL > res; for ( LL i = 1; i * i <= N; ++i ) { if ( N % i == 0 ) { res.insert( i ); res.insert( N / i ); } } copy( ALL( res ), OSI< LL >( cout, "\n" ) ); cout << flush; return 0; }