CF851 D 枚举思维

给出n个数，你可以对每个数把它变为0，或者增加1，分别需要花费x, y。问把所有数的GCD变为不为1的最小花费是多少。

n的范围5x1e5，a[i]的范围1e6。

开始想通过枚举最终gcd值，然后通过判左右个数以及消费来二分，显然是愚蠢的想法，因为一个数在不同模数下余数并不单调阿！

实际上是枚举gcd值，首先a[i]只有1e6范围，预处理前缀和：cnt[i]表示前a[] < i的个数和，sum[i] 比i小的所有a[]的和。

这样在枚举gcd的倍数值时，只要找到gcd范围内的一个划分，小于该划分的数的余数使用消去消费<增加该数到gcd的倍数的消费，那么只要计算gcd的所有倍数，就能得到该gcd作为最终因子的花费了。

/** @Date    : 2017-09-06 19:32:17

  * @FileName: D.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair<int ,int>

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e6+20;

const double eps = 1e-8;

LL n, x, y;

LL sum[N*2], cnt[N*2];

int main()

{

	while(cin >> n >> x >> y)

	{

		MMF(cnt);

		MMF(sum);

		for(int i = 0; i < n; i++)

		{

			LL t;

			scanf("%lld", &t);

			cnt[t]++;

			sum[t] += t;

			/*if(n <= 1)

			{

				printf("%d\n", t==1?min(x,y):0);

				return 0;

			}*/

		}

		for(int i = 1; i < N*2; i++)

			cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];

		LL ans = 1e16;

		for(LL i = 2; i <= 1000000; i++)

		{

			LL t = 0;

			for(LL j = i; j < 1000000 + i; j+=i)

			{

				LL ma = max(j - i + 1, j - x / y);

				t += (cnt[ma - 1] - cnt[j - i]) * x;//直接消去

				t += ((cnt[j] - cnt[ma - 1]) * j - (sum[j] - sum[ma - 1])) * y;

			}

			if(t < ans && t >= 0)

				ans = t;

		}

		printf("%lld\n", ans);

	}

    return 0;

}

巴特西

CF851 D 枚举思维

最新文章

热门文章

巴特西

CF851 D 枚举 思维

最新文章

热门文章

CF851 D 枚举思维