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} = 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_{1}^{e1}p_{2}^{e2}…p_{k}^{ek} 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}^{ei} 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.