問題概要
整数 $N$ と，長さ $N$ の正の整数列 $(A_1, \ldots, A_N)$ が与えられる． $m = 1, 2, \ldots, N$ に対して，次の問題を解け
- 列 $(A_1, \dots, A_m)$ の空でない部分列のスコアの総和を 998244353 で割ったあまりを求めよ． ただし，列 $(B_1, \ldots, B_k)$ のスコアは，$\displaystyle\sum_{i = 1}^{k-1} \textrm{gcd}(B_i, B_{i + 1})$ である．
制約
$1\leq N \leq 5\times10^{5}$，$1 \leq A_i \leq 10^5$
解
すこし考察すると，解を $R_1, \ldots, R_N$ として，
$$ R_i = 2R_{i - 1} + \sum_{j = 1}^{i - 1} 2^j \textrm{gcd}(A_i, A_j) $$
であることがわかる． だから，$\sum_{j = 1}^{i - 1} 2^j \textrm{gcd}(A_i, A_j)$ が高速に求められれば良い． 以下，これを記述する．
解1 (公式解説)．click to open
整数 $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 のユーザ解説)．click to open
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)$ が成り立つのであった．
求めるものは，$\sum_n \{ \sum_j 2^j n \mid \textrm{gcd}(A_i, A_j) = n \}$ と書けるので， 各 $n$ に対して，$\sum \{ 2^j \mid \textrm{gcd}(A_i, A_j) = n \}$ が求められれば良いが，
- $f(i) = 1$，$f(p) = 0 (p \neq i)$
- $g(p) = \sum \{ 2^j \mid A_j = p \}$
とすると，$h(n) = \sum \{ 2^j \mid \textrm{gcd}(A_i, A_j) = n\}$ となる．
これは，高速ゼータ変換，各点積，高速メビウス変換で計算できる． 素因数ごとに累積和とその反対の計算をする． 参照1 ， 参照2
おそらく，解1と解2は同じ原理に依っているのだろうと思うが，まだ整理できていない．