GCD Equality - 問題

Evirir 这条龙找到了 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。它想回答 $q$ 个形如 $(l, r)$（$1 \le l \le r \le n$）的询问，其含义是：

构造数组 $b = [b_1, b_2, \ldots, b_{r-l+1}] = [a_l, a_{l+1}, \ldots, a_r]$。在一次操作中，Evirir 可以选择 $b$ 中两个相邻的整数，比如 $b_i$ 与 $b_{i+1}$（$1 \le i < r-l+1$），并将它们替换为一个整数 $\gcd(b_i, b_{i+1})$。问：最少需要多少次操作，才能使 $b$ 中所有元素都相等？

你能帮助它快速回答这些询问吗？

注：$\gcd(x, y)$ 表示整数 $x, y$ 的最大公约数（GCD）。例如，$\gcd(18, 12) = 6$，$\gcd(14, 6) = 2$，$\gcd(9, 14) = 1$。参见 https://en.wikipedia.org/wiki/Greatest_common_divisor

第一行包含两个用空格分隔的整数 $n$ 和 $q$（$1 \le n \le 60,000$, $1 \le q \le 100,000$）。

第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 60,000$）。

接下来 $q$ 行每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一个询问。

按询问顺序，每行输出一个整数（答案）。

子任务 1（$8$ 分）：$n \le 15$，$q \le 120$。

子任务 2（$10$ 分）：$n, q \le 300$。

子任务 3（$13$ 分）：$n, q \le 3000$。

子任务 4（$17$ 分）：对所有 $1 \le i \le n$，$a_i \le 2$。

子任务 5（$9$ 分）：对所有 $1 \le i \le n$，$a_i = 2^k$，其中 $k \ge 0$ 为整数。

子任务 6（$7$ 分）：$q = n$。对所有 $1 \le i \le q$，第 $i$ 个询问为 $(1, i)$。

子任务 7（$26$ 分）：对所有 $1 \le i \le n$，$a_i \le 36$。

子任务 8（$10$ 分）：无额外限制。

10 6
36 24 120 24 36 60 48 24 24 9
1 7
2 4
6 10
6 8
8 9
10 10

对于第一个询问（1 7），$b = [36, 24, 120, 24, 36, 60, 48]$。一种最优方案如下（被选择的元素用 下划线 标出，最后一次操作得到的新元素用加粗表示）：

$[36, 24, \underline{120, 24}, 36, 60, 48]$：$\gcd(120, 24) = 24$
$[36, 24, \mathbf{24}, 36, \underline{60, 48}]$：$\gcd(60, 48) = 12$
$[\underline{36, 24}, 24, 36, \mathbf{12}]$：$\gcd(36, 24) = 12$
$[\mathbf{12}, \underline{24, 36}, 12]$：$\gcd(24, 36) = 12$
$[12, \mathbf{12}, 12]$

可以证明，不可能用少于 4 次操作使所有元素相等。

对于第二个询问（\texttt{2 5}），$b = [24, 120, 24]$。一种最优方案是 $[24, \underline{120, 24}] \to [24, \mathbf{24}]$。

对于第三和第四个询问，可以一直合并直到只剩下一个元素。

对于第五和第六个询问，$b$ 的所有元素本来就已经相等。

QOJ.ac