P15279 [MCO 2025] 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$。参见

第一行包含两个以空格分隔的整数 $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** 对于第一个询问（$\texttt{1 7}$）， $b = [36, 24, 120, 24, 36, 60, 48]$。一种最优解法如下（被选中的元素以 $\underline{下划线}$ 标记，上一次操作产生的新元素以 $\textbf{粗体}$ 标记）： - $[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 4}$）， $b = [24, 120, 24]$。一种最优解法是 $[24, \underline{120, 24}] \to [24, \mathbf{24}]$。 对于第三个和第四个询问，可以不断合并直至只剩下一个元素。 对于第五个和第六个询问，$b$ 中所有元素已经相等。 #### 计分 **子任务 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$，存在某个整数 $k \ge 0$ 使得 $a_i = 2^k$。 **子任务 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$ 分）： 无额外限制。 翻译由 DeepSeek 完成