Codeforces 850B

题意：

给出一个序列，两种操作：

1.删除一个数，代价为x

2.给一个数+1，代价为y

求最小代价，使这个序列不为空，且所有的数的gcd>1

n<=5e5,a[i]<=1e6

其实思路还是很简单的。

可以发现a[i]只有1e6，那么我们直接暴力枚举修改后的数列的gcd(为下文方便，我们假设挡当前枚举的数为i)。

那么对于一个不是i的倍数的数，它就是要么删，要么就是加到最接近它的i的倍数。

所以接下来就是暴力枚举i的倍数。

如果我们当前的倍数为j，那么易发现大小[ji-1,ji-x/y]的数，就是累加到ji，大小[(j-1)i+1,ji-x/y-1]的数就是删掉。

那这个代价怎么算？

用个桶+前缀和搞下就行了。

#include<cstdio>

#include<ctime>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<string>

#define rg register

#define il inline

#define vd void

#define ll long long

#define maxn 2000010

#define N 500010

#define For(i,x,y) for (rg int i=(x);i<=(y);i++)

#define Dow(i,x,y) for (rg int i=(x);i>=(y);i--)

#define cross(i,k) for (rg int i=first[k];i;i=last[i])

using namespace std;

il ll max(ll x,ll y){return x>y?x:y;}

il ll min(ll x,ll y){return x<y?x:y;}

il ll read(){

    ll x=;int ch=getchar(),f=;

    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();

    if (ch=='-'){f=-;ch=getchar();}

    while (isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*f;

}

int n,Max,a[N];

ll k,l,r,x,y,z,ans,Sum,cnt[maxn],sum[maxn];

int main(){

    n=read(),x=read(),y=read(),z=x/y;

    For(i,,n) a[i]=read(),Max=max(Max,a[i]),cnt[a[i]]++;

    For(i,,Max*) sum[i]=sum[i-]+cnt[i]*i,cnt[i]+=cnt[i-];

    ans=1000000000000000ll;

    For(i,,max(Max,)){

        Sum=;

        if (Max%i==) k=Max/i;

            else k=Max/i+;

        if (i<=z)

            For(j,,k){

                l=(j-)*i,r=j*i;

                Sum+=(r*(cnt[r-]-cnt[l])-sum[r-]+sum[l])*y;

            }

        else

            For(j,,k){

                l=(j-)*i,r=j*i;

                Sum+=(cnt[r-z-]-cnt[l])*x+(r*(cnt[r-]-cnt[r-z-])-sum[r-]+sum[r-z-])*y;

            }

        ans=min(ans,Sum);

    }

    printf("%lld",ans);

}