公式解説と同様、\(\displaystyle \sum_{j=1}^{i-1}2^j \gcd (A_i, A_j)\) を計算する方法を考えます。

列 \(\delta_x\) を \((\delta_x)_i = \begin{cases} 1 \quad (i = x) \\ 0 \quad (i \neq x)\end{cases}\) で定めます。

列に対する線形変換 \(Z\) を \(\displaystyle (Zv)_d = \sum_{k \geq 1} v_{kd}\) で定めると(*)、\(Z^{-1}(Z \delta_x \circ Z \delta_y) = \delta_{\gcd(x,y)}\) が成り立つという典型的なテクニックが存在します (GCD 畳み込み)。 ただし、\(\circ\) は各点で積を取る演算です。

これを用いて求める式を表現します。 列 \(w\) を \(w_i = i\) で定めると以下のようになります。

\[\begin{aligned} \sum_{j=1}^{i-1}2^j \gcd (A_i, A_j) &= \sum_{j=1}^{i-1} \left\langle w, Z^{-1} \left( Z 2^j\delta_{A_j} \circ Z \delta_{A_i} \right) \right\rangle \\ &= \sum_{j=1}^{i-1} \left\langle (Z^{-1})^{\top} w, Z 2^j\delta_{A_j} \circ Z \delta_{A_i} \right\rangle \\ &= \left\langle (Z^{-1})^{\top} w, \sum_{j=1}^{i-1} Z 2^j\delta_{A_j} \circ Z \delta_{A_i} \right\rangle \\ &= \sum_{k \geq 1} \Biggl ( (Z^{-1})^{\top} w \Biggr)_k \Biggl( \sum_{j=1}^{i-1} Z 2^j\delta_{A_j} \Biggr)_k \Biggl( Z \delta_{A_i} \Biggr)_k \end{aligned}\]

と表されます。 式変形には線形性と、転置と内積の関係を用いました。

\((Z^{-1})^{\top}\) は倍数部分に足し込む変換の逆変換であり \(\mathrm O(\max A \log \log \max A)\) で計算できます。 \(Z \delta_{A_i}\) が \(A_i\) の約数の部分にしか非零成分を持たないことから、

• \(\displaystyle \sum_{k \geq 1} \cdots\) 部分の計算
• \(i\) をインクリメントした際の \(\displaystyle \sum_{j=1}^{i-1} Z 2^j\delta_{A_j}\) の更新

はいずれも \(\mathrm O (d(A_i))\) の時間計算量で実行できます。

*: 無限和を含むため、厳密に定義するためには条件を付ける必要があります。