It is easy to prove that for any number n and bases > sqrt(n) there will be no representation where the number will contain 0 at its second least significant digit. So it is enough to check for bases ≤ sqrt(n).

As there are 106 test cases, you have to precalculate the results to avoid TLE.

Time complexity: O(n × sqrt(n) + Q) where Q is the number of queries and n is the highest possible number in the query.

Contributors

Statistics

72% Solution Ratio
EgorKulikovEarliest, Jan '20
Angsuman.269745Fastest, 0.1s
Mah1r_Lightest, 5.4 MB
mdvirusShortest, 335B
Toph uses cookies. By continuing you agree to our Cookie Policy.