| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 289 | 45 | 27 | 17.532% |
<<Клубу неудачников>> после победы над Пеннивайзом почти удалось сбежать из заброшенного дома, осталось только решить кодовый замок на двери.
На кодовом замке написано $n$ натуральных чисел $a_1, a_2, \ldots, a_n$. И чтобы открыть его, нужно найти размер наибольшего подмножества этих чисел, что НОД чисел в подмножестве строго больше единицы. НОД множества чисел --- это наибольшее натуральное число, делящее все числа из множества.
Помогите героям справиться с этой задачей!
В первой строке дано одно целое число $n$ (1ドル \leq n \leq 1000$) --- количество натуральных чисел.
Во второй строке даны $n$ натуральных чисел $a_i$ (2ドル \leq a_i \leq 10^{18}$).
Выведите одно целое число --- размер наибольшего подмножества данных чисел, что НОД чисел в этом подмножестве строго больше единицы.
4 6 15 10 42
3
3 2 2 2
3
1 35
1
В первом тесте можно выбрать множество $\{6, 15, 42\},ドル НОД чисел в этом множестве равен 3ドル$.