AtCoder Grand Contest 038 C - LCMs - アルゴリズム忘備録

atcoder.jp

$A_i$ が与えられるので、 $\sum lcm(A_i, A_j)$ を求めるというシンプルな問題。 $i, j$ はいずれも $1$ から $n$ を動くとしてよい。(tex: i = j]のときは簡単に計算できるので、後から引けばよい)

一般に、 $\sum c_{i,j} A_i A_j$ という形式の値を求める場合、 $O(N^2)$ が間に合わないなら、 $(\Sigma A_i) (\Sigma A_j)$ の形にしたいなと思うのが定石である。

まず考えることとしては $lcm(A_i, A_j) = A_i * A_j / gcd(A_i, A_j)$ であろう。一般に最小公倍数よりも最大公約数のほうが考えやすい(気がしている)。

そこで、与えられた式を $\sum_d f(d) \sum_{d|A_i, d|A_j} A_i A_j = \sum_d f(d) (\sum_{d|A_i)} A_i)^2$ という形に表す、ということを考えよう。(この発想は解説を見た)

すると $A_i A_j$ の係数(元の式では $\frac{1}{gcd(A_i, A_j)}$ )に着目すると、 $\frac{1}{gcd(A_i, A_j)} = \sum_{d|A_i, d|A_j} f(d) = \sum_{d|gcd(A_i, A_j)} f(d)$ であるため、結局 $X = \sum_{d|X} f(d)$ を求めれば良いことがわかった。

この値であるが、これはいわゆる約数メビウス変換という式になっている。すべての $X (1 \le X \le \max{A_i})$ に対して約数列挙して $f(d)$ を求めることも可能といえば可能だが、定数倍高速化を頑張らないと無理であろう。ということで高速約数メビウス変換を使うことで時間内に収まる。この計算量は $\max{A_i}=M$ とおくと、 $O(M \log{\log{M}})$ だそうである。(詳しくは証明したことはない)

残るは $\sum_{d|A_i} A_i$ の計算であるが、これはまず $c_y = |\{A_i | A_i = y\}|$ という値がyであるような $A_i$ の数というものを計算しておこう。すると $\sum_{d|A_i} A_i = \sum_{y=d, 2d, 3d,...} c_y * y$ と計算できる。これをすべての $d$ について計算するには、 $O(M \log{M})$ で計算できる。

問題設定はシンプルなのに式変形が高速ゼータ/メビウス変換の勉強になるという良問。