|
|
back to boardCan somebody tell me how solve this problem? what is test19? maybe some wrong in test19 It can be solved using backtracking :) can anyone tell me what algo for this problem > can anyone tell me what algo for this problem
I can, though my approach wasn't so easy.
I used precalculations. My way is to generate all pairs (N, P), where P = 1, 2, ... - complexity of number and N - such minimal number, that has exactly P divisors.
How to do this with such large inputs? Solve another problem: recover N, if you know P. I used backtrack there, but still I'm wondering whether there is a more beautiful way. First I wrote a recursive function that tries all v=2^a * 3^b * 5^c * 7^d * 11^e * ... with a>=b>=c>=... It generates +- a million possibilities and takes around 300 ms for each case. So I got TLE with 100 cases.
Then I wrote code that reads all the n values and sort them. Then I call the recursive function with 10^18. I added a binary search to it that finds the smallest n greater or equal to v and update the best result for it. When the recursive function returns, I update the results for the larger values of n with the smaller results. And then I output the results in the same order as the input.
All in less that 50 lines of C++. I think u can safely assume that that there is no number with power>10
so 10>=a>=b>=c>=d... and now I think u will get AC without doing anything else.
Plus small small optimisation.. like breaking at a point if current no. > query(which is obvious to do so) and other such small small optimisation will do.
Other thing is to check if ur current no. doesnt exceed the long long range (u can only check by using log()...) Баур, эта задача решатся "в лоб" |
|
|
