[51nod1616]最小集合

[51nod1616]

• ai并不大，所以我们可以正着考虑每个数是否在这个集合中必须出现

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=1e6+10;
int v[N],maxn,x,n,ans=0;
inline int read(){
	int num=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))num=num*10+ch-'0',ch=getchar();
	return num;
}
int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
int main()
{
	n=read();
	rep(i,1,n){
		x=read();
		v[x]=1;
		maxn=max(maxn,x);
	}
	rep(i,1,maxn){
		if(v[i])continue;
		int flag=0;
		for(int j=i+i;j<=maxn;j+=i){
			if(v[j]){
				flag=gcd(flag,j);
			}
		}
		v[i]=(flag==i);
	}
	rep(i,1,maxn)ans+=v[i];
	cout<<ans;
	return 0;
}