要するに「\(N\)の約数を列挙してください」という問題です。

制約が大きいため、\(1\)～\(N\) まですべてを試していては間に合いません。計算量を減らす方法を考えましょう。

「\(d\) が \(N\) の約数である」ことと「\(N/d\) が \(N\) の約数である」ことは同値です。つまり、\(\sqrt{N}\) より大きな \(N\) の約数は、必ず \(\sqrt{N}\) より小さな \(N\) の約数と対になります。

例えば \(N=20\) のとき、\(20\) は\(1\) と、\(10\) は \(2\) と、\(5\) は \(4\) と対になります。

よって、\(\sqrt{N}\) までを全探索しながら、\(d\) と \(N/d\) を同時に約数として記録していくことで、\(O(\sqrt{N})\) の時間でこの問題を解くことができました。

実装によっては、\(N\) が平方数の場合に注意が必要です。

以下の解答例ではsetを使っているため計算量は約数の個数を \(k\) として \(O(\sqrt{N}+k\log k)\) になっています。

解答例(C++)

#include <bits/stdc++.h>
using namespace std;

int main(){
	long n;
	cin >> n;

	set<long> ans;
	for(long d=1;d*d<=n;d++){
		if(n%d==0){
			ans.insert(d);
			ans.insert(n/d);
		}
	}
	
	for(auto x:ans)cout << x << endl;
}