In short, this problem asks “enumerate the divisors of \(N\).”

Since the constraints are large, it won’t finish in time if you try all \(1\)-\(N\). Let us consider the way to reduce the time complexity.

“That \(d\) is a divisor of \(N\)” and “that \(N/d\) is a divisor of \(N\)” are equivalent. Therefore, the divisor of \(N\) larger than \(\sqrt{N}\) always make a pair with another divisor of \(N\) smaller than \(\sqrt{N}\).

For instance, when \(N = 20\), \(20\) makes a pair with \(1\), \(10\) with \(2\), and \(5\) with \(4\).

Therefore, this problem could be solved in a total of \(O(\sqrt{N})\) time by exhaustively searching all integers up to \(\sqrt{N}\) while recording both \(d\) and \(N/d\) as its divisors.

Depending on the implementation, you have to be careful when \(N\) is a square number.

In the sample code below, a set is used, so the total time complexity is \(O(\sqrt{N} + k \log k)\), where \(k\) is the number of divisors.

Sample Code (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;
}