CF1516D Cut

这一次，Baby Ehab 只会剪纸而不会粘贴。他开始时有一张纸，上面写着一个长度为 $n$ 的数组 $a$，然后他会进行如下操作： - 他选择一个区间 $(l, r)$，将子段 $a_l, a_{l + 1}, \ldots, a_r$ 剪下来，移除数组的其他部分。 - 然后，他将这个区间再切分成若干个子区间。 - 为了增加一点数论的趣味，他要求每个子区间内所有元素的乘积必须等于它们的最小公倍数（LCM）。 形式化地说，他需要将 $a_l, a_{l + 1}, \ldots, a_r$ 划分为若干个连续的子数组，使得每个子数组的所有元素的乘积等于它们的最小公倍数。现在，对于 $q$ 个独立的区间 $(l, r)$，请你告诉 Baby Ehab 至少需要将该区间划分为多少个这样的子数组。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$），分别表示数组 $a$ 的长度和询问的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$），表示数组 $a$ 的元素。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示本次询问的区间端点。

对于每个询问，输出一行答案。

第一个询问询问的是整个数组。你可以将其划分为 $[2]$、$[3,10,7]$ 和 $[5,14]$。第一个子区间的乘积和 LCM 都为 $2$，第二个子区间的乘积和 LCM 都为 $210$，第三个子区间的乘积和 LCM 都为 $70$。另一种可能的划分方式是 $[2,3]$、$[10,7]$ 和 $[5,14]$。 第二个询问询问的是区间 $(2,4)$。它的乘积等于它的 LCM，因此不需要再划分。 最后一个询问询问的是区间 $(3,5)$。你可以将其划分为 $[10,7]$ 和 $[5]$。 由 ChatGPT 4.1 翻译