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

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

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

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

题意:给出一串数,要求出删去最少个数字,使这串数的gdc增大。

题解:开始我想的dp求最长的gcd大于原gcd的字串的长度,但是时间太长了。看来别人的题解才知道。先记录下每个数字出行的次数,然后从原来的gcd + 1开始枚举,找出所有大于gcd的字串中的最长长度。但是直接这样的话是n平方的复杂度,所以有了一个flag标记数组。举个例子,因为(gcd = 3 的数个数一定) >= (gcd = 6的个数),而在求gcd = 3 的数的个数的时候就已经访问了gcd = 6的数了,所以可以标记gcd = 6,在计算gcd = 6的数的个数的时候可以直接跳过。这样其实相当于每个数就只访问了一次。时间负杂度就降下来了。

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 15000000;
int vis[maxn],a[maxn],flag[maxn];

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a % b);
}

int main()
{
    memset(flag,0,sizeof(flag));
    memset(vis,0,sizeof(vis));

    int n;
    int gc = 0;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a[i]);
        vis[a[i]]++;
        if(!gc)
            gc = a[i];
        else
            gc = gcd(gc,a[i]);
    }

    int ans = 0;
    for(int i = gc + 1;i <= maxn;i++)//从gc + 1开始枚举
    {
        if(!flag[i])
        {
            int cnt = 0;
            for(int j = i; j <= maxn; j += i)
            {
                cnt += vis[j];
                flag[j] = 1;//每个数实际只访问了一次
            }
            ans = max(ans,cnt);
        }
    }

    if(ans > 0)     printf("%d\n",n - ans);
    else            printf("-1\n");

    return 0;
}