PROBLEM LINK:Author: Kevin Charles Atienza Tester: Kevin Charles Atienza Editorialist: Vaibhav Tulsyan DIFFICULTY:EasyMedium PREREQUISITES:None PROBLEM:Given an integer $N$, find the number of integer bases $B$, such that the base$B$ representation of $N$ starts with a $1$. QUICK EXPLANATION:In base $B$, a number with $(K + 1)$ digits is in the range $[B^K, B^{(K + 1)})$. It starts with the digit $1$ if and only if it is in the range $[B^K, 2.B^K)$. Hence, for a base $B$ containing $(K + 1)$ digits, we need to find the no. of bases satisfying $floor({N/2}^{1/K}) \lt B \le N^{1/K}$. The different lengths of bases we need to check are $log_2(N)$, which is at max $40$. EXPLANATION:For $N = 0$, the answer is $0$, as no base $B$ representation of $0$ can start with $1$. For $N = 1$, the answer is "INFINITY", as $1$ written in any base $B$ starts with a $1$. Naive Approach: We can iterate over all bases in the range $[2, N]$, find the base$B$ representation of $N$ and check if it starts with $1$. Pseudocode:
This approach is too slow and would pass only Subtask 1. Expected Solution: Let's say that a base in consideration $B$ contains $(K + 1)$ digits. Such a base can represent numbers in range: $[B^K, B^{(K + 1)})$. We want the first digit to be equal to $1$. A number $N$ written in base $B$ starts with $1$ if and only if it is in the range $[B^K, 2.B^K)$. This implies, $floor({N/2}) \lt B^K \le N$, which is equivalent to $floor({N/2}^{1/K}) \lt B \le N^{1/K}$. For each value of $K$, we can now find out the bases $B$ that we require  that is, the values of $B$ satisfying this inequality. Since the maximum value of $N$ in the given problem is $10^{12}$, the highest length of the base that is possible is at most $40$. Pseudocode:
Complexity: $O(T * (40.\alpha))$, where $\alpha$ is the complexity of the $pow(a, b)$ function, where $b$ is a floating point number less than $1$. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution can be found here. Tester's solution can be found here. Editorialist's solution can be found here. asked 13 Mar '17, 20:31
