Codeforces Round #511 (Div. 2)C+暴力筛

题目链接：http://codeforces.com/contest/1047/problem/C
题目大意：给你长度为n的数组，这个数组的gcd为m，输出能够使m变大的情况下至少要删除多少个数，如果删除数字不能使m变大的话，就为没有答案，输出-1

思路：把这些数除以他们所有数的最大公因数，保存在数组s1中，这s1中具有倍数（至少2倍）关系的数最多的个数即为保留的个数。

思考：为什么这样的复杂度没有被T？？？？？

#include<bits/stdc++.h>
using namespace std;

const int N=1.5e7+5, M=3e5+5;
int a[M], s1[N], s2[N];
int main()
{
    memset(s1, 0, sizeof(s1));
    memset(s2, 0, sizeof(s2));
    
    int n, g;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(i==0)
            g=a[0];
        else
            g=__gcd(g, a[i]);//所有数的最大gcd1
    }
    for(int i=0;i<n;i++)
    {
        s1[a[i]/g]++;        //所有的数都除以g,统计个数

    }

    //max_s记录s1中有相同gcd2并且gcd>=2的数的最大个数
    //即保留数字的最大个数，因为这些数的gcd3=gcd1*gcd2(gcd2>=2)
    //所以gcd3>gcd1。保留最多则删除最少
    int max_s=0;             
    for(int i=2;i<N;i++)
    {
        //统计具有相同公因数的数字个数
        if(!s2[i])
        {
            int s=0;
            for(int j=i;j<N;j+=i)
            {
                s+=s1[j];
                s2[j]=1;//防止重复访问
            }
            max_s=max(max_s, s);
        }
    }
    printf("%d\n",max_s?n-max_s:-1);

    return 0;
}