Задача №114654. Тимбилдинг
Недавно Алексей устроился на работу в крупную IT-компанию. Ему предложили поработать над групповым проектом. До этого у него уже было много успешных проектов, но в этот раз всё шло не по плану.
Алексей долго пытался найти причину всех неудач. В итоге он пришел к выводу, что его группа несбалансированна. Он считает, что \(i\)-й человек в компании характеризуется числом \(a_i\). Тогда в его понимании, группа сбалансирована, если для любого целого \(m \gt 1\) и любой пары разных людей \((i, j)\) в группе верно, что остатки от деления чисел \(a_i\) и \(a_j\) на \(m\) различаются.
Алексей обратился со своими соображениями к руководству. Они были бы рады согласиться на реформы, но для начала хотели бы оценить все риски. Помогите Алексею убедить руководство, для этого требуется найти минимальное количество сбалансированных групп, на которое можно разбить всех работников компании.
В первой строке задано одно целое число \(n\) (\(2 \leq n \leq 200\,000\)) — количество работников в компании.
Во второй строке заданы \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) — числа, характеризующие работников.
Выведите одно число — минимальное количество сбалансированных групп, на которое можно разбить всех работников компании.
В первом примере работников можно разбить на группы 4 способами: {\((1), (2), (3), (4)\)}, {\((1, 2)\), \((3), (4)\)}, {\((1), (2, 4), (3)\)}, {\((1), (2, 3), (4)\)}. Первый и третий работник не могут быть в одной группе так как остатки от деления \(a_1\) и \(a_3\) на \(2\) совпадают. Первый и четвёртый работник не могут быть в одной группе так как остатки от деления \(a_1\) и \(a_4\) на \(7\) совпадают. Третий и четвёртый работник не могут быть в одной группе так как остатки от деления \(a_3\) и \(a_4\) на \(2\) совпадают. Таким образом, ответ на данный тест равен \(3\).
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | |||||
| Группа | Баллы | \(n\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 13 | \(n \leq 10\) | \(a_i \leq 10 \) | 0 | |
| 2 | 29 | \(n \leq 1000\) | – | 0, 1 | |
| 3 | 12 | \(n \leq 200\,000\) | \(a_i \leq 2\) | – | |
| 4 | 15 | \(n \leq 200\,000\) | – | – | Все \(a_i\) различны. |
| 5 | 31 | – | – | 0, 1, 2, 3, 4 | |
4 1 2 3 1
3
5 6 1 2 5 3
3
6 1 1 2 2 1 1
4