Codeforces Round #757 (Div. 2) - D2. Divan and Kostomuksha (hard version)

GCD + DP + 调和级数/埃式筛

[Problem - D - Codeforces](https://codeforces.com/contest/1610/problem/D)

题意

给出一个长度为 \(n\;(1<=n<=10^5)\) 的数组 \(a[i]\;(1<=a[i]<=2*10^7)\)

可以重新排列 \(a\) 数组，使得 \(\sum\limits_{i=1}^n\gcd(a_1,a_2,...,a_i)\) 最大

思路

设 \(cnt[x]\) 为 \(x\) 的倍数有多少个，easy版本可用调和级数，hard版本可 \(n*\sqrt{a[i]}\) 分解因数
若 \(x\) 开头，最优策略是把 \(x\) 的倍数全都紧接着放在 \(x\) 之后，他们的贡献为 \(cnt[x]*x\)
设以 \(x\) 作为 \(gcd(a[1])\) 的答案为 \(f[x]\)（这里并非 \(a[1]\) 开头 \(gcd(a[1])\) 就是 \(a[1]\), \(a[1]\) 的任何因数都可以）, 把 \(x\) 的倍数 \(y\) 放到 \(x\) 的前面时会更优，因此 \(f[x]->f[y]\) 转移
在 \(f[x]\) 向 \(f[y]\) 转移的过程中，除了 \(x\) 的倍数 \(cnt[x]\) 个以外的 \(n-cnt[x]\) 个数对贡献并没有改变

且是 \(x\) 的倍数但不是 \(y\) 的倍数的数的贡献也没有改变，只有 \(cnt[y]\) 个数的贡献由 \(x\) 变成了 \(y\), 因此转移方程为

\(f[y]=max(f[y],f[x]+(y-x)*cnt[y])\)
easy 版本可用调和级数；hard版本考虑优化，其实并非 \(x\) 向它的每个倍数 \(y\) 都需要转移，只需要转移向素数倍的 \(y\) 就行（感受一下，应该也可以证）

类比埃式筛，时间复杂度为 \(O(nloglogn)\)

代码

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

typedef long long ll;

typedef pair<int, int> PII;

const int N = 2e7 + 10;

ll f[N];

int n;

ll cnt[N];

int pr[N / 5], p[N];

int t;

void get_primes(int n)

{

	p[1] = 1;

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

	{

		if (!p[i])

		{

			p[i] = i;

			pr[++t] = i;

		}

		for (int j = 1; j <= t && pr[j] <= n / i; j++)

		{

			p[i * pr[j]] = pr[j];

			if (p[i] == pr[j])

				break;

		}

	}

}

int main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	get_primes(N - 10);

	cin >> n;

	for (int i = 1, x; i <= n; i++)

	{

		cin >> x;

		for (int j = 1; j <= x / j; j++)

		{

			if (x % j == 0)

			{

				cnt[j]++;

				if (j != x / j)

					cnt[x / j]++;

			}

		}

	}

	f[1] = n;

	for (int x = 1; x <= N - 10; x++)

	{

		for (int i = 1; i <= t && pr[i] <= (N - 10) / x; i++)

		{

			int y = x * pr[i];

			f[y] = max(f[y], f[x] + (y - x) * cnt[y]);

		}

	}

	cout << *max_element(f + 1, f + N - 9) << endl;

    return 0;

}

巴特西

Codeforces Round #757 (Div. 2) - D2. Divan and Kostomuksha (hard version)

GCD + DP + 调和级数/埃式筛

题意

思路

代码

最新文章

热门文章