BASE - Editorial

dec16
editorial

#1

PROBLEM LINK:

Practice

Contest

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.