CF850B Arpa and a list of numbers 题解枚举

题目链接：https://codeforces.com/problemset/problem/850/B

题目大意

我们定义一个数列是 ”坏的数列” 当且仅当这个数列不为空且数列中所有元素的最大公约数为 \(1\)。

如果一个数列不是一个 ”坏的数列”，那么它就是一个 ”好的数列”。

现在给你一个长度为 \(n\) 的数列 \(a\)，你可以对这个数列进行如下两种类型的操作：

操作1：删除数列中的一个元素，对应的花费为 \(x\)；
操作2：选择数列中的任意一个元素，并将这个元素的数值增加 \(1\)。

你可以执行任意次上述操作。你也可以对数列中的同一个元素执行任意次操作2。

问：使数列变为一个 ”好的数列” 所需的最小总花费。

解题思路

让我们定义 \(cost(g)\) 表示让数列的 gcd 为 \(g\) 时的最小总花费。则答案为所有 \(g \gt 1\) 对应的 \(cost(g)\) 的最小值。接下来我们来思考如何计算 \(cost(g)\)。

对于数列中的任何一个元素，设这个元素的数值为 \(c\)，则我们可以对其进行如下两种修改之一：

删除这个元素，这将花费 \(x\)；
将这个元素增加最少的 \(1\) 使其能被 \(g\) 整除，对应的最小的操作次数是 \(\lceil \frac{c}{g} \rceil - c\)

这也就是说，对于一个数值为 \(c\) 的元素，\(cost(g) = \min(x, y \times (\lceil \frac{c}{g} \rceil - c))\)

我们只需要去迭代所有可能的 \(\lceil \frac{c}{g} \rceil\)

在正式进入解题方案的主要思路之前，我们先定义两个有用的函数：

\(cnt(l, r)\)：这个函数返回满足条件 \(1 \le a_i \le r\) 的下标 \(i\)
\(sum(l, r)\)：这个函数返回满足条件 \(1 \le a_i \le r\) 的所有 \(a_i\)

上述两个函数都可以前缀和预处理然后 \(O(1)\)

现在，对于某一个确定的 \(g\) 的倍数 \(k\)，我们需要去统计一下区间 \((k-g, k]\) 范围内的数带来的花费（因为这个区间范围内的数要变成 \(g\) 的倍数都需要增加到 \(k\)）。

对于区间 \((k-g, k]\)，我们能够找到一个 \(f\)，满足：

数值在区间 \((k-g, f]\)
数值在区间 \((f, k]\) 范围内的所有元素加到 \(k\)

\(f\)

\((g - f) \times y = \frac{x}{y} \Rightarrow f = g - \min(g, \frac{x}{y})\)。

（这个公式可以理解成：计算一个数字 \(p\)，则 \((g, f-p]\) 都选择删除，\((f-p, f]\) 都选择加到 \(f\)，具体看我的代码可能更好理解一些）

总的花费是 \(cnt(k-g+1, k-\lfloor f \rfloor) \times x + (cnt(k - \lfloor f \rfloor + 1, k) \times k - sum(k - \lfloor f \rfloor +1 , k)) \times y\)。

时间复杂度 \(O(\max a_i \log \max a_i)\)。

需要考虑特殊情况就是：所有数都等于 \(1\)

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int n, m, a;
long long x, y, cnt[maxn], sum[maxn], ans = (1ll<<60);
 
long long cal(int g)
{
  int z = min(1ll*g, (x - 1) / y + 1);
  long long res = 0;
  for (int p = g; p <= 2*m; p += g)
  {
    long long c = cnt[p] - cnt[p-z];
    long long s = sum[p] - sum[p-z];
    long long tmp = (cnt[p-z] - cnt[p-g]) * x + (c * p - s) * y;
    res += tmp;
  }
  return res;
}
 
int main()
{
  scanf("%d%lld%lld", &n, &x, &y);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &a);
    m = max(m, a);
    cnt[a]++;
    sum[a] += a;
  }
  for (int i = 1; i <= 2*m; i++)
  {
    cnt[i] += cnt[i-1];
    sum[i] += sum[i-1];
  }
  for (int g = 2; g <= max(m, 2); g++)
    ans = min(ans, cal(g));
  printf("%lld\n", ans);
  return 0;
}