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

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