A君有一个集合。
这个集合有个神奇的性质。
若X,Y属于该集合，那么X与Y的最大公因数也属于该集合。
但是他忘了这个集合中原先有哪些数字。
不过幸运的是，他记起了其中n个数字。
当然，或许会因为过度紧张，他记起来的数字可能会重复。
他想还原原先的集合。
他知道这是不可能的……
现在他想知道的是，原先这个集合中至少存在多少数。
样例解释：
该集合中一定存在的是{1,2,3,4,6}
Input
第一行一个数n(1<=n<=100000)。 第二行n个数，ai(1<=ai<=1000000，1<=i<=n)。表示A君记起来的数字。 输入的数字可能重复。
Output
输出一行表示至少存在多少种不同的数字。
Input示例
5 1 3 4 6 6
Output示例
5
思路：
在输入时记录下最大元素的值m，以此作为后面运算的数值上界，题目中只要求输出最终的数字个数，于是我们可以忽略集合中已经存在的元素，在原集合中元素个数的基础上进行添加。
枚举从1到m的所有数字，遇到集合中已经存在的元素直接跳过，对于没有存在过的元素我们考虑要不要把它加入集合，枚举这个数后面的数，发现某些数字是这个数字的倍数且在集合中出现过，于是求出他们的gcd，枚举到m后，如果惊奇的发现这些数的gcd恰好等于我们在第一层循环中找出的那个未出现的数，(⊙o⊙)…那就说明我们正需要这个数，就把它加进去。
#include<cstdio> #include<iostream> #define N 1000010 using namespace std; int a[N],used[N],n; int gcd(int x,int y){ if(!y)return x; return gcd(y,x%y); } int main(){ scanf("%d",&n);int p=0,m=0; for(int i=1;i<=n;i++){ int x;scanf("%d",&x); if(!used[x]){ a[++p]=x; used[x]=1; m=max(m,x);//m集合中最大的一个数的值 } } for(int i=1;i<=m;i++){ if(used[i])continue;//如果集合中已经有这个数字了，不做讨论 int w=0; for(int j=i;j<=m;j+=i){//枚举未出现过的数字的倍数，考虑要不要把他加进去 if(used[j])w=gcd(w,j); } if(w==i)p++; } printf("%d",p); return 0; }