Codeforces Round 731 (Div. 3) |
---|
Закончено |
Задан массив из положительных целых чисел $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ ($$$n \ge 2$$$).
За один шаг массив $$$a$$$ заменяется на другой массив длины $$$n$$$, в котором каждый элемент это наибольший общий делитель (НОД) двух соседних элементов (самого элемента и его правого соседа; считайте, что правый сосед $$$(n - 1)$$$-го элемента это $$$0$$$-й элемент).
Формально говоря, по массиву $$$a = [a_0, a_1, \dots, a_{n - 1}]$$$ строится новый массив $$$b = [b_0, b_1, \dots, b_{n - 1}]$$$ такой, что $$$b_i$$$ $$$= \gcd(a_i, a_{(i + 1) \mod n})$$$, где $$$\gcd(x, y)$$$ — это наибольший общий делитель $$$x$$$ и $$$y$$$, а $$$x \mod y$$$ — это остаток от деления $$$x$$$ на $$$y$$$. За один шаг строится массив $$$b$$$, а затем массив $$$a$$$ заменяется массивом $$$b$$$ (то есть осуществляется присваивание $$$a$$$ := $$$b$$$).
Например, если $$$a = [16, 24, 10, 5]$$$, то $$$b = [\gcd(16, 24)$$$, $$$\gcd(24, 10)$$$, $$$\gcd(10, 5)$$$, $$$\gcd(5, 16)]$$$ $$$= [8, 2, 5, 1]$$$. Таким образом, массив $$$a = [16, 24, 10, 5]$$$ после одного шага станет равен $$$[8, 2, 5, 1]$$$.
Для заданного массива $$$a$$$ найдите минимальное количество шагов, после которых все значения $$$a_i$$$ станут равными (то есть $$$a_0 = a_1 = \dots = a_{n - 1}$$$). Если изначально массив $$$a$$$ уже состоял из одинаковых элементов, то считайте, что количество шагов равно $$$0$$$.
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте. Далее записаны $$$t$$$ наборов входных данных.
Каждый набор состоит из двух строк. В первой строке содержится целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$. Вторая строка содержит $$$n$$$ целых чисел $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$1 \le a_i \le 10^6$$$).
Сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2 \cdot 10^5$$$.
Выведите $$$t$$$ чисел — ответы на наборы входных данных теста.
5 4 16 24 10 5 4 42 42 42 42 3 4 6 4 5 1 2 3 4 5 6 9 9 27 9 9 63
3 0 2 1 1
Название |
---|