AGC 038 C - LCMs

• 問題
• AC

ゼータ変換について勉強する機会になった。

ゼータ変換とメビウス変換

• 下位集合に関するゼータ変換: $F(S) = \sum_{T \subseteq S} f(T)$
• 上位集合に関するゼータ変換: $F(S) = \sum_{T \supseteq S} f(T)$

これを${\mathcal O}(2^N N)$でやるのが高速ゼータ変換。普通の総和以外にも、$\times, \max, \min$とかでもまったく同じ方法が使える。結合法則と交換法則が成り立っていればよいので、可換半群なら大丈夫なはず¹。

• 下位集合に関するメビウス変換: $f(S) = \sum_{T \subseteq S} (-1)^{|S\setminus T|}F(T)$
• 上位集合に関するメビウス変換: $f(S) = \sum_{T \supseteq S} (-1)^{|T \setminus S|}F(T)$

ゼータ変換の逆変換。つまり、上の$F$から$f$を導出する変換。

ゼータ変換と違って引き算を使うので、アーベル群でないといけない。演算が$\min$とかだとそもそも$f$を一意に復元できないので、当然ではある。

（用語法はよくわからないけど、競プロ界ではだいたいみんなnaoya_tさんの記事にある使いわけをしているっぽいのでそれに従っている。文献（これとか）によっては、ここでいう下位集合に対するゼータ変換がMöbius transform、その逆変換がMöbius inversionと呼ばれていたりする。）

$\cup$畳み込みと$\cap$畳み込み

$f$, $g$を
$F(S) := \sum_{T \subseteq S} f(T)$

$G(S) := \sum_{T \subseteq S} g(T)$

と下位集合に関してゼータ変換して、点毎に掛け算したものを$H$とする:

$\begin{aligned} H(S) & := F(S) \times G(S) \\ & =\sum_{T_1 \subseteq S} f(T_1) \times \sum_{T_2 \subseteq S} g(T_2) \\ & = \sum_{T \subseteq S} \sum_{T_1 \cup T_2 = T}f(T_1) \times g(T_2) \end{aligned}$

$H$をメビウス変換すると

$h(S) := \sum_{T_1 \cup T_2 = S} f(T_1) \times g(T_2)$

という関数が得られて、$\cup$に関する畳み込みができたことになる。

同様に、上位集合に関してゼータ変換して掛け合わせて逆変換すると、$\cap$に関する畳み込みができる。

分配法則を使っているので、この掛け算は足し算と合わせて環になっていないといけない。

約数、倍数に関するゼータ変換とメビウス変換

上と同じ話を約数、倍数について繰り返す。

• 約数に関するゼータ変換: $F(x) = \sum_{d | x} f(d)$
• 倍数に関するゼータ変換: $F(x) = \sum_{x | m} f(m)$

ただし、定義域は$\{0, 1, ..., N\}$とかに決まっているとして、その中だけで計算する。この変換は${\mathcal O}(N \log\log N)$でできる。²

• 約数に関するメビウス変換: メビウスの反転公式参照
• 倍数に関するメビウス変換: 同上

上の$F$から$f$を導出する変換。同じオーダーでできる。歴史的には約数・倍数に関するもののほうが最初に考えられたらしい。

LCM畳み込みとGCD畳み込み

やはり上と同じ話をLCMとGCDについて書き下してみる。

$f$, $g$を
$F(x) := \sum_{d | x} f(d)$

$G(x) := \sum_{d | x} g(d)$

と約数に関してゼータ変換して、掛け合わせたものを$H$とする:

$\begin{aligned} H(x) & := F(x) \times G(x) \\ & =\sum_{d_1|x} f(d_1) \times \sum_{d_2|x} g(d_2) \\ & = \sum_{d | x} \sum_{\operatorname{lcm}(d_1, d_2) = d}f(d_1) \times g(d_2) \end{aligned}$

$H$を逆変換すると

$h(x) := \sum_{\operatorname{lcm}(d_1, d_2) = x} f(d_1) \times g(d_2)$

という関数が得られて、$\operatorname{lcm}$に関する畳み込みができたことになる。

同様に、倍数に関してゼータ変換して掛け合わせて逆変換すると、$\gcd$に関する畳み込みができる。

問題

$\operatorname{lcm}(A_i, A_j) = A_iA_j/\gcd(A_i, A_j)$で、$\gcd(A_i, A_j)$は高々$1000000$なので、同じ$\gcd$毎にまとめて和を計算できれば良さそう。

最終的には、$dp[x]$が$\gcd(A_i, A_j) = x$となるような組み合わせについての$A_i A_j$の総和になってほしいので、とりあえず$dp$を次のように初期化していく。

$dp[A_i] := dp[A_i] + A_i$

$dp$を倍数に関してゼータ変換して$dp[x] := dp[x] \cdot dp[x]$と掛け合わせて逆変換すると、

$dp[x] = \sum_{\gcd(A_i, A_j) = x}A_iA_j$

になっている。このままでは不必要な組み合わせについても加算されているので、

$dp[A_i] := dp[A_i] - A_i^2$

として添え字が同じ組み合わせを除いたあと、$A_iA_j$と$A_jA_i$のダブルカウントを除くためにすべて半分にする: $dp[x] := dp[x]/2$。（ここではなくて一番最後に半分にしてもよい。）

これで$dp[x]$は$\gcd(A_i, A_j) = x$となるような組み合わせについての$A_i A_j (i < j)$の総和になったので、あとは$\gcd$で割りながら総和を取れば答えになる: $\sum_{x = 1}^{1000000} dp[x]/x$

---

1. ググってもそれっぽい言明が見つからなかったけど、かならいさんがそう言ってるのを発見した。 ↩︎

2. noshi91さんの記事に書いてある。 ↩︎