题面
分析
1.暴力做法
首先先把每个数除以gcd(a1,a2…,an)gcd(a_1,a_2 \dots,a_n )gcd(a1,a2…,an)
可以O(namax)O(n\sqrt {a_{max}})O(namax)的时间内分解出所有数的质因数,然后统计出现次数最多的质因数,设最多出现次数为xxx,然后把其他的数去掉就可以了,答案为n−xn-xn−x
例:
n=4,a={6,9,15,30}n=4,a=\{6,9,15,30\}n=4,a={6,9,15,30}
处理后a={2,3,5,10}a=\{2,3,5,10\}a={2,3,5,10}
2=22=22=2
3=33=33=3
5=55=55=5
10=2×510=2 \times 510=2×5
我们可以看出质因数2出现了2次,3出现了1次,5出现了2次
出现次数最多的质因数为2或5,均出现了2次
故答案为4-2=2
2.优化
可以看出算法的瓶颈在质因数分解,我们考虑如何优化质因数分解算法
这是一般的质因数分解算法
set<int>S;
for(int i=2; i<=x; i++) {
while(x%i==0 &&x != i) {
n/=i;
S.push(i);
}
if(x == i) {
S.push(i)
break;
}
}
该算法的时间复杂度为O(x)O(\sqrt x)O(x)
问题在于该算法需要枚举能整除x的数,效率比较低,如果对于每个数x,我们知道能被整除x的最小质数minprime[x],算法的效率就可以提高了
那么如何求出minprime呢?
我们想到线性筛法的过程
for(int i=2; i<=n; i++) {
if(!vis[i]) {
prime[++k]=i;
}
for(ll j=1; j<=k&&(ll)i*prime[j]<=n; j++) {
minprime[(ll)i*prime[j]]=prime[j];
vis[(ll)i*prime[j]]=1;
if(!(i%prime[j])) break;
}
}
其中的每个合数只会被筛一次,而prime[j]不正好是能整除i×prime[j]i\times prime[j]i×prime[j]的最小质数吗?
因此可以把线性筛改成这个样子
for(int i=2; i<=n; i++) {
if(!vis[i]) {
minprime[i]=i;
prime[++k]=i;
}
for(ll j=1; j<=k&&(ll)i*prime[j]<=n; j++) {
minprime[(ll)i*prime[j]]=prime[j];
vis[(ll)i*prime[j]]=1;
if(!(i%prime[j])) break;
}
}
我们就求出了minprime,注意若p是质数,minprime[p]=p
然后可以写出分解质因数的算法
if(!vis[x]||x==1) {//如果是1或质数,直接返回
cnt[x]++;
return;
}
while(x>1) {
int t=minprime[x];
cnt[t]++;
while(x%t==0&&x!=1) {
x/=t;
}
}
因为每次循环x至少要除以2,所以时间复杂度为O(log2x)O(log_2 x)O(log2x)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 300005
#define maxv 15000005
using namespace std;
typedef long long ll;
inline int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int n;
int a[maxn];
int vis[maxv];
int minprime[maxv];
int cnt[maxv];
int prime[maxv];
int k=0;
void sieve(int n) {
for(int i=2; i<=n; i++) {
if(!vis[i]) {
minprime[i]=i;
prime[++k]=i;
}
for(ll j=1; j<=k&&(ll)i*prime[j]<=n; j++) {
minprime[(ll)i*prime[j]]=prime[j];
vis[(ll)i*prime[j]]=1;
if(!(i%prime[j])) break;
}
}
}
void div(int x) {
if(!vis[x]||x==1) {
cnt[x]++;
return;
}
while(x>1) {
int t=minprime[x];
cnt[t]++;
while(x%t==0&&x!=1) {
x/=t;
}
}
}
int main() {
scanf("%d",&n);
sieve(15000000);
int g=0;
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
g=gcd(g,a[i]);
}
for(int i=1; i<=n; i++) {
a[i]/=g;
}
for(int i=1; i<=n; i++) {
div(a[i]);
}
int ans=0;
for(int i=2; i<=15000000; i++) {
ians=max(ans,cnt[i]);
}
if(ans==0) printf("-1\n");
else printf("%d\n",n-ans);
}