题目描述
tb 给了 fc 一个包含若干个数字的可重集合 AAA ，如果我们说一个数字 xxx 是好的当且仅当 ∀ d∣x\forall \ d | x∀ d∣x ，有 d∈Ad \in Ad∈A。
现在，fc 想知道有多少个不同的正整数是好的，请你告诉他吧。
d∣xd|xd∣x : 表示 ddd 为 xxx 的约数。
∀ d∣x\forall \ d | x∀ d∣x ，有 d∈Ad \in Ad∈A ： xxx 的任何约数都至少在 AAA 中出现一次。
输入描述:
第一行输入一个正整数 n(1≤n≤106)n(1 \le n \le 10^6)n(1≤n≤106) ，表示集合的大小。第二行输入 nnn 个数，表示集合 AAA 中的元素 ai(1≤ai≤106)a_i(1 \le a_i \le 10^6)ai(1≤ai≤106) 。
输出描述:
一个非负整数，表示好的数的个数。
示例1
输入
复制7 1 4 3 8 10 8 9
7 1 4 3 8 10 8 9
输出
复制3
3
备注:
样例 111 解释： 符合条件的正整数有 1,3,91,3,91,3,9 ，由于 222 不在 AAA 中，其它数又都是 222 的倍数，所以其它数均不符合条件。
做法
用类似埃式筛法的做法，把不符合条件的数字筛掉
#include<bits/stdc++.h>
using namespace std;const int N=1e6+10;
int n,a[N],vis[N],sign,st[N],ans;
unordered_map<int,int>mp;int main(){scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%d",&a[i]);vis[a[i]]++;mp[a[i]]++;//去重if(a[i]==1) sign=1;}if(!sign) {cout<<0;return 0;}for(int i=2;i<=1e6;i++){if(!vis[i]&&!st[i]){//数组中没有这个数，且没有被去除掉for(int j=i;j<=1e6;j+=i){//它的倍数都被去除vis[j]=0;st[j]=1;}}}for(auto x:mp) {if(vis[x.first]) ans++;}cout<<ans;
}
