Clique in the Divisibility Graph

题意翻译

在一张图中，如果有 $k$ 个点之间两两都有一条边相连，这 $k$ 个点就组成了一个“团”。 先在给你 $n$ ($n\leq 10^6)$ 个点，给你一个数组 $a$，$a_i$ 即为第 $i$ 个点的点权。 如果两个点 $i$, $j$ 使得 $a_i\bmod a_j=0$ 或者 $a_j\bmod a_i=0$，则 $i$, $j$ 之间有一条边相连，问这张图中最大的“团”的大小。 $\text{traslate by Y2y7m}$

题目描述

As you must know, the maximum clique problem in an arbitrary graph is $ NP $ -hard. Nevertheless, for some graphs of specific kinds it can be solved effectively. Just in case, let us remind you that a clique in a non-directed graph is a subset of the vertices of a graph, such that any two vertices of this subset are connected by an edge. In particular, an empty set of vertexes and a set consisting of a single vertex, are cliques. Let's define a divisibility graph for a set of positive integers $ A={a_{1},a_{2},...,a_{n}} $ as follows. The vertices of the given graph are numbers from set $ A $ , and two numbers $ a_{i} $ and $ a_{j} $ ( $ i≠j $ ) are connected by an edge if and only if either $ a_{i} $ is divisible by $ a_{j} $ , or $ a_{j} $ is divisible by $ a_{i} $ . You are given a set of non-negative integers $ A $ . Determine the size of a maximum clique in a divisibility graph for set $ A $ .

输入输出格式

输入格式

The first line contains integer $ n $ ( $ 1<=n<=10^{6} $ ), that sets the size of set $ A $ . The second line contains $ n $ distinct positive integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{6} $ ) — elements of subset $ A $ . The numbers in the line follow in the ascending order.

输出格式

Print a single number — the maximum size of a clique in a divisibility graph for set $ A $ .

输入输出样例

输入样例 #1

8
3 4 6 8 10 18 21 24

输出样例 #1

3

说明

In the first sample test a clique of size 3 is, for example, a subset of vertexes $ {3,6,18} $ . A clique of a larger size doesn't exist in this graph.

题意翻译

在一张图中，如果有 $k$ 个点之间两两都有一条边相连，这 $k$ 个点就组成了一个“团”。 先在给你 $n$ ($n\leq 10^6)$ 个点，给你一个数组 $a$，$a_i$ 即为第 $i$ 个点的点权。 如果两个点 $i$, $j$ 使得 $a_i\bmod a_j=0$ 或者 $a_j\bmod a_i=0$，则 $i$, $j$ 之间有一条边相连，问这张图中最大的“团”的大小。 $\text{traslate by Y2y7m}$