传送门
- 复盘:刚开始想到用质因数分解方法 但是板子又忘记了 暴力取模只能过10%
- 晚上思路有很多 我选了最简单的那种 就是先用数组模拟去重复,然后遍历区间【1-数组的最大值】找到数组中没出现的数 然后线性筛选标记上false 最后遍历一遍数组 看看那些被打上标记就是不符号条件的 输出没有打上标记的数量
accode
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int num[N],n,cnt[N],flag[N];
int main(){cin>>n;int ctnum=0;for(int i=1;i<=n;i++){int t;cin>>t;if(cnt[t]>0) continue;else{num[++ctnum]=t;cnt[t]++;//记录重复个数}}sort(num+1,num+ctnum+1);// for(int i=1;i<=ctnum;i++) cout<<num[i]<<endl;for(int i=1;i<=num[ctnum]-1;i++){if(cnt[i]==0){// cout<<i<<endl;for(int j=1;j*i<=num[ctnum];j++){flag[j*i]=1;}}}int res=0;for(int i=1;i<=ctnum;i++){if(flag[num[i]]==0){// cout<<num[i]<<endl;res+=1;} }cout<<res<<endl;return 0;}