CodeForces 402D Upgrading Array

好像没有什么要说的，主要是两个数组的数据范围太大，要做好优化，避免因子的重复计算。

预处理：
首先计算出 a[] 初始时的 Max = sigma f(a[i]) (1 <= i <= n).

然后，对于 a[i] ，计算出所有的 gcd[i] ，可以从左边开始递推，时间复杂度o(n).

从gcd[n] 开始往左遍历，若f( gcd[ i ] ) < 0,Max -= i*f ( gcd[i] )，site = i。

继续枚举 i ,若 f(gcd[i] / gcd[site]) < 0,则 Max -= i*f( gcd[i] / gcd[site]),site = i , 直到 i < 1;

代码又写的很长 . . . . . .

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long int
#define ULL unsigned long long int
#define _LL __int64
#define _INF 0x3f3f3f3f
#define INF 40000000
#define Mod 1000000009

using namespace std;

int Top_Prime;

int prime[100000];

bool mark[100000];

int pg[5010];

int a[5010],b[5010];

int n,m;

struct N
{
    int s,f;
    N *l,*r;
}*root;

N *creat()
{
    N *p = (N *)malloc(sizeof(N));
    p->l = NULL,p->r = NULL;
    return p;
}

void Insert(N *&root ,int s,int f)
{
    if(root == NULL)
    {
        root = creat();
        root->s = s;
        root->f = f;
        return ;
    }

    if(s < root->s)
    {
        Insert(root->l,s,f);
    }
    else
    {
        Insert(root->r,s,f);
    }
}


bool Is_good(int p)
{
    int s = 1,e = m;

    int mid = (s+e)>>1;

    while(s < e)
    {
        if(b[mid] == p)
            return false;
        if(p < b[mid])
            e = mid-1;
        else
            s = mid+1;
        mid = (s+e)>>1;
    }

    if(p == b[(s+e)>>1])
        return false;
    return true;
}

int Query(N *root,int s)
{
    if(root == NULL)
        return -1;
    if(root->s == s)
        return root->f;

    if(s < root->s)
        return Query(root->l,s);
    return Query(root->r,s);
}

int Cal_F(int a)
{
    if(a == 1)
        return 0;

    int temp = Query(root,a);

    if(temp != -1)
        return temp;
    int i;
    for(i = 0;i < Top_Prime; ++i)
    {
        if(a%prime[i] == 0)
            break;
    }

    int r;

    if(i == Top_Prime)
        r = a;
    else
        r = prime[i];

    temp = Cal_F(a/r) + (Is_good(r) == true ? 1 : -1);

    Insert(root,a,temp);

    return temp;
}

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

int main()
{
    memset(mark,false,sizeof(mark));

    int i,j;

    for(i = 2;i <= 100000; ++i)
    {
        if(mark[i] == false)
        {
            for(j = i+i;j <= 100000; j += i)
            {
                mark[j] = true;
            }
        }
    }

    Top_Prime = 0;

    for(i = 2;i <= 100000; ++i)
    {
        if(mark[i] == false)
        {
            prime[Top_Prime++] = i;
        }
    }

    scanf("%d %d",&n,&m);

    for(i = 1;i <= n; ++i)
    {
        scanf("%d",&a[i]);
    }

    for(i = 1;i <= m; ++i)
    {
        scanf("%d",&b[i]);
    }

    sort(b+1,b+1+m);

    int Max = 0;

    for(i = 1;i <= n; ++i)
    {
        Max += Cal_F(a[i]);
    }

    pg[1] = a[1];


    for(i = 2;i <= n; ++i)
    {
       pg[i] = gcd(pg[i-1],a[i]);
    }

    int l;

    for(i = n;i >= 1; --i)
    {
        int tt = Cal_F(pg[i]);
        if(tt < 0)
        {
            Max -= i*tt;
            l = i;
            break;
        }
    }

    for(--i ; i >= 1; --i)
    {
        int tt = Cal_F(pg[i]/pg[l]);

        if(tt < 0)
        {
            Max -= i*tt;
            l = i;
        }
    }

    printf("%d\n",Max);

    return 0;
}

CodeForces 402D Upgrading Array,布布扣,bubuko.com

CodeForces 402D Upgrading Array

原文：http://blog.csdn.net/zmx354/article/details/21371623