Недавно алексей устроился на работу в крупную it-компанию. ему предложили поработать над
групповым проектом. до этого у него уже было много успешных проектов, но в этот раз всё шло
не по плану.
алексей долго пытался найти причину всех неудач. в итоге он пришел к выводу, что его группа
. он считает, что i-й человек в компании характеризуется числом ai
. тогда в его
понимании, группа , если для любого целого m > 1 и любой пары разных людей
(i, j) в группе верно, что остатки от деления чисел ai и aj на m различаются.
алексей обратился со своими соображениями к руководству. они были бы рады согласиться на
реформы, но для начала хотели бы оценить все риски. алексею убедить руководство, для
этого требуется найти минимальное количество групп, на которое можно разбить
всех работников компании.
формат входных данных
в первой строке задано одно целое число n (2 6 n 6 200 000) — количество работников в компании.
во второй строке заданы n целых чисел a1, a2, . . , an (1 6 ai 6 109
) — числа, характеризующие
работников.
формат выходных данных
выведите одно число — минимальное количество групп, на которое можно
разбить всех работников компании.
примеры
стандартный ввод стандартный вывод
4
1 2 3 1
3
5
6 1 2 5 3
3
6
1 1 2 2 1 1
4
замечание
в первом примере работников можно разбить на группы первый и третий работник не могут быть в одной группе
так как остатки от деления a1 и a3 на 2 . первый и четвёртый работник не могут быть
в одной группе так как остатки от деления a1 и a4 на 7 . третий и четвёртый работник
не могут быть в одной группе так как остатки от деления a3 и a4 на 2 . таким образом,
ответ на данный тест равен 3

Catherina4002    3   08.01.2020 12:25    56