Codeforces Round 717 (Div. 2) |
---|
Закончено |
В этот раз Ехаб решил только разрезать массив. Он начинает с массива $$$a$$$ длины $$$n$$$, записанного на полоске бумаги, и делает следующее:
Формально, он разбивает элементы $$$a_l, a_{l + 1}, \ldots, a_r$$$ на подотрезки так, чтобы произведение элементов каждого подотрезка было равно НОК элементов этого подотрезка. У Ехаба есть $$$q$$$ независимых отрезков $$$(l, r)$$$, для которых он хочет узнать, на какое минимальное число подотрезков их необходимо разрезать, чтобы условие выполнялось.
В первой строке записано $$$2$$$ целых числа $$$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$$$ строк записано $$$2$$$ целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — границы каждого запроса.
Для каждого запроса выведите ответ на него.
6 3 2 3 10 7 5 14 1 6 2 4 3 5
3 1 2
Первый запрос спрашивает про весь массив. Вы можете разделить его так: $$$[2]$$$, $$$[3,10,7]$$$, и $$$[5,14]$$$. Произведение и НОК первого подотрезка равны $$$2$$$. Произведение и НОК второго подотрезка равны $$$210$$$. И произведение и НОК третьего подотрезка равны $$$70$$$. Существует другое возможное разделение: $$$[2,3]$$$, $$$[10,7]$$$, и $$$[5,14]$$$.
Второй запрос спрашивает про отрезок $$$(2,4)$$$. Его произведение уже равно его НОК, следовательно, не нужно делить его ни разу.
Последний запрос про отрезок $$$(3,5)$$$. Вы можете разделить его на $$$[10,7]$$$ и $$$[5]$$$.
Название |
---|