Editorial for DMOPC '15 Contest 5 P4 - Steins;Number

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Since $\log_3(10^{18}) \approx 38$ ~\log_3(10^{18}) \approx 38~, there are over $2^{37}$ ~2^{37}~ Steins;Numbers within the given constraints, so generating all Steins;Numbers will only give us 20 points.

For full points, we need to make the observation that a Steins;Number can be represented in binary where each bit denotes whether the corresponding power is part of the sum. Using these bitmasks, we can use binary search to find $A$ ~A~, the smallest Steins;Number that is greater than or equal to $L$ ~L~, and $B$ ~B~, the largest Steins;Number that is less than or equal to $R$ ~R~. The answer is then $B-A+1$ ~B-A+1~.

Time Complexity: $\mathcal{O}(Q \log^2 N)$ ~\mathcal{O}(Q \log^2 N)~

Comments

There are no comments at the moment.