P12579 [UOI 2021] 哥萨克与 GCD

哥萨克 Vus 得到了一个包含 $n$ 个整数的数组 $a$。随后，他被告知存在另一个同样由 $n$ 个整数组成的数组 $b$，但具体内容未知。为了确定数组 $b$，哥萨克可以无限次使用以下操作 - 选择两个整数 $1 \leq l \leq r \leq n$。 - 查询 $b_l + b_{l + 1} + \dots + b_r$ 的和。 - 支付 $\gcd(a_l, a_{l+1}, ..., a_r)$ 戈比，其中 $\gcd$ 表示最大公约数（例如 $\gcd(3, 5) = 1$，而 $\gcd(15, 30, 6) = 3$）。 Vus 需要你求出确定数组 $b$ 所需的最小戈比数。 随后，哥萨克会对数组 $a$ 进行 $q$ 次修改，每次将某个 $a_i$ 改为 $x$。每次修改后，你需要重新计算更新后的数组所需的最小戈比数。

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 10^5, 0 \leq q \leq 10^5)$ —— 分别表示数组 $a$ 的长度和修改次数。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 10^9)$ —— 数组 $a$ 的初始元素。 接下来的 $q$ 行，每行包含两个整数 $i$ 和 $x$ $(1 \leq i \leq n, 1 \leq x \leq 10^9)$ —— 表示修改的位置和修改后的值。

输出 $q + 1$ 个数字 —— 分别对应初始数组和每次修改后的数组所需的最小戈比数。 第一个数字是初始数组 $a$ 的答案。 接下来的 $q$ 个数字是每次修改后的答案。

### 评分标准 - （8 分）：$n \le 10^2, q = 0$； - （7 分）：$n \le 10^3, q = 0$； - （11 分）：$q = 0$； - （12 分）：$q \leq 100$； - （9 分）：$q \leq 500$； - （23 分）：$q \leq 10000$； - （30 分）：无额外限制。 翻译由 DeepSeek V3 完成