51nod 1616 最小集合
题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1616
题目大意：若$a$和$b$均在集合$S$中，则$gcd(a,b)$也在$S$中。现给出$S$中$n$个元素，问$|S|$的最小值.
数论
定义$f(k)$为这$n$个数中能被$k$整除的数的个数.
对任意一个数$x$，设其倍数构成的集合为$D$，令$d=gcd(D)$，则显然有$f(x)=f(d)=|D|$
代码如下：
1 #include <iostream> 2 using namespace std; 3 int n,ans,t,vis[1000005],f[1000005],tmp[1000005]; 4 int main(void){ 5 std::ios::sync_with_stdio(false); 6 cin>>n; 7 for(int i=0;i<n;++i){cin>>t;vis[t]=1;} 8 for(int i=1;i<=1000000;++i) 9 for(int j=1;i*j<=1000000;++j) 10 if(vis[i*j])f[i]++; 11 for(int i=1,j;i<=1000000;++i)if(f[i]){ 12 for(j=1;i*j<=1000000;++j) 13 if(f[i]==f[i*j])t=i*j; 14 tmp[t]=1; 15 } 16 for(int i=1;i<=1000000;++i) 17 if(tmp[i])ans++; 18 cout<<ans; 19 }
原文：http://www.cnblogs.com/barrier/p/6656410.html