Internet Problem Solving Contest

IPSC 2008

Solution to Problem K – K Equal Digits

Let’s start with a few useful observations:

The most obvious approach is to simply try all the possible lengths of the number (up to N, of course). This can be done, for example, by considering the following sequence: a0 = 0, an+1 = (10an + D)(modd). Clearly, the n-th term of the sequence is equal to the remainder we get if we divide number consisting of n digits D by d. We’re looking for values of n, such that an = 0. As the terms of the sequence can attain only d different values, the sequence will eventually become periodic. Furthermore, if there is some p > 0, such that ap = 0, an will be zero whenever n is divisible by p. The least such number p will be the “period” of this sequence.

Thus, in order to find the largest n N, such that an = 0, we just need to find the period of the sequence (or find that the sequence is not equal to zero for any n > 0). For small values of d, this can be done in a straightforward way – let’s just evaluate an for all n and stop as soon as we find the first one with an = 0 or we exceed d (the sequence will necessarily become periodic in at most d steps, as there are only d possible remainders modulo d).

For large values of d, this approach becomes too slow, though. The key to a faster solution lies in another useful observation. Let A and B be numbers with no common divisor greater than 1. Let the period of (an modulo A) be P, and the period of (an modulo B) be Q. Then we can conclude that the period of (an modulo AB) is lcm(P,Q), the least common multiple of P and Q.

In particular, if d = p1e1p2e2pkek with pi representing distinct primes, finding the period of an modulo d can be done by finding the period modulo each piei and taking the least common multiple of all these periods. And yes, before you ask, all the numbers in the input files had only small powers of primes in their prime factorizations, so this approach could be applied to them.

In fact, it’s possible to improve this approach even further by realizing that we can use the information about the period of an modulo pe to find the period of an modulo pe+1 in just p steps. This optimization was not necessary here.