Upgrading Array

卧薪尝胆，厚积薄发。

Upgrading Array

Date: Thu Jul 19 17:05:48 CST 2018

In Category: NoCategory

Description：

给定 $n$ 个数 $a_i$ ，以及大小为 $m$ 的质数集合 $b_i$ ，定义 $f$ 函数： $f(1) = 0$ ，令 $p$ 为 $s$ 的最小质因子，若 $p$ 不在 $b$ 中，则 $f(s) = f(\frac s p) + 1$ ，否则 $f(s) = f(\frac s p)−1$ 现在你可以对 $a$ 做任意次操作，每次操作可以选择一个 $r$ ，使得 $a_1,a_2,\dots,a_r$ 同除以 $GCD(a_1,a_2,\dots,a_r)$ ，求通过操作后能得到的 $\begin{align}\sum^n_{i=1}f(a_i)\end{align}$ 最大值

$1\le n,m\le 5000$

Solution：

一个 $r$ 只能操作一次令 $G_r = GCD(a_1,a_2,\dots,a_r)$ ，显然 $G_i |G_j(i > j)$ 因此若选择 $ i $ 操作，则 $ j(j > i) $ 都无法执行，且操作 $ j(j > i) $ 的影响也包含在 $ i $ 中。

从 $ n $ 开始一位位贪心，若操作能增大答案就执行操作。

正确性：若当前能增大答案不选择增大，则若之后都不进行操作，显然不优；若之后进行操作，则当前执行操作的影响也被包含在其中，注意贡献是可减的，所以在当前位置操作不会更劣。

计算贡献时暴力根号分解数字即可。

注意有些贡献已在后面加了，记一个 $cur$ 表示已有的贡献。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 5010

int a[MAXN],b[MAXN];

#define MAXA 1000001

map<int,bool> p;

bool isprime[MAXA];

int prime[MAXA / 3],tot = 0;

map<int,int> F;

void sieve()

{

	for(int i = 2;i < MAXA;++i)isprime[i]= true;

	for(int i = 2;i < MAXA;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] < MAXA;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

int f(int s)

{

	if(s == 1)return 0;

	if(F.find(s) != F.end())return F[s];

	int ans = 0,num = s;

	for(int k = 1;prime[k] * prime[k] <= num;++k)

	{

		if(num % prime[k] == 0)

		{

			bool isbad = p[prime[k]];

			while(num % prime[k] == 0)

			{

				num /= prime[k];

				if(isbad)--ans;

				else ++ans;

			}

		}

	}

	if(num != 1)

	{

		if(p[num])--ans;

		else ++ans;

	}

	return F[s] = ans;

}

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

int g[MAXN];

int main()

{

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

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

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

	for(int i = 1;i <= m;++i)p[b[i]] = true;

	sieve();

	g[1] = a[1];

	for(int i = 2;i <= n;++i)g[i] = gcd(g[i - 1],a[i]);

	int cur = 0;

	int ans = 0;

	for(int i = 1;i <= n;++i)ans += f(a[i]);

	for(int i = n;i >= 1;--i)

	{

		if(f(g[i]) + cur < 0)

		{

			ans -= (f(g[i]) + cur) * i;

			cur -= f(g[i]) + cur;

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051