埃氏筛+线段树——cf731F

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

从2e5-1依次枚举每个数作为主显卡，然后分段求比它大的数的个数，这里的复杂度是调和级数ln2e5,即埃氏筛的复杂度、、

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 200005

int cnt[N],n;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

ll num[N<<];

void update(int pos,int v,int l,int r,int rt){

    if(l==r){

        num[rt]+=v;

        return;

    }

    int m=l+r>>;

    if(pos<=m)update(pos,v,lson);

    else update(pos,v,rson);

    num[rt]=num[rt<<]+num[rt<<|];

}

ll query(int L,int R,int l,int r,int rt){

    if(L<=l && R>=r){

        return num[rt];

    }

    int m=l+r>>;

    ll res=;

    if(L<=m)res+=query(L,R,lson);

    if(R>m)res+=query(L,R,rson);

    return res;

}

int main(){

    cin>>n;

    for(int i=;i<=n;i++){

        int x;scanf("%d",&x);

        cnt[x]++;

    }

    ll ans=;

    for(ll i=;i>=;i--)if(cnt[i]){

        ll tmp=;

        update(i,cnt[i],,,);

        for(ll j=;j*i<=;j++)

            tmp+=query(j*i,min(200000ll,(j+)*i-),,,)*i*j;

        ans=max(ans,tmp);

    }

    cout<<ans<<endl;

}