Codeforces Round 628 (Div. 2) |
---|
Закончено |
Вам дан массив $$$a$$$ длины $$$n$$$, который имеет специальное условие: каждый элемент в этом массиве имеет не более 7 делителей. Найдите длину кратчайшей непустой подпоследовательности этого массива, произведение элементов которой является полным квадратом.
Последовательность $$$a$$$ является подпоследовательностью массива $$$b$$$, если $$$a$$$ можно получить из $$$b$$$, удалив несколько (возможно, ноль или все) элементов.
Первая строка содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину массива $$$a$$$.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{n}$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.
Выведите длину кратчайшей непустой подпоследовательности $$$a$$$, произведение элементов которой является полным квадратом. Если существует несколько таких кратчайших подпоследовательностей, вы можете найти любую из них. Если такой подпоследовательности нет, выведите «-1».
3 1 4 6
1
4 2 3 6 6
2
3 6 15 10
3
4 2 3 5 7
-1
В первом примере, вы можете выбрать подпоследовательность $$$[1]$$$.
Во втором примере, вы можете выбрать подпоследовательность $$$[6, 6]$$$.
В третьем примере, вы можете выбрать подпоследовательность $$$[6, 15, 10]$$$.
В четвертом примере, такой подпоследовательности не существует.
Название |
---|