Arpa and a List of Numbers

题目描述

Arpa has found a list containing $n$ numbers. He calls a list bad if and only if it is not empty and gcd of numbers in the list is $1$.

Arpa can perform two types of operations:

• Choose a number and delete it with cost $x$.
• Choose a number and increase it by $1$ with cost $y$.

Arpa can apply these operations to as many numbers as he wishes, and he is allowed to apply the second operation arbitrarily many times on the same number.

Help Arpa to find the minimum possible cost to make the list good.

题意概述

给定一个长度为$n$的序列，第$i$个数字为$a_i$。有两种操作：删除一个数，消耗$x$；将一个数加$1$，消耗$y$。求使得序列中所有数的最大公约数大于$1$的最少消耗。

数据范围：$1 \le n \le 5 \times 10^5, \ 1 \le x, y \le 10^9, \ 1 \le a_i \le 10^6$。

算法分析

枚举$[2, 10^6]$中的素数$p$作为最大公约数（合数作为最大公约数的消耗一定不比质数少）。对于序列中的每个数，要么将它删去，要么将它变成不小于它且最小的$p$的倍数。设$d_i=\left\lceil {a_i \over p} \right\rceil \times p -a_i$。显然，若$x \le d_i \times y$，那么将它删去更优，否则将它变成$p$的倍数更优。也就是说，对于$d_i \ge {x \over y}$的数，我们将它删去，否则将它变成$p$的倍数。预处理出前缀和，根据调和级数，可知时间复杂度为$O(a_i\log a_i)$。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

void minify(long long &a, long long b) { b < a && (a = b); }

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager operator > (T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager operator < (T x) {
    write(x); return *this;
  }
} io;

struct Solver {
private:
  static const int N = 1000000;
  static const int M = 1000000;
  int n, x, y, a[N + 1], cnt[N + 1 << 1];
  long long sum[N + 1 << 1];
  int top, prime[N];
  bool vis[N + 1 << 1];
  void input() {
    io > n > x > y;
    for (int i = 1; i <= n; ++ i) io > a[i], ++ cnt[a[i]], sum[a[i]] += a[i];
  }
  void init() {
    for (int i = 1; i <= M << 1; ++ i) cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
    for (int i = 2; i <= M; ++ i) {
      if (! vis[i]) prime[++ top] = i;
      for (int j = 1; j <= top && i * prime[j] <= M; ++ j) {
        vis[i * prime[j]] = true;
        if (! (i % prime[j])) break;
      }
    }
  }
  void process() {
    int p = x / y;
    long long ans = 1000000000000000000ll;;
    for (int i = 1; i <= top; ++ i) {
      long long tmp = 0;
      int delta = prime[i] - p - 1;
      for (int j = 0; j <= N; j += prime[i]) {
        if (delta < 0) {
          tmp += (((long long) cnt[j + prime[i]] - cnt[j]) * (j + prime[i]) - (sum[j + prime[i]] - sum[j])) * y;
        } else {
          tmp += ((long long) cnt[j + delta] - cnt[j]) * x + (((long long) cnt[j + prime[i]] - cnt[j + delta]) * (j + prime[i]) - (sum[j + prime[i]] - sum[j + delta])) * y;
        }
      }
      minify(ans, tmp);
    }
    io < ans < '\n';
  }

public:
  void solve() {
    input(), init(), process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}