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 ;
}