Олимпиадный тренинг

Задача . A. Идеально неидеальный массив


Задача

Темы: математика теория чисел *800

Вам дан массив \(a\) длины \(n\). Скажите, существует ли непустая подпоследовательность этого массива такая, что произведение ее элементов не является полным квадратом.

Последовательность \(b\) является подпоследовательностью массива \(a\), если \(b\) может быть получена из \(a\) удалением нескольких (возможно, ни одного) элементов.

Входные данные

В первой строке находится одно целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных. Далее следуют наборы входных данных.

Первая строка набора входных данных содержит одно целое число \(n\) (\(1 \le n \le 100\)) — длину массива \(a\).

Вторая строка набора входных данных содержит \(n\) целых чисел \(a_1\), \(a_2\), \(\ldots\), \(a_{n}\) (\(1 \le a_i \le 10^4\)) — элементы массива \(a\).

Выходные данные

Если существует подпоследовательность массива \(a\), произведение элементов которой не является полным квадратом, выведите «YES». Иначе, выведите «NO».

Примечание

В первом примере, произведение элементов всего массива (\(20\)) не является полным квадратом.

Во втором примере, произведение элементов любой подпоследовательности является полным квадратом.


Примеры
№Входные данныеВыходные данные
1 2
3
1 5 4
2
100 10000 
YES
NO

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет