問題概要 問題へのリンク 整数 $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$ 解 公式解説へのリンク ユーザ解説 (noshi91) へのリンク すこし考察すると，解を $R_1, \ldots, R_N$ として， $$ R_i = 2R_{i - 1} + \sum_{j = 1}^{i - 1} 2^j \textrm{gcd}(A_i, A_j) $$...
拡張ユークリッドアルゴリズムのメモ (といっても，Wikipedia を参照するだけ) 参照先 Wikipediaの記事 ポイント 与えられた $a$, $b$ に対して，$g := \text{gcd}(a, b)$ と $sa + tb = g$ となる $s$，$t$ を求める． $a$, $b$ は正，負，0 いずれも可． ただし，$\text{gcd}(a, 0) = \text{gcd}(0, a) = a$ $|s| \leq \max(|a|, |b|)$，$|t| \leq \max(|a|, |b|)$ が成り立つ． $|a|$ や $|b|$ が 64 ビットで表せていれば，このアルゴリズムで得られる $|a|$，$|b|$ もそうなる． ($|sa|$ や $|tb|$ ははみ出すかもしれない) アルゴリズム概要 1 * a + 0 * b = a と，0 * a + 1 * b = b から始める． $s_i a + t_i b = z_i$ と $s_{i + 1} a + t_{i + 1} b = z_{i + 1}$ まで得られたとする． 右辺の割算 $z_i = p z_{i + 1} + q$ をする． ($i$ の式) $ - p \times (i + 1$ の式) を作って， $(s_i - p \, s_{i + 1}) a + (t_i - p \, t_{i + 1}) b = q$ を得る． 右辺が $g := \text{gcd}(a, b)$ になるまで繰り返す． なお，もう一回まわすと $s_{k + 1} a + t_{k + 1} b = 0$ になり，$|s_{k + 1}| = |a|/g$，$|t_{k + 1}| = |b|/g$ が成り立つ． コード util....