上海计算机学会2021年5月月赛C++丙组T4整除
发布时间
阅读量：
阅读量
整除
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个数字构成的一个多重集合：a1,a2,⋯,an，请求出，其中有多少元素不能被任意一个在集合中的其他元素整除？
多重集合是指允许出现多个相等元素的集合。
输入格式
第一行：单个正整数 n；
第二行：n 个数字表示 a1,a2,⋯,an。
输出格式
单个自然数：表示集合中不能被其他数字整除的数字个数。
数据范围
- 1≤ai≤1,000,000；
- 对于 50% 的数据：1≤n≤10000；
- 对于 100% 的数据：1≤n≤100000。
样例数据
输入:
5
3 5 13 9 16
输出:
4
说明:
3,5,13,16均不能被集合中其他数整除，而9可以被3整除
解析：桶排序+埃氏筛
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int t[1000005];
bool b[1000005];
int ans=0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int a;
cin>>a;
t[a]++;//桶排序
}
for(int i=1;i<=1000000;i++){
if (t[i]!=0){
for(int j=2*i;j<=1000000;j+=i){//埃氏筛
b[j]=1;
}
}
if(b[i]==0&&t[i]==1){//没被筛掉且只有一个数的
ans++;
}
}
cout<<ans;
return 0;
}
全部评论 (0)
还没有任何评论哟~