【前缀和】【枚举倍数】 Codeforces Round #432 (Div. 2, based on IndiaHacks Final Round 2017) D. Arpa and a list of numbers

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：给你n个数，一次操作可以选一个数delete，代价为x；或者选一个数+1，代价y。你可以进行这两种操作任意次，让你在最小的代价下，使得所有数的GCD不为1（如果全删光也视作合法）。

我们从1到max(ai)枚举最后都变成的gcd是多少，假设为g，那么所有数都必须变成一个比g大的最小的g的倍数k·g。枚举k，然后在一个区间[(k-1)*g+1,k*g]里，一定存在一个分界点f，使得小于等于f的数全都删去，因为删除的代价小于把它们都变成kg的代价；大于f的数全都变成kg。因为x<=(kg-ai)*y，所以显然这个分界点是kg-ceil(x/y)。不过分界点不一定落在区间里，要讨论一下。

要预处理前缀和cnt(i)表示小于等于i的数的个数，sum(i)表示小于等于i的数的和。

特殊情况：一开始全是1。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int cnt[2000005],n,x,y,a[500005],N;
ll sum[2000005],ans=9000000000000000000ll,nowans;
int main(){
//freopen("a.in","r",stdin);
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
++cnt[a[i]];
sum[a[i]]+=(ll)a[i];
}
N=*max_element(a+1,a+n+1);
if(N==1){
printf("%I64d\n",(ll)n*(ll)min(x,y));
return 0;
}
for(int i=2;i<=N*2;++i){
cnt[i]+=cnt[i-1];
sum[i]+=sum[i-1];
}
for(int i=2;i<=N;++i){
nowans=0;
for(int j=i;j<=N+i;j+=i){
int R=j;
int L=R-i+1;
int upd=R-(int)(ceil((double)x/(double)y)+0.5);
if(upd>=L){
nowans+=(ll)x*(ll)(cnt[upd]-cnt[L-1]);
}
else{
upd=L-1;
}
nowans+=(ll)y*((ll)(cnt[R]-cnt[upd])*(ll)R-(sum[R]-sum[upd]));
}
ans=min(ans,nowans);
}
printf("%I64d\n",ans);
return 0;
}