分析：也就是取任意多个数，它们的最大公约数都在这个集合里。考虑到ai比较小，可以枚举小于a中最大值的所有数，判断是否为其中若干个数的gcd。记c[k]为a中k的倍数的个数，然后枚举k的倍数i*k，c[i]<2直接跳过，如果c[i*k]==c[k]，说明k的那些倍数也同时是i*k的倍数，k就可以不在集合中，反之，如果任意i，c[i*k]<c[k]，说明存在一个倍数和其它k的倍数的gcd是k，所以k一定在集合中。两次枚举倍数，复杂度为O(nlogn)。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int maxn=1e6+5; 6 bool In_set[maxn]; 7 int count_multiple[maxn]; 8 int main(){ 9     int n,ans=0,a;10     scanf("%d",&n);11     ans=n;12     memset(In_set,0,sizeof(In_set));13     memset(count_multiple,0,sizeof(count_multiple));14     for(int i=0;i