176 . 數字拆分

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

80.0% (4/5)

Tags

ioicamp ioicamp-2022

Description

有 N 個正整數 a1,…,aN，求最小正整數 k 使得你可以把 a1,…,aN 分成 k 堆，使得如果 ai,aj 在同一堆而且 i≠j，那麼 ai∤aj 且 aj∤ai，亦即這兩個數沒有整除關係。

Input Format

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

輸入第二行有 N 個正整數 a1,a2,…,aN。

  • 1≤N≤106
  • 1≤ai≤106

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