\(d(x,y)\) を \(x,y\) 間の距離とします。頂点対 \(x< y\) であって、\(x,y\) 最短パス上の頂点たちの \(\gcd\) が \(g\) となるものの集合を \(S_g\)、\(\gcd\) が \(g\) の倍数となるものの集合を \(T_g\) とします。また、\(A_i\) が \(g\) の倍数であるような \(i\) の個数を \(C_g\) とします。

求める値を \(\rm gcd\) ごとに分けて考えると、\(\sum_{g=1}^{10^5}g\sum_{(i,j)\in S_g}(d(i,j)+1)\) となります。

ここで、\(S_g\) のかわりに \(T_g\) を考え、各 \(g\) について \(\sum_{(i,j)\in T_g}(d(i,j)+1)\) を求めることができれば、約数メビウス変換 (あるいは単に”除原理”) を用いることで、元の問題に答えることができます (参考: ABC162E)。これを求める方法を考えます。

まずは \(g=1\) である場合を考えます。このとき、\(T_g\) には全ての頂点対が含まれるので、求める値は \(\frac{N(N-1)}{2}+\sum_{(i,j)\in T_1}d(i,j)\) です。ここで、\(\sum_{(i,j)\in T_1}d(i,j)\) の”意味”は「全ての頂点対についての距離の和」なので、「各辺が和に何度寄与するか」を考えることで、\(\sum_{(i,j)\in T_1}d(i,j)=\sum_e(\text{木から辺 }e \text{ を取り除いたときにできる }2 \text{つの木の頂点数の積})\) となることがわかります。したがって、これはDFSにより \(O(N)\) で求められます。

\(g\) が一般の場合も同様で、\(\sum_{(i,j)\in T_g}(d(i,j)+1)\) は、\(A_i\) が \(g\) の倍数であるような頂点だけからなる誘導部分グラフを考え、その各連結成分について、さきほどと同様に辺ごとの寄与を考えることでDFSにより求めることができます。計算量は \(O(C_g)\) です。

以上によりこの問題を解くことができました。時間計算量を考えてみます。

\(\sum_{(i,j)\in T_g}(d(i,j)+1)\) の計算には \(O(C_g)\) かかるので、全ての \(g\) について計算すると \(O(\sum_g C_g)\) となります。ここで、\(i\) が \(C_g\) に寄与することは、\(g\) が \(A_i\) の約数であることと同値なので、\(\sum_g C_g=\sum_i \sigma_0(A_i)\) となります (\(\sigma_0(x)\) は \(x\) の約数の個数を表す)。\(\sigma_0(A_i)\) は緩い評価で \(O(\sqrt{A_i})\) であることから、結局この部分の計算量は \(O(N\sqrt{A})\) となります (\(A:=\max\{A_i\}\))。

約数メビウス変換は \(O(A\log\log A)\) でできるので、全体の計算量は \(O(N\sqrt{A}+A\log\log A)\) であることがわかりました。

実装例(C++) ※メビウス変換ではなく”除原理”を使っているため、\(O(N\sqrt{A}+A\log A)\)

追記：
上の実装例はDFSパートが \(O(C_g)\) になっていませんでした。\(C_g\) に寄与するような \(i\) たちについての \(\sum {\rm deg}(i)\) に依る時間計算量になっています。しかしよく考えると、この場合でも、全ての \(g\) についての計算にかかる時間が \(O(N\sqrt{A})\) になることが確かめられます。