首页 > 其他 > 详细

CF 1047 C. Enlarge GCD

时间:2018-09-25 13:51:45      阅读:151      评论:0      收藏:0      [点我收藏+]

传送门

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

题意

给你n个数,移除最少的数字是剩下的数字GCD大于初始GCD

思路

需要一点暴力的技巧,先求出初始GCD为g,并统计每个数字的个数这是减少复杂度的关键,令ans=0,我们从i=g+1开始枚举GCD为i的个数,进行统计每次更新ans=min(ans,n-cnt)
需要注意的是某个数的因子依然是那个数倍数的因子,如2 4 8.这样可以避免重复统计。具体看代码

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1.5e7+5;
int a[maxn],num[maxn];
int main(){
    int n,i,j,h;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("in.txt","r",stdin);
    cin>>n;
        int g,m=0,ans=n;
    //  memset(a,0,sizeof(a));
        for(i=1;i<=n;i++){
            cin>>h;
            if(i==1) g=h;
            else g=__gcd(g,h);
            num[h]++;
            if(h>m) m=h;
        }
        //cout<<g<<endl;
        for(i=g+1;i<=m;i++){
            if(a[i]==0){
                int cnt=0;
                for(j=i;j<=m;j+=i)
                a[j]=1,cnt+=num[j];
                ans=min(ans,n-cnt);
            }
        }
        if(ans==n) cout<<-1<<endl;
        else cout<<ans<<endl;
    return 0;
}

CF 1047 C. Enlarge GCD

原文:https://www.cnblogs.com/mch5201314/p/9699016.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!