# Internet Problem Solving Contest

## Solution to Problem K – K Equal Digits

Let’s start with a few useful observations:

• Rather than considering all the divisors di at the same time, we start can by finding the largest repetitive number divisible by each of them separately and then simply pick the biggest one. Thus, from now we’ll try to solve a modified problem: “For given N and d, find the biggest repetitive number divisible by d, having at most N digits.”
• With the exception of the trivial answer 1 0, there are only nine digits we need to consider for the numbers, so we can split each problem into nine subproblems of the form: “For given N, d and D, find the biggest number with at most N digits, consisting solely of digit D”.

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.