本問のおそらく最難所は次でしょう．

• \(a[n] = \sum_{n\mid m}b[m]\) という関係がある．\(a[n]\) が分かっている．\(\sum_n nb[n]\) を求めよ．

\(a,b\) の関係は，

• \(a[n]\) は \(n\) が \(x,y\) の公約数であるときの何かの和
• \(b[n]\) は \(n = \gcd(x,y)\) であるときの何かの和

というような状況で頻出で，\(a\) から \(b\) を求める変換は倍数関係に関するメビウス変換です．（俗称に自信がないですが約数包除と呼ばれたりもするかも）

\(\sum_n nb[n] = \varphi(n)a[n]\) になるというのが公式解説のポイントです．これを「重みが \(n\) で足すときには \(\varphi(n)\) が使える」と理解してしまうと理解が限定されてしまうので，ここではさらに次の問題が一般に解けることを確認しておきましょう：

• 重みの列 \(Y[n]\) が与えられている．\(a[n] = \sum_{n\mid m}b[m]\) という関係があるとき，\(\sum_n Y[n]b[n] = \sum_n X[n]a[n]\) という重みの列 \(X[n]\) を求めよ．

次の式変形から \(X,Y\) が満たすべき関係式が分かります：

\(\sum_n X[n]a[n]=\sum_{n}(\sum_{n\mid m}X[n]b[m]) = \sum_m(\sum_{n\mid m}X[n])b[m]\)．

したがって \(Y[m] = \sum_{n\mid m}X[n]\) が成り立つようにすればよいです．\(Y\) が与えられて \(X\) を求めるには約数関係に関するメビウス変換をすればよいです．

別の解釈として，\(Y\) から \(X\) を求めるというのは \(a\) から \(b\) を求めることの転置なので，\(a\) から \(b\) を求める操作を転置するという方法でもこの計算手順を導出できます（転置原理）．