Как вам должно быть известно, задача о поиске максимальной клики в произвольном неориентированном графе является NP-трудной. Тем не менее, для некоторых графов специфических видов её можно решить эффективно.
На всякий случай напомним, что кликой в неориентированном графе называется подмножество вершин графа, такое, что любые две вершины этого подмножества соединены ребром. В частности, пустое множество вершин и множество, состоящее из единственной вершины, являются кликами.
Определим граф делимостей для множества целых положительных чисел A = {a1, a2, ..., an} следующим образом. Вершинами данного графа являются числа из множества A, а два числа ai и aj (i ≠ j) соединены ребром тогда и только тогда, когда либо ai делится на aj, либо aj делится на ai.
Вам дано множество целых неотрицательных чисел A. Определите максимальный размер клики в графе делимостей множества A.
В первой строке находится целое число n (1 ≤ n ≤ 106), задающее размер множества A.
Во второй строке находятся n различных целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — элементы множества A. Числа в строке следуют в порядке возрастания.
Выведите единственное целое число — максимальный размер клики в графе делимостей для множества A.
8
3 4 6 8 10 18 21 24
3
В первом тесте из условия кликой размера 3 является, например, подмножество вершин {3, 6, 18}. Клик большего размера в данном графе нет.
Название |
---|