CF#511-C Enlarge GCD（gcd）

题意：给你一个序列，然后求删除几个数之后整个序列的最大公约数增大思路：1）我们首先要求出这个公共的gcd，然后要使gcd增大1直到到最大的数，然后再统计因子出现的个数，sort用n减去最大2) 要统计因子，我们还可以使用欧拉筛提前打好素数表，然后把所有数除以gcd剩下的对素数表来求因子个数（每个合数都是某个素数的倍数）所以我们采用第二种方法，降低复杂度  欧拉筛才O(N)

完整代码：(如果数组大小没有开够给出的可能是WA的结果)

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <cmath>using namespace std;const int maxm = 3e5+5;const int maxn = 1.5e7+5;int a[maxm+5],vis[maxn+5],p[maxn+5],s[maxn+5];int cnt;int gcd(int x,int y){    return y? gcd(y,x%y) : x;}//欧拉筛void init(){    int i ,j;    cnt = 0;    memset(vis,0,sizeof(0));    vis[0] = vis[1] = 1;    for(i=2;i<=maxn;++i)    {        if(!vis[i]) vis[i]= p[cnt++]= i;        for(j=0;j<cnt&&i*p[j]<=maxm;++j){            vis[i*p[j]] = p[j];//vis[i+p[j]] = 1;            if(i%p[j]==0) break;        }    }}int main(){    int n,i,j,g,x,ans;    init();     scanf("%d",&n);    g = 0;     for(i=1;i<=n;++i) {        scanf("%d",&a[i]);        g = gcd(g,a[i]);    }        ans = 0;    for(i =1;i<=n;i++){        a[i]/= g;//所有a[i]除以共同gcd(然后记录所有因子个数)        for(j = 0;p[j]*p[j] <= a[i];j++){            int q = p[j];            if(a[i]%q ==0) s[q]++;            while(a[i]%q==0){                a[i] /= q;            }          }        if(a[i] != 1) s[a[i]]++;    }    ans = n;    for(int i=2; i<maxn; ++i){        ans = min(ans, n-s[i]);    }    if(ans == n)    ans = -1;    printf("%d\n", ans);    return 0;}

 

转载于:https://www.cnblogs.com/Tianwell/p/11320374.html

相关资源：JAVA上百实例源码以及开源项目