# BASE - Editorial

#PROBLEM LINK:
[Practice][111]
[Contest][222]
**Author:** [Kevin Charles Atienza][4444]
**Tester:** [Kevin Charles Atienza][5555]
**Editorialist:** [Vaibhav Tulsyan][6666]
#DIFFICULTY:
Easy-Medium
#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$.
Pseudo-code:
<code>
if N == 0: return 0
if N == 1: return "INFINITY"
ans = 0
for base in [2..N]:
num = n
while num > 1:
num /= base
digit %= base
if digit == 1:
ans += 1
return ans
</code>
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$.
Pseudo-code:
<code>
if N == 0: return 0
if N == 1: return "INFINITY"
ans = 0
for length in [2..40]:
val = f(N, length) - f(N / 2, length)
ans += val
return ans
</code>
<code>
function f(N, length):
x = int(round(pow(N, 1 / length)))
while pow(x, length) < N: x += 1
while pow(x, length) > N: x -= 1
return x
</code>
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][333].
Tester's solution can be found [here][444].
Editorialist's solution can be found [here][555].
[111]: https://www.codechef.com/problems/BASE
[222]: https://www.codechef.com/DEC16/problems/BASE
~~<!-- [333]:
[444]:
~~[333]: https://www.codechef.com/DEC16/problems/BASE
[444]: https://www.codechef.com/DEC16/problems/BASE
[555]: ~~-->
~~https://www.codechef.com/DEC16/problems/BASE
[4444]: https://www.codechef.com/users/code_master01
[5555]: https://www.codechef.com/users/kevinsogo
[6666]: https://www.codechef.com/users/wittyceaser