CF1614D1 Divan and Kostomuksha (easy version)

发布时间:2024年01月19日

Divan and Kostomuksha (easy version)

传送门

题面翻译

给定一个序列 a a a ,定义其权值为:

Σ i = 1 n gcd ? ( a 1 , a 2 , . . . , a i ) \Sigma_{i=1}^n\gcd(a_1,a_2,...,a_i) Σi=1n?gcd(a1?,a2?,...,ai?)

现在你可以重排 a a a ,求这个权值的最大值。

本题与同场 D2 的唯一差别在于 a i a_i ai? 的范围。

题目描述

This is the easy version of the problem. The only difference is maximum value of a i a_i ai?.

Once in Kostomuksha Divan found an array a a a consisting of positive integers. Now he wants to reorder the elements of a a a to maximize the value of the following function:
Σ i = 1 n gcd ? ( a 1 , ? a 2 , ? … , ? a i ) , \Sigma_{i=1}^n \operatorname{gcd}(a_1, \, a_2, \, \dots, \, a_i), Σi=1n?gcd(a1?,a2?,,ai?),
where gcd ? ( x 1 , x 2 , … , x k ) \operatorname{gcd}(x_1, x_2, \ldots, x_k) gcd(x1?,x2?,,xk?) denotes the greatest common divisor of integers x 1 , x 2 , … , x k x_1, x_2, \ldots, x_k x1?,x2?,,xk? , and gcd ? ( x ) = x \operatorname{gcd}(x) = x gcd(x)=x for any integer x x x.

Reordering elements of an array means changing the order of elements in the array arbitrary, or leaving the initial order.

Of course, Divan can solve this problem. However, he found it interesting, so he decided to share it with you.

输入格式

The first line contains a single integer n n n ( 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105 ) — the size of the array a a a .

The second line contains n n n integers a 1 , ? a 2 , ? … , ? a n a_{1}, \, a_{2}, \, \dots, \, a_{n} a1?,a2?,,an? ( 1 ≤ a i ≤ 5 ? 1 0 6 1 \le a_{i} \le 5 \cdot 10^6 1ai?5?106 ) — the array a a a .

输出格式

Output the maximum value of the function that you can get by reordering elements of the array a a a .

样例 #1

样例输入 #1

6
2 3 1 2 6 2

样例输出 #1

14

样例 #2

样例输入 #2

10
5 7 10 3 1 10 100 3 42 54

样例输出 #2

131

提示

In the first example, it’s optimal to rearrange the elements of the given array in the following order: [ 6 , ? 2 , ? 2 , ? 2 , ? 3 , ? 1 ] [6, \, 2, \, 2, \, 2, \, 3, \, 1] [6,2,2,2,3,1] :

gcd ? ( a 1 ) + gcd ? ( a 1 , ? a 2 ) + gcd ? ( a 1 , ? a 2 , ? a 3 ) + gcd ? ( a 1 , ? a 2 , ? a 3 , ? a 4 ) + gcd ? ( a 1 , ? a 2 , ? a 3 , ? a 4 , ? a 5 ) + gcd ? ( a 1 , ? a 2 , ? a 3 , ? a 4 , ? a 5 , ? a 6 ) = 6 + 2 + 2 + 2 + 1 + 1 = 14. \operatorname{gcd}(a_1) + \operatorname{gcd}(a_1, \, a_2) + \operatorname{gcd}(a_1, \, a_2, \, a_3) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4)\\ + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5) + \operatorname{gcd}(a_1, \, a_2, \, a_3, \, a_4, \, a_5, \, a_6)\\= 6 + 2 + 2 + 2 + 1 + 1 = 14. gcd(a1?)+gcd(a1?,a2?)+gcd(a1?,a2?,a3?)+gcd(a1?,a2?,a3?,a4?)+gcd(a1?,a2?,a3?,a4?,a5?)+gcd(a1?,a2?,a3?,a4?,a5?,a6?)=6+2+2+2+1+1=14.
It can be shown that it is impossible to get a better answer.

In the second example, it’s optimal to rearrange the elements of a given array in the following order: [ 100 , ? 10 , ? 10 , ? 5 , ? 1 , ? 3 , ? 3 , ? 7 , ? 42 , ? 54 ] [100, \, 10, \, 10, \, 5, \, 1, \, 3, \, 3, \, 7, \, 42, \, 54] [100,10,10,5,1,3,3,7,42,54].

以上来自洛谷 以上来自洛谷 以上来自洛谷

解题思路

设重排 gcd ? ( a 1 , a 2 , … , a i ) = s u m i \operatorname{gcd}(a_1,a_2,\dots ,a_i)=sum_i gcd(a1?,a2?,,ai?)=sumi? ,有一条很重要的性质:
s u m i + 1 ∣ s u m i sum_{i+1}\mid sum_i sumi+1?sumi?
根据这一条我们这样写出方程,设 f i f_i fi? 表示目前到某个 s u m j sum_j sumj? s u m j = i sum_j=i sumj?=i时, Σ k = 1 j s u m k \Sigma_{k=1}^j sum_k Σk=1j?sumk?的最大值。不难得到:
f i = max ? ( f j + i × ( c n t i ? c n t j ) ) f_i=\max(f_j+i\times (cnt_i?cnt_j)) fi?=max(fj?+i×(cnti??cntj?))
其中 c n t i cnt_i cnti? 表示 i i i 出现的次数。
时间复杂度为 O ( n + p log ? log ? p ) O(n+p\log\log p) O(n+ploglogp) p p p 为值域。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 3e5 + 5, Maxv = 5e6 + 5;
int n, a[Maxn];
int maxx, f[Maxv], cnt[Maxv], tot[Maxv];
inline void work() {
	maxx = INT_MIN;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		maxx = max(maxx, a[i]);
		tot[a[i]] += 1;
	}
	cnt[1] = n;
	for (int i = 2; i <= maxx; i++) {
		for (int j = i; j <= maxx; j += i) {
			cnt[i] += tot[j];
		}
	}
	for (int i = maxx; i >= 1; i--) {
		f[i] = cnt[i] * i;
		for (int j = i + i; j <= maxx; j += i) {
			f[i] = max(f[j] + (cnt[i] - cnt[j]) * i, f[i]);
		}
	}
	cout << f[1] << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}

写完了,去看看进阶版吧。

文章来源:https://blog.csdn.net/BestMonkey/article/details/135688659
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。