Lately, i was solving this problem and the editorial provide this solution
can someone tell me what's the time complexity of the getDivisors()?
I think it's 2^n pick-or-leave that's why I wonder !
if a, b like 2^29 it will generate all possibilities which will not fit in time!
~~~~~
vector<int> divisors;
void getDivisors(int ind = 0, int res = 1) {
if (ind == (int) factors.size()) {
divisors.push_back(res);
return;
}
for (int i = 0; i <= factors[ind].second; i++) {
getDivisors(ind + 1, res);
res *= factors[ind].first;
}
}
~~~~~
