C - Cream puff Editorial by evima
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.
#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;
}
posted:
last update: