まず結論を書きます。

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

を満たすように \(F_1, F_2, \dots\) を定義します。すると、

\[\mathrm{LCM}(R_{A_1}, R_{A_2}, \dots, R_{A_n}) = \prod_{1 \leq i \leq n かつ d \vert A_i を満たす i が存在する d} F_d\]

が成り立ち、これが全てです。以降ではこの事実を証明していきます。

まず、レピュニットの重要な性質を次に挙げます。

補題 1

全ての正整数 \(n, m\) について \(\gcd(R_n, R_m) = R_{\gcd(n,m)}\) が成り立つ。

(補題 1 の証明) \(n=m\) の時は明らかに成り立ちます。\(n \gt m\) を仮定して一般性を失いません。このとき、

\[ \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} \]

という式変形により \(\gcd(R_n, R_m) = \gcd(R_{n-m}, R_m)\) を得ます。この事実に互除法の性質を合わせると \(\gcd(R_n, R_m) = R_{\gcd(n,m)}\) が従います。(補題 1 の証明終わり)

直感的な説明

上述の通り、\(R_n\) は非常に良い性質を持ちます。例えば \(\gcd(R_{12}, R_{30}, R_{24}) = R_6\) です。
ここで \(R_n = \prod_{d \vert n} F_d\)、例えば \(R_6 = F_1 F_2 F_3 F_6\) を満たす \(F_n\) を用いて \(R_n\) を表すと、例えば

\[ \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} \]

であり、この \(3\) つに共通する \(F_1, F_2, F_3, F_6\) の積が GCD ということになります。そうすると LCM については逆に和集合を取って

\[\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}\]

のようになるだろうと予想されます。
この直感的な予想を式変形を用いて証明します。

• 想定解はいくらか大仰な式変形になってしまいました。詳細は割愛しますが、「直感的な説明」にある議論を深めることで証明する方法もあり、そちらの方が自然に感じる方も多そうです。興味がある方は考えてみてください。

証明

補題 2

正整数の集合 \(S\) に対して次式が成り立つ。

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

(補題 2 の証明) 両辺への寄与を素数ごとに考えると、非負整数の集合 \(S\) に対して

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

が証明できれば命題が証明できることがわかります。
\(S\) の要素を降順に並べた列が \((s_1,s_2,\dots,s_n)\) であるとします。\(T\) の最小値が \(s_i\) であるものに対する \((-1)^{\vert T \vert - 1}\) の総和を考えると、

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

になることがわかります。(\(\lbrack \mathrm{cond} \rbrack\) は \(\mathrm{cond}\) が真の時 \(1\) を、偽の時 \(0\) を取る関数) よって

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

が成り立ち、命題は示されました。(補題 2 の証明終わり)

補題 1,2 を元に解法を証明します。(以降では集合に対する LCM を計算するので \(A_i\) は互いに異なるとしますが、そうでない場合も同様に証明できます) \(\mathrm{LCM}(\lbrace R_{A_1}, \dots, R_{A_n} \rbrace)\) を計算すると次のようになります。

\[ \begin{aligned} \mathrm{LCM}(\lbrace R_{A_1}, \dots, R_{A_n} \rbrace) &= \prod_{\emptyset \neq T \subseteq \lbrace R_{A_1}, \dots, R_{A_n} \rbrace} \mathrm{pow}(\gcd(T), (-1)^{\vert T \vert - 1}) \\ &= \prod_{\emptyset \neq T \subseteq \lbrace A_1,\dots,A_n \rbrace} \mathrm{pow}(R_{\gcd(T)}, (-1)^{\vert T \vert - 1}) \\ &= \prod_{\emptyset \neq T \subseteq \lbrace A_1,\dots,A_n \rbrace} \mathrm{pow}(\prod_{d \vert \gcd(T)} F_d, (-1)^{\vert T \vert - 1}) \\ &= \prod_d \mathrm{pow}(F_d, \sum_{\emptyset \neq T \subseteq \lbrace A_1,\dots,A_n \rbrace, d \vert \gcd(T)} (-1)^{\vert T \vert - 1} ) \\ &= \prod_d \mathrm{pow}(F_d, (-1) (1-1)^{\# \lbrace i \text{ s.t. } d \vert A_i\rbrace} + 1) \\ &= \prod_{1 \leq i \leq n かつ d \vert A_i を満たす i が存在する d} F_d \end{aligned} \]

以上より冒頭の式は示されました。

計算量は全てを適切に実装すると \(M = \max(N, \max(A))\) として \(\mathrm{O}(M \log \log M + \log \mathrm{mod})\) で問題を解くことができて非常に高速です。いくらかラフに書くと \(\mathrm{O}(M^{1.5})\) 程度になりますがこれでも十分高速です。