答えを \(R_1, R_2, \dots, R_N\) とします。また便宜上 \(R_0 = 0\) とします。すると動的計画法を用いた考察により、\(R_1, R_2, \dots, R_N\) は次の式で計算できることが分かります。

\[R_i = 2R_{i - 1} + \sum_{j=1}^{i-1} 2^j \gcd(A_i, A_j)\]

この式をそのまま用いて \(R\) を計算すると \(\mathrm{O}(N^2 \log \max(A))\) 掛かってしまうので高速化が必要です。

実は上式はトーシェント関数 \(\varphi(n)\) を利用すると高速化が可能です。トーシェント関数とは次式を満たす関数です。(ここで \(d \vert n\) は \(d\) が \(n\) の約数であることを意味します。)

• 全ての正整数 \(n\) に対して \(\sum_{d \vert n} \varphi(d) = n\) が成り立つ。

トーシェント関数を用いると次の変形が出来ます。(ここで \([ \text{cond} ]\) は \(\text{cond}\) が真ならば \(1\) 、偽ならば \(0\) を取る関数)

\[ \begin{aligned} \gcd(n, m) &= \sum_{d \vert \gcd(n, m)} \varphi(d) \\ &= \sum_{d \vert n, d \vert m} \varphi(d) \\ &= \sum_{d \vert n} \varphi(d) [d \vert m] \end{aligned} \]

\[ \begin{aligned} &\sum_{j=1}^{i-1} 2^j \gcd(A_i, A_j) \\ &= \sum_{j=1}^{i-1} 2^j \sum_{d \vert A_i} \varphi(d) [d \vert A_j] \\ &= \sum_{d \vert A_i} \varphi(d) \sum_{j=1}^{i-1} 2^j [d \vert A_j] \end{aligned} \]

この式を利用すれば \(R_1, R_2, \dots, R_N\) の計算を \(\mathrm{O}(\max(A) + \sum_{i=1}^N d(A_i))\) (\(d(n)\) は \(n\) の約数の個数を意味する関数) で行う DP を導出できます。すなわち次の通りです。

• はじめ \(s = (s_1, s_2, \dots, s_{\max(A)})\) を \(0\) 初期化された列とする。
• \(i = 1, 2, \dots, N\) に対して次の操作を行う。
  • \(R_i = 2 \times R_{i-1} + \sum_{d \vert A_i} \varphi(d) s_d\) とする。
  • その後、\(d \vert A_i\) を満たす \(d\) に対して \(s_d\) に \(2^i\) を加算する。

この DP ではあらかじめ \(1, 2, \dots, \max(A)\) に対する約数の列挙および \(\varphi(1), \varphi(2), \dots, \varphi(\max(A))\) の列挙が必要となりますが、どちらも \(\mathrm{O}(\max(A) \log \max(A))\) 程度で前計算が可能です。

よってこの問題を \(\mathrm{O}(\max(A) \log \max(A) +\sum_{i=1}^N d(A_i))\) で解くことが出来て、制約下において \(d(A_i) \leq 128\) であることを考えると十分高速に動作します。