Задача №115152. Матрица циклических сдвигов
Дан одномерный массив \(a\) размера \(n\). Построим квадратную матрицу \(n \times n\), где \(i\)-я строка — это массив \(a\) с циклическим сдвигом\(^1\) на \(i - 1\) шагов вправо. Например, по массиву \([3, 4, 9]\) получается матрица
\(\) \begin{bmatrix} 3 & 4 & 9 \\ 9 & 3 & 4 \\ 4 & 9 & 3 \end{bmatrix}\(\)
Также дано число \(k\). Построим граф, где вершинами графа будут элементы этой матрицы. Рёбрами соединим все вершины графа, которые в исходной матрице находятся на манхэттенском расстоянии\(^2\) не больше \(k\) и у которых НОД\(^3\) значений строго больше \(1\). Ваша задача — посчитать число компонент связности\(^4\) полученного графа.
\(^1\) Циклический сдвиг массива \(a\) на \(i\) шагов вправо — это массив \(a_{n-i+1}, a_{n-i+2}, \ldots, a_n, a_1, \ldots, a_{n-i}\).
\(^2\) Манхэттенское расстояние в квадратной матрице \(n \times n\) между элементами с индексами \((i_1, j_1)\) и \((i_2, j_2)\) равно \(|i_1 - i_2|\) + \(|j_1 - j_2|\).
\(^3\) НОД (наибольший общий делитель) натуральных чисел \(a\) и \(b\) — это такое наибольшее натуральное число \(d\), что \(a\) делится на \(d\), и \(b\) делится на \(d\).
\(^4\) Компонента связности — это некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Первая строка входных данных содержит два числа \(n\) и \(k\) (\(2 \le n \le 10^6\), \(2 \le k \le 10^9\)) — размер массива и ограничение на манхэттенское расстояние соответственно.
Вторая строка входных данных содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)) — элементы массива \(a\).
Выведите одно число — ответ на задачу.
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
В условии приведена матрица, которая получается в первом и втором примере.
В первом примере все \(3\)-ки и \(9\)-ки будут находиться в одной компоненте, а \(4\)-ки в другой, поэтому ответ равен \(2\).
Во втором примере всё как в первом, но есть ещё дополнительная компонента из четверки, которая находится в матрице на позиции \((3, 1)\), поэтому ответ равен \(3\).
В третьем примере получается по две компоненты из двоек и троек, а также три компоненты, в каждой из которых одна единица, суммарно \(7\) компонент.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Ограничения | ||||
| Подз. | Баллы | \(n\) | дополнительно | Необх. подзадачи |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 15 | \(n \le 50\) | – | 0 |
| 2 | 15 | \(n \le 1000\) | – | 0, 1 |
| 3 | 15 | – | \(k = 2 \cdot n - 2, a_i \le 1000\) | – |
| 4 | 15 | – | \(k = 2 \cdot n - 2\) | 3 |
| 5 | 20 | – | все \(a_i\) — простые | – |
| 6 | 20 | – | – | 0 – 5 |
3 3 3 4 9
2
3 2 3 4 9
3
3 2 1 2 3
7