Codeforces Round 717 (Div. 2) |
---|
Finished |
This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array $$$a$$$ of length $$$n$$$ written on it, and then he does the following:
Formally, he partitions the elements of $$$a_l, a_{l + 1}, \ldots, a_r$$$ into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for $$$q$$$ independent ranges $$$(l, r)$$$, tell Baby Ehab the minimum number of subarrays he needs.
The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 10^5$$$) — the length of the array $$$a$$$ and the number of queries.
The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the elements of the array $$$a$$$.
Each of the next $$$q$$$ lines contains $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the endpoints of this query's interval.
For each query, print its answer on a new line.
6 3 2 3 10 7 5 14 1 6 2 4 3 5
3 1 2
The first query asks about the whole array. You can partition it into $$$[2]$$$, $$$[3,10,7]$$$, and $$$[5,14]$$$. The first subrange has product and LCM equal to $$$2$$$. The second has product and LCM equal to $$$210$$$. And the third has product and LCM equal to $$$70$$$. Another possible partitioning is $$$[2,3]$$$, $$$[10,7]$$$, and $$$[5,14]$$$.
The second query asks about the range $$$(2,4)$$$. Its product is equal to its LCM, so you don't need to partition it further.
The last query asks about the range $$$(3,5)$$$. You can partition it into $$$[10,7]$$$ and $$$[5]$$$.
Name |
---|