tb的数数问题
题号:NC276177
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

tb 给了 fc 一个包含若干个数字的可重集合 A ,如果我们说一个数字 x 是好的当且仅当 \forall \ d | x ,有 d \in A

现在,fc 想知道有多少个不同的正整数是好的,请你告诉他吧。

d|x : 表示 dx 的约数。

\forall \ d | x ,有 d \in A : x 的任何约数都至少在 A 中出现一次。

输入描述:

第一行输入一个正整数 n(1 \le n \le 10^6) ,表示集合的大小。

第二行输入 n 个数,表示集合 A 中的元素 a_i(1 \le a_i \le 10^6)

输出描述:

一个非负整数,表示好的数的个数。
示例1

输入

复制
7
1 4 3 8 10 8 9

输出

复制
3

备注:

样例 1 解释:
符合条件的正整数有 1,3,9 ,由于 2 不在 A 中,其它数又都是 2 的倍数,所以其它数均不符合条件。