Contest Duration: - (local time) (100 minutes) Back to Home
Official

## 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.

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;
}


posted:
last update: