P15279 [MCO 2025] GCD Equality

Evirir the dragon found $n$ positive integers $a_1, a_2, \ldots, a_n$. They want to answer $q$ queries of the form $(l, r)$ ($1 \le l \le r \le n$), which means: - Construct the array $b = [b_1, b_2, \ldots, b_{r-l+1}] = [a_l, a_{l+1}, \ldots, a_r]$. In one operation, Evirir can choose two adjacent integers in $b$, say $b_i$ and $b_{i+1}$ ($1 \le i < r-l+1$), and replace them with one integer $\gcd(b_i, b_{i+1})$. What is the minimum number of operations needed to make all elements in $b$ equal? Can you help them answer the queries fast? Note: $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$. For example, $\gcd(18, 12) = 6$, $\gcd(14, 6) = 2$, and $\gcd(9, 14) = 1$. See

The first line contains two space-separated integers $n$ and $q$ ($1 \le n \le 60\,000$, $1 \le q \le 100\,000$). The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 60\,000$). Each of the following $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$), representing a query.

For each query in order, output an integer (the answer) on a line.

### Note $\underline{Example 1}$ For the first query ($\texttt{1 7}$), $b = [36, 24, 120, 24, 36, 60, 48]$. One optimal solution is (chosen elements are $\underline{underlined}$, the new element from the last operation is $\textbf{bolded}$): - $[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]$ It can be proven that one cannot make all elements equal in fewer than 4 operations. For the second query ($\texttt{2 5}$), $b = [24, 120, 24]$. One optimal solution is $[24, \underline{120, 24}] \to [24, \mathbf{24}]$. For the third and fourth query, one can keep merging until one element is left. For the fifth and sixth query, all elements of $b$ are already equal. ### Scoring Subtask 1 ($8$ points): $n \le 15$, $q \le 120$. Subtask 2 ($10$ points): $n, q \le 300$. Subtask 3 ($13$ points): $n, q \le 3000$. Subtask 4 ($17$ points): For all $1 \le i \le n$, $a_i \le 2$. Subtask 5 ($9$ points): For all $1 \le i \le n$, $a_i = 2^k$ for some integer $k \ge 0$. Subtask 6 ($7$ points): $q = n$. For all $1 \le i \le q$, the $i$-th query is $(1, i)$. Subtask 7 ($26$ points): For all $1 \le i \le n$, $a_i \le 36$. Subtask 8 ($10$ points): No additional constraints.