AT_abc170_d [ABC170D] Not Divisible

题目描述

给定一个长度为 $N$ 的数列 $A$。

请你求出满足以下性质的整数 $i$ 的个数（$1 \leq i \leq N$）：

• 对于任意的整数 $j$（$1 \leq j \leq N$，且 $i \neq j$），$A_i$ 不能被 $A_j$ 整除。

输入格式

输入以如下格式从标准输入中给出。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5
24 11 8 3 16

输出 #1

3

输入输出样例 #2

输入 #2

4
5 5 5 5

输出 #2

0

输入输出样例 #3

输入 #3

10
33 18 45 28 8 19 89 86 2 4

输出 #3

5

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^6$

样例解释 1

满足题目性质的是 $2$、$3$、$4$。

样例解释 2

请注意存在相同数字的情况。

由 ChatGPT 4.1 翻译