PROBLEM LINK:
Author: Ke Bi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
Contest Admin: Praveen Dhinwa
DIFFICULTY:
Easy
PREREQUISITES:
Backtracking, enumeration, precomputation, polydivisible numbers
PROBLEM:
A number is easy in base b if every prefix of i digits is divisible by i when interpreted as a base-b number. Given b and d, how many d-digit easy numbers are there in base b?
QUICK EXPLANATION:
There are only a few easy numbers per base, so enumerate them all.
But there may still be too many such numbers to be enumerated within the time limit, so simply enumerate them offline and then hardcode the results in your code.
EXPLANATION:
These numbers are known better in the literature as polydivisible numbers.
One important property of polydivisible numbers is that every prefix of a polydivisible number is also polydivisible (in that base). This allows us to enumerate polydivisible numbers using a simple recursion / backtracking procedure, which constructs polydivisible numbers from left to right:
def construct_polydivisibles(base, length, current):
// 'base' is the base we're at
// 'length' is the length of the number we have constructed so far
// 'current' is the number we have constructed so far
// count this polydivisible number
counts[base][length]++
// try appending a digit.
for digit in 0..base-1:
newnumber = current * base + digit
if newnumber % (length+1) == 0:
construct_polydivisibles(base, length+1, newnumber)
Here are a few notes:
-
The initial call to this is
construct_polydivisibles(b, 1, digit)for everydigitfrom1tobase-1. Note thatdigitcannot be zero initially, because we only count positive integers, and also youāll run into an infinite loop of appending 0 s if you do. -
For b > 8,
currentexceeds the bounds of along long. In this case, we need to representcurrentusing something else, for example, a string of digits in base ābaseā. To computenewnumber, we simply append a digit at the end. To computenewnumber % (length+1), we have to perform a loop:def mod(base, current, value):
// compute ācurrentā modulo āvalueā, where ācurrentā is
// a string of digits in base ābaseā// Horner's rule to evaluate the number result = 0 for i = 0..current.length-1: result = (result * base + current[i]) % value return result
This runs in time proportional to the number of digits, and itās essentially just Hornerās rule.
- Notice that thereās no stopping condition in the code, which means it will run forever if there are an infinite number of polydivisible numbers. In that case, we could stop when we reach the length d, so it doesnāt run forever. Also, you could use a more BFS-like procedure instead of this DFS code to enumerate the numbers in increasing order, and then stop completely once we reach a number with length greater than d.
But actually, thereās another important property of polydivisible numbers: There are only a finite number of them for base b \le 16. Why is that? I donāt think thereās any deep reason, other than that as we construct the number, it becomes increasingly hard to find a valid digit to append, because length keeps on increasing, while our pool of digits stays the same: {0, 1, 2, ..., base-1}, and since we require that current % length == 0 every time, the proportion of digits that fit that criterion simply approaches zero. This is not a proof though; itās just a heuristic. But if you try running construct_polydivisibles on base 10 for example, youāll find that there are only 20456 positive polydivisible numbers! (The largest of which is 3608528850368400786036725.) And fortunately, this is also true for any other base \le 16. Try running construct_polydivisibles for every base up to 16 to get the following data:
Base # polydiv Max polydiv (in the given base)
2 2 10
3 15 200220
4 37 2220301
5 127 4022042200
6 323 52323000003
7 1067 222255000033402606
8 2568 56147660642432202
9 8380 8831805708264668401762
10 20456 3608528850368400786036725
11 58173 594028289306446AA604A08202
12 148058 606890346850BA6800B036206464
13 441492 420A26CC95820CCCA8B346A80062A0996C3
14 916145 BA280A76B2D29008B63A784800604A1A6476CC0
15 3722967 6A99598095665B0EAC8A95000C9960B50AAC42
16 8407789 FAE06678C2E884607EB8B4E0B0A0F0603420342
As you can see, the length of the longest polydivisible number per base isnāt constantly increasing. Itās quite random actually, though thereās a clear trend that itās increasing, primarily because the higher the base, the more digits that we have, so the higher our chances of finding valid digits to append.
So given this, a new simple strategy would be the following:
- Enumerate all polydivisible numbers. Precompute the maximum length per base, and the counts per base and length.
- For a given test case (b,d), check if d is greater than the maximum length for base b. If so, the answer is 0. Otherwise, print the stored count for base b and length d.
This greatly simplifies the range of interesting test cases! Note that the longest polydivisible number has 39 digits, which means the answer is 0 for d \ge 40!
But actually, the enumeration algorithm above is too slow to pass the time limit (unless you really, really optimize). So what do we do? We simply compute all answers offline, and then simply hardcode the answers in our submission!
And finally, thereās an interesting optimization in our enumeration algorithm. Notice that computing current % (length+1) is slow when current is a string of digits. But notice that the longest valid polydivisible number here has 39 digits, which means we will only need to compute % for moduli \le 40. This means that instead of storing current as a string of digits, we can just store it modulo \operatorname{lcm}(1,2,3,4,\ldots,40) = 5342931457063200! This makes the computation of % much quicker!
Time Complexity:
O(1)