DMOPC '21 Contest 4 P2 - Festive Groups - Olympiads Online Judge

DMOPC '21 Contest 4 P2 - Festive Groups

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

The $N$ ~N~ citizens of Dmojistan are arranging a Christmas gathering! The $i$ ~i~-th citizen has a jolliness of $J_i$ ~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$ ~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.

Constraints

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

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

Subtask 1 [20%]

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

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains an integer $N$ ~N~.

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

Output Specification

Output a single integer, the answer to the problem.

Sample Input

7
8 3 15 10 6 4 16

Sample Output

Explanation

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

Comments

1

Olly_Onion99 commented on May 9, 2026, 2:57 a.m. ← edited →

for python coders, if you don't want fancy stuff, it's either MLE for PyPy or TLE for CPython 😔