公式解説にもあるように、\(\gcd(R_{n}, R_{m}) = R_{gcd(n, m)}\) が成り立ちます。

任意の \(k\) に対して、\(Z_{k} = \dfrac{\mathrm{lcm}(R_{A_{1}}, \dots , R_{A_{k}})}{\mathrm{lcm}(R_{A_{1}}, \dots , R_{A_{k - 1}})}\) が求まれば良いので、これを求めることを目標とします。

一般に、\(\dfrac{\mathrm{lcm}(x_{1}, \dots , x_{i}, y)}{\mathrm{lcm}(x_{1}, \dots , x_{i})}\) について、以下が成り立ちます。

\[\prod_{S\subset\{1, \dots , i\}}\gcd(\gcd_{j\in S}(x_{j}), y)^{-1^{|S|}}\]

これ以降 \(i = k - 1\) かつ \(x_{a} = R_{A_{a}}\) かつ \(y = A_{R_{k}}\) であるとします。

任意の \(a\) に対して「\(\gcd(\gcd_{j\in S}(x_{j}), y)^{-1^{|S|}}\) が \(R_{a}\) で割り切れるような \(S\) に対する \(|S|^{-1}\) の総和」が求まれば、約数包除することで、「\(\gcd(\gcd_{j\in S}(x_{j}), y)^{-1^{|S|}}\) が \(R_{a}\) であるような \(S\) に対する \(|S|^{-1}\) の総和」が求められるので、\(Z_{k}\) が求まります。

\(\gcd(\gcd_{j\in S}(x_{j}), y)^{-1^{|S|}}\) が \(R_{a}\) で割り切れるような \(S\) に対する \(|S|^{-1}\) の総和について、以下が成り立ちます。

• \(a\) が \(A_{k}\) の約数でなければ \(0\)
• \(A_{i}\) が \(a\) で割り切れるような \(i\) が存在すれば\(0\)
• それ以外は \(1\)

以上の事実から \(Z_{k}\) が求まります。

\(A_{i}\) が互いに相異なれば演算回数は少なくとも \(\sum (A[i] の約数の数)^{2}\) 必要ですが、十分高速でした。

c++ 実装例