Codeforces 851D

发表于 |

题目

给$N$个数$a_1$到$a_N$，可以进行2种操作：（1）将某个数删去，费用为$x$；（2）将某个数$+1$，费用为$y$。操作（2）可以对一个数操作任意次。问：将这个数列变为空的或者非空但是整个数列的$gcd$不为1的最小费用是多少。

数据范围

$1\le N \le 5\times 10^5\quad 1\le x,y,\le 10^9 \quad 1\le a_i \le 10^6$

做法

枚举整个数列的$gcd$，维护最小的费用。一个优化是，可以将$gcd$按所含有的质数分类，这样枚举质数就行，虽然会重复枚举一些$gcd$，但不会漏。所以，答案是正确的。

假设当前枚举的质数为$p$，那么，我们需要将每个数$a$删掉或者将它变为$kp$，其中$k$是使得$kp\ge a$的最小的$k$（这样+1操作的费用最小）。对于在$[kp+1,(k+1)p]$范围内的数$a$，对其若干次+1操作比删去操作更优，当且仅当$((k+1)p-a)y \le x$。于是操作的分割点为$mid=max(kp+1,\lceil(k+1)p-\frac{x}{y}\rceil)$。对于每个区间的操作的总费用，可以通过前缀和$O(1)$求出。所以总的时间复杂度为枚举的区间的个数，和埃氏筛法复杂度一样$O(NUM\log_2NUM)$。$NUM=max(a_i)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 5;
const int MAX_NUM = 1e6 + 5;
int N;
ll X, Y;
ll num[MAX_NUM << 1], sum[MAX_NUM << 1];
bool notPrime[MAX_NUM];
vector<int> primes;
void eulerEieve(int n)
{
  notPrime[0] = notPrime[1] = true;
  for (int i = 2; i <= n; ++i) {
    if (!notPrime[i]) {
      primes.push_back(i);
    }
    for (int j = 0; i * primes[j] <= n; ++j) {
      int tmp = i * primes[j];
      notPrime[tmp] = true;
      if (i % primes[j] == 0) break;
    }
  }
}
int main()
{
  cin >> N >> X >> Y;
  int x = X / Y;
  int maxNum = 2;
  for (int i = 0; i < N; ++i) {
    int a;
    scanf("%d", &a);
    maxNum = max(maxNum, a);
    num[a]++;
    sum[a] += a;
  }
  for (int i = 1; i < MAX_NUM << 1; ++i) {
    sum[i] += sum[i - 1];
    num[i] += num[i - 1];
  }
  eulerEieve(MAX_NUM);
  ll ans = LLONG_MAX;
  bool hasBigger = false;
  for (int i = 0; i < primes.size(); ++i) {
    int p = primes[i];
    if (hasBigger) break;
    if (!hasBigger && p > maxNum) hasBigger = true;
    ll tmpAns = 0;
    for (int l = 1; l <= maxNum; l += p) {
      int r = l + p - 1;
      int mid = max(r - x, l);
      tmpAns += (num[mid - 1] - num[l - 1]) * X;
      tmpAns += ((num[r] - num[mid - 1]) * r - sum[r] + sum[mid - 1]) * Y;
    }
    ans = min(ans, tmpAns);
  }
  cout << ans << endl;
  return 0;
}

细节

  1. 在枚举质数的时候，为了保险起见，要枚举到比$max(a_i)$大的第一个质数。
  2. 前缀和要开$max(a_i)$的2倍大小。

总结

之前对于比$max(a_i)$大的第一个质数会不会称为答案想了很久，但自己太蠢，没想出来。其实根本不需要考虑这个，只要枚举$gcd$的时候把这个也枚举了就行 。毕竟这是程序竞赛，是可以适当暴力的。