### PROBLEM LINK:

**Author:** Kevin Charles Atienza

**Tester:** Kevin Charles Atienza

**Editorialist:** Vaibhav Tulsyan

### 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:

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

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:

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

```
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
```

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.