[数学][质因数分解][预处理优化] codeforces 1034A Enlarge GCD

http://codeforces.com/problemset/problem/1034/A

题意问给定n个数，从中最少去掉多少个数之后可以使得剩下的数字的gcd严格大于原序列的gcd。

思路：先求出来原序列的gcd，无解的情况很容易判断，当序列中最大的数字就是gcd的时候无解。对于有解的情况，把每个数字除以这个gcd，剩下的一个序列就是gcd为1的序列，然后只要求出来去掉多少个数字之后可以使得序列gcd不为1就行了。这时候考虑去掉k个数字之后剩下的数字gcd为几，不妨设为w，很容易知道如果能求出来对于每个质数有多少个数字有这个质因子，那么取“在序列中出现最多次数的那个质数”的出现次数就是最大的剩下的序列中的元素个数，这里的出现次数是说如果ai%w==0则cnt++的意思。那么能求出来剩下的元素最多有多少个，也就能求出来去除的元素最少有多少个了。

比赛时候这个题是把我T爆了，主要是很难确定对于每个数暴力质因数分解好还是线性筛预处理出来1.5e7之内的素数比较好，一开始一直用的暴力质因数分解但是test23一直t，最后6min换了预处理素数ac了，其实手推渐进复杂度感觉二者差不多。。。。玄学卡常，而且最后过了也是800ms飘过。。。

 

#include
#include
using namespace std;

typedef long long LL;
const int maxn=3e5+5;
const int mod=1.5e7+7;

const int MAXN=15000000;
int prime[MAXN+1];
void getPrime()
{
    for(int i=2; i<=MAXN; i++)
    {
        if(!prime[i])
            prime[++prime[0]]=i;
        for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++)
        {
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}

LL gcd(LL a,LL b)
{
    return !b?a:gcd(b,a%b);
}

int a[maxn];
int cnt[mod];
int gma,ans;
int p[50];
bool vis[mod];
unordered_map >mp;
const int maxp=970721;

void div(int x)
{
    int A=x;
    if(vis[x])
    {
        int len=mp[A].size(),tmp;
        for (int i=0; i