torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 180, C : Cream puff

問題概要

 正整数 $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;
}