176 . 數字拆分

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (3/3)

Tags

ioicamp ioicamp-2022

Description

有 $N$ 個正整數 $a_1, \ldots, a_N$，求最小正整數 $k$ 使得你可以把 $a_1, \ldots, a_N$ 分成 $k$ 堆，使得如果 $a_i, a_j$ 在同一堆而且 $i \neq j$，那麼 $a_i \nmid a_j$ 且 $a_j \nmid a_i$，亦即這兩個數沒有整除關係。

Input Format

輸入第一行只包含一個正整數 $N$。

輸入第二行有 $N$ 個正整數 $a_1, a_2, \ldots, a_N$。

  • $1 \leq N \leq 10^ 6$
  • $1 \leq a_i \leq 10^ 6$

Output Format

輸出一個正整數 $k$ 代表至少要分成 $k$ 堆使得每一堆裡面沒有整除關係。

Sample Input 1

5
2 3 4 5 6

Sample Output 1

2

Sample Input 2

3
1 2 4

Sample Output 2

3

Sample Input 3

6
2 10 6 3 1 2

Sample Output 3

4

Hints

Problem Source

IOICamp 2022 Day3 pH

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~43 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 65536 1 2
1 4000 262144 65536 1 2
2 4000 262144 65536 1 2
3 4000 262144 65536 2
4 4000 262144 65536 2
5 4000 262144 65536 2
6 4000 262144 65536 2
7 4000 262144 65536 2
8 4000 262144 65536 2
9 4000 262144 65536 2
10 4000 262144 65536 2
11 4000 262144 65536 2
12 4000 262144 65536 2
13 4000 262144 65536 2
14 4000 262144 65536 2
15 4000 262144 65536 2
16 4000 262144 65536 2
17 4000 262144 65536 2
18 4000 262144 65536 2
19 4000 262144 65536 2
20 4000 262144 65536 2
21 4000 262144 65536 2
22 4000 262144 65536 2
23 4000 262144 65536 2
24 4000 262144 65536 2
25 4000 262144 65536 2
26 4000 262144 65536 2
27 4000 262144 65536 2
28 4000 262144 65536 2
29 4000 262144 65536 2
30 4000 262144 65536 2
31 4000 262144 65536 2
32 4000 262144 65536 2
33 4000 262144 65536 2
34 4000 262144 65536 2
35 4000 262144 65536 2
36 4000 262144 65536 2
37 4000 262144 65536 2
38 4000 262144 65536 2
39 4000 262144 65536 2
40 4000 262144 65536 2
41 4000 262144 65536 2
42 4000 262144 65536 2
43 4000 262144 65536 2
Submit
Back to Top