# 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.

## 代码

#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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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) {
}
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;
}


418 I'm a teapot