EZNO - Editorial

PROBLEM LINK:

Contest
Practice

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 every digit from 1 to base-1. Note that digit cannot 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, current exceeds the bounds of a long long. In this case, we need to represent current using something else, for example, a string of digits in base “base”. To compute newnumber, we simply append a digit at the end. To compute newnumber % (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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

2 Likes

A better way to prove this can be -

If the current number is x in base 10 then after we add a digit y(base 10) the number would become bx + y, where b is the base, now we want (bx + y) mod (current_length) = 0. Suppose current_length > b, then it is quite intuitive to see that there is at most 1 value of y, which would could satisfy the above equation.

Similarly, if current_length <= b, then there are at most ceil(b / current_length) many distinct possible values of y which could satisfy (b*x + y) mod (current_lenght) = 0.

Example - current_length = 3, x = 11, b = 10, then (10 x 11 + y) mod (5) = 0, is true for y = 1, 4, 7

Taking the product of all possible values for each current_length from 1 to b, gives us the maximum possible
number of distinct easy numbers possible of length b, which is -->

= ceil(b / 1) * ceil(b / 2) * … * ceil(b / b)

= roughly (b^b) / (b!)
= for b = 16, this comes out to be of the order 10^6.

And we already know that if current_length > b, then at most only one value of y would satisfy the equation. So whenever current_length > b, the answer would either remain the same or decrease.

So we have basically proved that the maximum upper bound of number of easy numbers of any length where b <= 16, is roughly 10^6.

Now the part as to why the number of easy numbers always reduces to 0 after d = 39, is according to me highly heuristics based approach as mentioned in the editorial. A better way would be to see it like this.
(b*x + y) mod (current_length) = 0, where current_length > b, now here possible values of y can be plugged from 0 to b - 1.

So the probability of having the correct y for a specific current_length in the range [0, b) is roughly = b / current_length.

So let us assume that k is the length were number of easy numbers left is exactly 1.

Then,

1e6 * (b/(b + 1)) * (b/(b + 2)) * (b/(b + 3)) * … * (b/k)) = 1

1e6 * ((b^(k - b)) / (k!/b!)) = 1

Here if we plug in b = 16, k comes out to be 40.755

So I guess this prooves a lot.

6 Likes

I have checked the tester’s solution. In the enumerate_good function, why did he use -curr%i in range?.

@shiva92 we want curr + d to be divisible by i, (-curr % i) is the smallest nonnegative integer such that curr + d is divisible by i.