Internet Problem Solving Contest

• Correct output – K1
• Correct output – K2
• C++ program solving both data sets

Let’s start with a few useful observations:

• Rather than considering all the divisors d_i 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: a₀ = 0, a_n+1 = (10a_n + 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 a_n = 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 a_p = 0, a_n 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 a_n = 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 a_n for all n and stop as soon as we find the first one with a_n = 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 (a_n modulo A) be P, and the period of (a_n modulo B) be Q. Then we can conclude that the period of (a_n modulo AB) is lcm(P,Q), the least common multiple of P and Q.

In particular, if d = p₁^e₁p₂^e₂…p_k^e_k with p_i representing distinct primes, finding the period of a_n modulo d can be done by finding the period modulo each p_i^e_i 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 a_n modulo p^e to find the period of a_n modulo p^e+1 in just p steps. This optimization was not necessary here.