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

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)$ $O (Q \log^{2} N)$

Comments

There are no comments at the moment.