欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #511 (Div. 2)C. Enlarge GCD

程序员文章站 2022-05-09 16:18:04
...

http://codeforces.com/contest/1047/problem/C

直接暴力即可。

首先求出所有数的gcd

然后计数:每个数/gcd   结果的个数

最后直接线性筛  边筛边判断   找到含有共同因子最多的数字  去掉不含有这个公共因子的数字  gcd就会变大

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=1.5e7+5;
int n, g, ans, a[N], cnt[M], vis[M];

int main()
{
	scanf("%d",&n);

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

        scanf("%d",&a[i]);
        g = __gcd(a[i],g);
	}

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

        cnt[a[i] / g] ++;
	}

	for(int i = 2;i < M;i ++){

        int tmp = 0;

        if(!vis[i]){

            for(int j = i;j < M;j += i){

                vis[j] = 1;
                tmp += cnt[j];
            }
        }

        ans = max(ans, tmp);

	}

	printf("%d\n",ans?n-ans:-1);
}