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

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

说明：第一次记录的时候代码是超时的，本校校内赛出题人改编的，数据被缩小了，没有再cf上ac就贴了，很抱歉。另外，也不需要map这个东西，因为我做的校内赛的题a[i]被改成1e8,数组放不下所以需要map，而原题的数据是够范围的。修正时间：2019.7.27.14：26

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

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

比如有5个数6 4 8 16 32最大公约数为2

除以2后变成3 2 4 8 16，除以原本的maxxgcd=2之后，大家都有2这个质因数，唯独3没有，则3的引入全部的公约数中必然会导致公约数变小，3 2 4 8 16的最大公约数则是1，如果不要3，2 4 8 16的最大公约数是2.

返回到原始数组，删掉6之后，4 8 16 32的最大公约数就是4了，比原来的2大。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<map>

#include<string>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

int n;

int prime[];

bool vis[];

int num[];///质因子的个数

int a[];///原数组

int cnt;

int maxxgcd;

int gcd(int a,int b)

{

    if(b==)

        return a;

    return gcd(b,a%b);

}

void init()

{

    memset(vis,true,sizeof(vis));

    cnt=;

    for(int i=;i<;i++)

    {

        if(vis[i])

            prime[cnt++]=i;

        for(int j=;j<cnt && prime[j]*i<;j++)

        {

            vis[ i*prime[j] ]=false;

            if(i%prime[j]==)

                break;

        }

    }

}

int main()

{

    init();

    while( scanf("%d",&n)!=EOF )

    {

        memset(num,,sizeof(num));///每次清0

        maxxgcd=;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            maxxgcd=gcd( maxxgcd,a[i] );

        }

        for(int i=;i<=n;i++)

            a[i]=a[i]/maxxgcd;

        int maxx=-;

        for(int i=;i<=n;i++)

        {

            int x=a[i];

            ///原本的错误代码是for(int j=0;j<cnt;j++) cnt至少也是1000级的，n*cnt直接超时

            for(int j=0;prime[j]*prime[j]<=x;j++)///避免找全部素数，减少时间

            {

                if( x%prime[j]== )

                {

                    num[ prime[j] ]++;///小素数直接用数组存

                    maxx=max( num[ prime[j] ],maxx);

                    while(x%prime[j]==)

                        x=x/prime[j];

                }

                if(x==)

                    break;

            }

            if(x!=)///遍历完10000以内的素数后，如果x还大于1，则是大素数，大素数用map存

            {

                num[x]++;

                maxx=max(num[x],maxx);

            }

        }

        if(maxx==-)///若没有不同的质因子，此时a[i]必然全部都是1,也就没办法获取任何一个素数因子，不会改变maxx

            printf("-1\n");

        else

            printf("%d\n",n-maxx);

    }

    return ;

}

巴特西

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

最新文章

热门文章