ARC185E - Adjacent GCD

整数 $x$ の約数の集合を $D(x)$ と書くことにする．$x \leq 5\times10^5$ のとき，$|D(x)| \leq 128$ である．

オイラーの $\varphi$関数 ($\varphi(x)$ は，$x$ と互いに素である $x$ 以下の整数の個数) を使う． $n = \sum_{d \in D(n)} \varphi(d)$ が成り立つのであった．

\begin{align*} \sum_j 2^j \text{gcd}(A_i, A_j) & =\sum_j 2^j \sum \{ \varphi(d) \mid d \in D(\text{gcd}(A_i, A_j)) \} \\ & =\sum_j 2^j \sum \{ \varphi(d) \mid d \in D(A_i), d \in D(A_j) \} \\ & =\sum_{d \in D(A_i)} \varphi(d) \sum_j ( \texttt{if } d|A_j \texttt{ then } 2^j \texttt{ else } 0) \end{align*}

$\sum_j ( \texttt{if } d|A_j \texttt{ then } 2^j \texttt{ else } 0)$ の部分は，各 $d$ に対する値を 全部持っていて，$i$ が 1増えるたびに更新すれば良い．更新箇所は $|D(A_i)|$ 箇所である．

解2 (noshi91 のユーザ解説)

GCD畳み込みが，約数ゼータ変換を行うと各点積になることを用いる．すなわち， $h(n) = \sum \{ f(p)g(q) \mid \text{gcd}(p, q) = n \}$， $F(n) = \sum_{n|p} f(p)$， $G(n) = \sum_{n|p} g(p)$， $H(n) = \sum_{n|p} h(p)$ であるとき，$H(n) = F(n)G(n)$ が成り立つのであった． 意味を考えると， 最大公約数が $n$ の倍数であるような $p$ と $q$ (つまり，$n$ を公約数に持つ $p$ と $q$) に対する $f(p)$ と $g(q)$ の積の総和は，$n$ の倍数 $p$ に対する $f(p)$ の和と $n$ の倍数 $q$ に対する $g(q)$ の和の積になる，ということだから．

求めるものは，$\sum_n n \sum \{2^j \mid \textrm{gcd}(A_i, A_j) = n,\; j < i\}$ と書けるので， 各 $n$ に対して，$\sum \{ 2^j \mid \textrm{gcd}(A_i, A_j) = n,\; j < i \}$ が求められれば良い．

• $f(p) = \texttt{if } p = A_i \texttt{ then } 1 \texttt{ else } 0$
• $g(p) = \sum \{ 2^j \mid j < i, A_j = p \}$

とすると， $h(n) = \sum \{ f(p)g(q) \mid \text{gcd}(p, q) = n \} = \sum \{ 2^j \mid \textrm{gcd}(A_i, A_j) = n, \; j < i\}$ となる．

これは，高速ゼータ変換，各点積，高速メビウス変換で計算できる． 素因数ごとに(上から下に向かった)累積和とその反対の計算をする． 参照1 ， 参照2

$i - 1$ まで計算が終わっているとき，$i$ の計算を考える． $G$ の各点の値は計算しておくとして，これが変化するのは $A_{i - 1}$ の約数の点のみである． $F$ は，$A_i$ の約数の点のみが 1 で他は 0 だから，$H$ の計算 (および $G$ の更新) に要する手間は $|D(A_i)| + |D(A_{i - 1})|$ 程度である．$H$ から $h$ の計算は， 「$xp^r$ と $xp^{r + 1}$ の値の差で$xp^r$ の値を置き換える」ことなので，これも，$A_i$ の約数の点のみで行えば良い．