BASE - Editorial

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.