Codeforces Round 948 (Div. 2) |
---|
Закончено |
Никита — студент, увлеченный теорией чисел и алгоритмами. Он столкнулся с интересной задачей, связанной с массивом чисел.
Допустим, у Никиты есть массив целых чисел $$$a$$$ длины $$$n$$$. Назовём подпоследовательность$$$^\dagger$$$ массива особенной, если её наименьшее общее кратное (НОК) не содержится в $$$a$$$. НОК пустой подпоследовательности равен $$$0$$$.
Никита задался вопросом: какова длина самой длинной особенной подпоследовательности массива $$$a$$$? Помогите ему ответить на этот важный вопрос!
$$$^\dagger$$$ Последовательность $$$b$$$ является подпоследовательностью $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ путем удаления нескольких (возможно, нуля или всех) элементов, не изменяя порядок оставшихся элементов. Например, $$$[5,2,3]$$$ является подпоследовательностью $$$[1,5,7,8,2,4,3]$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — длину массива $$$a$$$.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2000$$$.
Для каждого набора выведите одно целое число — максимальную длину особенной подпоследовательности $$$a$$$.
651 2 4 8 1663 2 10 20 60 172 3 4 6 12 100003 120003692 42 7 3 6 7 7 1 684 99 57 179 10203 2 11 4081211
0 4 4 5 8 0
В первом наборе входных данных НОК любой непустой подпоследовательности будет содержаться в $$$a$$$, поэтому ответ $$$0$$$.
Во втором наборе входных данных можно взять подпоследовательность $$$[3, 2, 10, 1]$$$, ее НОК — число $$$30$$$, которое не содержится в $$$a$$$.
В третьем наборе входных данных можно взять подпоследовательность $$$[2, 3, 6, 100\,003]$$$, ее НОК — число $$$600\,018$$$, которое не содержится в $$$a$$$.
Название |
---|