【链接】h在这里写链接
【题意】
定义bad list是一个非空的、最大公约数为1的序列。给定一个序列，有两种操作：花费x将一个元素删除、花费y将一个元素加1，问你将这个序列变为good list所需要的最小花费是多少。
【题解】
枚举gcd为i.
这里的枚举,并不是说确切这些数字的gcd就是i;
而是枚举这些数的gcd是i的倍数。
这样的话,每个数字都必须是i的倍数。
(然后,我们只要贪心地让每个数都变成i的倍数就好了,最近的i的倍数,这样肯定是最优的)
(最后gcd到底是多少,并不重要,只要肯定它是i的倍数就好,i>=2);
(最后的gcd为多少,其实取决于我们的贪心结果,它是一个i的倍数,且是在满足花费最小的情况下的一个i的倍数)
(那么,虽然你i的倍数还有其他,也能组成i的倍数的gcd,但是我们不要那些数字了,因为那些数字肯定没有这个gcd来得优,因为你的花费肯定没有我这样贪心选的花费来得低.
这里枚举i只要枚举1..10^6里面的素数就好。
因为不管你的gcd是多少,它肯定是某个素数的倍数
然后,我们只要对0..i,i+1..2i,2i+1..3i....这些范围里面的数字,优先选一个离它最近的i的倍数,加成它就好了.
又或者,你觉得加上去不划算->直接删掉更好。那么就不加。
可以肯定.
对于L = t*i,R = (t+1)*i
L..R-(x/y)-1肯定是删掉更优.
R-(x/y)..R肯定是一个一个加到R更优。
每一个L..R都能用前缀和O(1)算出来最小花费.
(sum[i]表示a[]中小于等于i的数和,num[i]表示a[]中小于等于i的数的个数)
其中一个一个加到R的情况比较麻烦。
要这么写
->R*(num[R-1]-num[R-x/y-1]) -
sum[R-1]-sum[R-x/y-1];
sum[R-1]-sum[R-x/y-1];
这个减号左边是这个范围的数全部加成R之后的和.
减号右边是这个范围里的数原来的全部和.
则差值,就是这个范围里面的数全都加成R需要的操作数了。
把这个乘上y就是花费了。
取所有i的花费最小值就好。
前缀和要处理到2e6.
因为可能会出现gcd比如为99 99999的倍数的情况。
比如a[1] = 99 99999 a[2] = 100 0000
然后删掉一个数花费为1 数字加上1的花费为y(y>1)
这样的话,我们会处理【99 99999 +1 .. 99 99999 *2】这个区间了。
(然后把a[2]删掉)
处理这区间肯定要用到大于1e6的前缀和了。
【错的次数】
【反思】
枚举gcd的质因子i,注意到每个数必然都是i的倍数。
然后一个区间一个区间地处理。
区间里面有一些东西能用前缀和处理出来。
快速得到答案。
不用拘泥于gcd具体是什么。
【代码】
/*
所有数字都等于1
①把n-1个数字删掉,剩下一个数字,再递增1? (n-1)*x + y = n*x + y - x
②或者,把n个数字都加上1,花费为n*y
n*x + y - x > n*y
n*x - n*y > x - y;
n*(x-y) > (x-y)
如果x > y
选第二种
如果x < y
选第一种
但是,也可以其中一些数字加上1,剩下的全删掉.
一个数字加上1之后,就不用删掉了.
所以,哪一个花费比较低,就优先操作那一个就好.
那最后如果全是选删掉怎么办?
那就只能留一个选增加了。
枚举最后的gcd为i.
然后如果一个数字比它小的话,就看一下加的费用和删的费用,哪一个比较大。
选那个费用比较小的。
然后选取费用差值最小的那个,以防全都被删掉了。
O(N^2)的复杂度了
比i小的数字,肯定是要删掉的->不一定,可以加到gcd.
但加到一定程度,就一定要删掉的。
因为删掉的花费不变,但是你一直增加,花费是会变多的。
但是也不一定能被i整除,整体的gcd就是i啊
give up. */ #include <bits/stdc++.h>
using namespace std; const int N = 2e6; int n;
long long num[N+10], sum[N+10],x,y,ans = -1; void inandpre() {
cin >> n >> x >> y;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
num[t]++, sum[t] += t;
} for (int i = 1; i <= N; i++)
sum[i] += sum[i - 1],num[i]+=num[i-1];
} const int M = 1e6;
bool iszs[M + 10];
vector <int> zsb;
void getzhishu() {
memset(iszs, true,sizeof iszs);
for (int i = 2; i <= M; i++){
if (iszs[i]) zsb.push_back(i);
int len = zsb.size();
for (int j = 0; j <= len - 1; j++) {
int t = zsb[j];
if (i*t > M) break;
iszs[i*t] = false;
if (i%t == 0) break;
}
}
} void meiju() {
for (int ii = 0; ii <= (int) zsb.size()-1; ii++) {
long long rest = 0;
int i = zsb[ii];
for (int j = i; j <= N; j += i) {
long long temp = x / y;
long long ju = j - temp,l = j-i+1,r = j;
ju = max(ju, l);
rest += x*(num[ju-1] - num[l - 1]);//删掉
rest += y*((num[r - 1] - num[ju - 1])*r - (sum[r-1]-sum[ju-1]));//加上
}
if (ans == -1)
ans = rest;
else
ans = min(ans, rest);
}
} void out() {
cout << ans << endl;
} int main() {
//freopen("F:\\rush.txt", "r", stdin);
ios::sync_with_stdio(0);
inandpre();
getzhishu();
meiju();
out();
return 0;
}