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.