Let us begin with the conclusion.

Define \(F_1, F_2, \dots\) such that:

\[R_n = \prod_{d \mid n} F_d\]

Then, the following holds:

\[\mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_n}) = \prod_{\substack{1 \leq i \leq n \text{ and } \\ \exists i \text{ such that } d \mid A_i}} F_d\]

This is everything. In what follows, we will prove this fact.

First, here is an important property of repunits.

Lemma 1

For all positive integers \(n, m\), we have \(\gcd(R_n, R_m) = R_{\gcd(n,m)}\).

(Proof of Lemma 1) This clearly holds when \(n = m\). Without loss of generality, assume \(n > m\). Then:

\[ \begin{aligned} \gcd(R_n, R_m) &= \gcd(R_n - R_m, R_m) \\ &= \gcd(R_{n-m} \times 10^m, R_m) \\ &= \gcd(R_{n-m}, R_m) \end{aligned} \]

By this transformation, we obtain \(\gcd(R_n, R_m) = \gcd(R_{n-m}, R_m)\). Combined with the properties of the Euclidean algorithm, this gives us \(\gcd(R_n, R_m) = R_{\gcd(n,m)}\). (End of proof of Lemma 1)

Intuitive Explanation

As stated above, \(R_n\) has very nice properties. For example, \(\gcd(R_{12}, R_{30}, R_{24}) = R_6\).
Here, if we express \(R_n\) using \(F_n\) that satisfies \(R_n = \prod_{d \mid n} F_d\), for example \(R_6 = F_1 F_2 F_3 F_6\), then:

\[ \begin{aligned} R_{12} &= F_1 F_2 F_3 F_4 F_6 F_{12} \\ R_{30} &= F_1 F_2 F_3 F_5 F_6 F_{10} F_{15} F_{30} \\ R_{24} &= F_1 F_2 F_3 F_4 F_6 F_8 F_{12} F_{24} \end{aligned} \]

The product of \(F_1, F_2, F_3, F_6\) that are common to these three becomes the GCD. Then for the LCM, we conversely take the union and expect:

\[\mathrm{LCM}(R_{12}, R_{30}, R_{24}) = F_1 F_2 F_3 F_4 F_5 F_6 F_8 F_{10} F_{12} F_{15} F_{24} F_{30}\]

We will prove this intuitive conjecture using algebraic manipulations.

• The intended solution involves somewhat elaborate algebraic manipulations. While I omit the details, there is also a method to prove this by deepening the argument in the “Intuitive Explanation,” which many might find more natural. Those interested should try thinking about it.

Proof

Lemma 2

For a set \(S\) of positive integers, the following equation holds:

\[\mathrm{LCM}(S) = \prod_{\emptyset \neq T \subseteq S} \mathrm{pow}(\gcd(T), (-1)^{|T| - 1})\]

(Proof of Lemma 2) Considering the contribution to both sides by each prime, we can see that if we can prove the following for a set \(S\) of non-negative integers:

\[\max(S) = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T| - 1} \min(T)\]

then the proposition can be proved.
Let \((s_1, s_2, \dots, s_n)\) be the sequence of elements of \(S\) arranged in descending order. Considering the sum of \((-1)^{|T| - 1}\) for those \(T\) whose minimum value is \(s_i\):

\[\sum_{0 \leq j < i} (-1)^j \binom{i-1}{j} = (1-1)^{i-1} = [i = 1]\]

(\([\mathrm{cond}]\) is a function that takes 1 when \(\mathrm{cond}\) is true and 0 when false.) Therefore:

\[\sum_{\emptyset \neq T \subseteq S} (-1)^{|T| - 1} \min(T) = s_1 = \max(S)\]

holds, and the proposition is proved. (End of proof of Lemma 2)

Based on Lemmas 1 and 2, we prove the solution. (In what follows, since we compute LCM over sets, we assume \(A_i\) are pairwise distinct, but the same can be proved when this is not the case.) Computing \(\mathrm{LCM}(\{R_{A_1}, \dots, R_{A_n}\})\) gives:

\[ \begin{aligned} \mathrm{LCM}(\{R_{A_1}, \dots, R_{A_n}\}) &= \prod_{\emptyset \neq T \subseteq \{R_{A_1}, \dots, R_{A_n}\}} \mathrm{pow}(\gcd(T), (-1)^{|T| - 1}) \\ &= \prod_{\emptyset \neq T \subseteq \{A_1,\dots,A_n\}} \mathrm{pow}(R_{\gcd(T)}, (-1)^{|T| - 1}) \\ &= \prod_{\emptyset \neq T \subseteq \{A_1,\dots,A_n\}} \mathrm{pow}(\prod_{d \mid \gcd(T)} F_d, (-1)^{|T| - 1}) \\ &= \prod_d \mathrm{pow}(F_d, \sum_{\emptyset \neq T \subseteq \{A_1,\dots,A_n\}, d \mid \gcd(T)} (-1)^{|T| - 1} ) \\ &= \prod_d \mathrm{pow}(F_d, (-1) (1-1)^{\#\{i \text{ s.t. } d \mid A_i\}} + 1) \\ &= \prod_{\substack{1 \leq i \leq n \text{ and } \\ d \mid A_i \text{ for some } i}} F_d \end{aligned} \]

Thus, the formula at the beginning is proved.

The time complexity, when everything is implemented appropriately, is \(O(M \log \log M + \log \mathrm{mod})\) where \(M = \max(N, \max(A))\), which is very fast. If written somewhat roughly, it becomes \(O(M^{1.5})\) or similar, which is still sufficiently fast.