Codeforces Round #511 (Div. 2) C. Enlarge GCD

http://codeforces.com/contest/1047/problem/C

复杂度很玄学的一个题，不是吗

998ms应该是最极限的了吧。

题目就是给n个数字问最少删掉几个能使得gcd变大。

被辉神一眼识破的题，

问题可以转化成n个数字先除以全部的gcd，那么现在的gcd肯定是1，对吧，就问最少删除几个可以使得gcd不是1.

筛质数，然后对于每个质因子，判断有多少个数字存在这个质因子，取出现数量最大的那么质因子，然后用n-最大出现次数就可以了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e5+5;
const int MAXM=1.5e7+5;
const int mmax=1.5e7;
int C[MAXN],num[MAXM],vis[MAXM];
int main()
{
    int n;
    scanf("%d",&n);
    int now=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&C[i]);
        now=__gcd(now,C[i]);
    }
    int num1=0;
    //cout<<now<<endl;
    int Max=-1;
    for(int i=1;i<=n;i++){
        C[i]/=now;
        Max=max(Max,C[i]);
        if(C[i]==1)num1++;
        num[C[i]]++;
    }
    if(num1==n){
        printf("-1\n");return 0;
    }
    int ans=0;
    for(int i=2;i<=Max;i++){
        if(vis[i])continue;
        int t=0;
        for(int j=1;j*i<=Max;j++){
            vis[i*j]=1;t+=num[i*j];
        }
        ans=max(ans,t);
    }
    printf("%d\n",n-ans);
}