牛客小白月赛101：tb的数数问题（筛法）

题目形貌

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 中出现一次。
输入形貌:

1. 第一行输入一个正整数 n(1≤n≤106)n(1 \le n \le 10^6)n(1≤n≤106) ，表示集合的大小。
3. 第二行输入 nnn 个数，表示集合 AAA 中的元素 ai(1≤ai≤106)a_i(1 \le a_i \le 10^6)ai​(1≤ai​≤106) 。

复制代码

输出形貌:

1. 一个非负整数，表示好的数的个数。

复制代码

示例1
输入

复制7 1 4 3 8 10 8 9

1. 7
2. 1 4 3 8 10 8 9

复制代码

输出

复制3

1. 3

复制代码

备注:

1. 样例 111 解释：
2. 符合条件的正整数有 1,3,91,3,91,3,9 ，由于 222 不在 AAA 中，其它数又都是 222 的倍数，所以其它数均不符合条件。

复制代码

做法

用类似埃式筛法的做法，把不符合条件的数字筛掉

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N=1e6+10;
5. int n,a[N],vis[N],sign,st[N],ans;
6. unordered_map<int,int>mp;
8. int main(){
10.     scanf("%d",&n);
12.     for(int i=1;i<=n;i++) {
13.         scanf("%d",&a[i]);
14.         vis[a[i]]++;
15.         mp[a[i]]++;//去重
16.         if(a[i]==1) sign=1;
17.     }
19.     if(!sign) {
20.         cout<<0;
21.         return 0;
22.     }
24.     for(int i=2;i<=1e6;i++){
26.         if(!vis[i]&&!st[i]){//数组中没有这个数，且没有被去除掉
27.             for(int j=i;j<=1e6;j+=i){//它的倍数都被去除
28.                 vis[j]=0;
29.                 st[j]=1;
30.             }
31.         }
33.     }
34.    
35.     for(auto x:mp) {
36.         if(vis[x.first]) ans++;
37.     }
38.     cout<<ans;
39. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。