CF566F Clique in the Divisibility Graph

正如你所知，任意图中的最大团问题是 $NP$-困难的。然而，对于某些特定类型的图，这个问题可以被有效地解决。 这里我们再提醒一下，无向图中的「团」是指图中顶点的一个子集，使得这个子集中的任意两个顶点都由一条边相连。特别地，空集与只含有一个顶点的集合，也都视为团。 给定一个正整数集合 $A = \{a_1, a_2, \ldots, a_n\}$，我们定义它的「整除图」如下：该图的顶点是集合 $A$ 中的数字，且对于任意的 $a_i$ 和 $a_j$（$i \neq j$），当且仅当 $a_i$ 整除 $a_j$，或者 $a_j$ 整除 $a_i$ 时，$a_i$ 和 $a_j$ 之间有一条无向边。 现在给定一个正整数集合 $A$，请你求出全集 $A$ 的整除图中，最大团的大小。

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示集合 $A$ 的规模。 第二行包含 $n$ 个互不相同的正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^6$），表示集合 $A$ 的元素。第二行中的数字已经按升序排列。

输出一个整数，表示集合 $A$ 的整除图中最大团的大小。

在第一个样例测试中，大小为 3 的团的一个例子是顶点子集 $\{3, 6, 18\}$。这个图中不存在更大的团了。 由 ChatGPT 5 翻译