DMOPC '21 Contest 4 P2 - Festive Groups

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

The N citizens of Dmojistan are arranging a Christmas gathering! The i-th citizen has a jolliness of J_i, and a group of citizens is festive if the smallest jolliness of a citizen in that group is a divisor of the jolliness of every citizen in the group. To ensure that the gathering is as exciting as possible, the N citizens want to split themselves into some number of groups, where each group is festive and the number of groups is minimized. Please determine the number of groups in such an arrangement.


1 \le N \le 2 \times 10^6

1 \le J_i \le 5 \times 10^6

Subtask 1 [20%]

1 \le N \le 2 \times 10^3

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer N.

The second line contains N integers J_1, J_2, \dots, J_N.

Output Specification

Output a single integer, the answer to the problem.

Sample Input

8 3 15 10 6 4 16

Sample Output



The citizens may be divided into 3 festive groups as follows: [8, 4, 16], [3, 15, 6], [10].


There are no comments at the moment.