cf1047C-Enlarge GCD-（欧拉筛+map+gcd+唯一分解定理）

佚名 6年前 (2019-04-23) 随笔 1296人围观抢沙发百度已收录

https://vjudge.net/problem/CodeForces-1047C

题意：有n个数，他们有个最大公约数设为maxxgcd，要删去一些数，使得剩下的数的gcd大于maxxgcd。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解题：先求出原来的数的最大gcd，每个数除以maxxgcd，之后所有数的gcd为1。用分解质因数，最多数拥有的质因子便是新的gcd，大于1就行，除掉那些不含该质因子的数。

cf1047C-Enlarge GCD-（欧拉筛+map+gcd+唯一分解定理）随笔第1张

#include<stdio.h>
#include<iostream>
#include<algorithm>
//#include <bits/stdc++.h>
//cf不承认万能头文件
#include<cstring>
#include<math.h>
#include<map>
#include<string>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

int n;
int prime[10086];
bool vis[10086];
int num[10086];///质因子的个数
int a[300005];///原数组
int cnt;
int maxxgcd;

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

void init()
{
    memset(vis,true,sizeof(vis));
    cnt=0;
    for(int i=2;i<10086;i++)
    {
        if(vis[i])
            prime[cnt++]=i;
        for(int j=0;j<cnt && prime[j]*i<10086;j++)
        {
            vis[ i*prime[j] ]=false;
            if(i%prime[j]==0)
                break;
        }
    }
}

int main()
{
    init();
    while( scanf("%d",&n)!=EOF )
    {
        memset(num,0,sizeof(num));///每次清0
        maxxgcd=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            maxxgcd=gcd( maxxgcd,a[i] );
        }
        for(int i=1;i<=n;i++)
            a[i]=a[i]/maxxgcd;
        map<int,int>mp;
        int maxx=-1;
        for(int i=1;i<=n;i++)
        {
            int x=a[i];
            for(int j=0;j<cnt;j++)
            {
                if( x%prime[j]==0 )
                {
                    num[ prime[j] ]++;///小素数直接用数组存,如果也用map很费时间，每次运用一个map都要logn
                    maxx=max( num[ prime[j] ],maxx);
                    while(x%prime[j]==0)
                        x=x/prime[j];

                }
                if(x==1)
                    break;
            }
            if(x!=1)///遍历完10000以内的素数后，如果x还大于1，则是大素数，大素数用map存
            {
                mp[x]++;
                maxx=max(mp[x],maxx);
            }
        }
        if(maxx==-1)///若没有不同的质因子，此时a[i]必然全部都是1,也就没办法获取任何一个素数因子，不会改变maxx
            printf("-1\n");
        else
            printf("%d\n",n-maxx);
    }
    return 0;
}