埃氏筛+线段树——cf731F

矫情吗；* 2023-10-12 08:21 35阅读 0赞

从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<<2];
    void update(int pos,int v,int l,int r,int rt){
        if(l==r){
            num[rt]+=v;
            return;
        }
        int m=l+r>>1;
        if(pos<=m)update(pos,v,lson);
        else update(pos,v,rson);
        num[rt]=num[rt<<1]+num[rt<<1|1];
    }
    ll query(int L,int R,int l,int r,int rt){
        if(L<=l && R>=r){
            return num[rt];
        }
        int m=l+r>>1;
        ll res=0;
        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=1;i<=n;i++){
            int x;scanf("%d",&x);
            cnt[x]++;
        }
        
        ll ans=0;
        for(ll i=200000;i>=1;i--)if(cnt[i]){
            ll tmp=0;
            update(i,cnt[i],1,200000,1);
            for(ll j=1;j*i<=200000;j++)
                tmp+=query(j*i,min(200000ll,(j+1)*i-1),1,200000,1)*i*j;
            ans=max(ans,tmp);
        }
        cout<<ans<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11440213.html

发表评论取消回复

表情：

评论列表（有 0 条评论，35人围观）

还没有评论，来说两句吧...

相关阅读

相关欧拉筛&&埃氏筛

数论——欧拉筛、埃氏筛 `记录一点关于数论的知识，该知识点本身不难，主要是学习一下思想~` -------------------- 文章目录数论——欧

向右看齐/ 2024年03月30日 12:54/ 0 赞/ 101 阅读

相关【GCD可交性】CF731div3 F

好难不会感觉见过以后应该就会了吧 [Problem - F - Codeforces][] 题意：给定一个序列，每次操作可以让一个数与后面那个数取gcd，问你最少操

落日映苍穹つ/ 2024年03月27日 13:54/ 0 赞/ 82 阅读

相关【普通线段树+小小剪枝优化】CF849div4 F

[Problem - F - Codeforces][] 太久太久没写线段树了，昨天的F直接搬板子，调了半天也没调出来，今天写了一下也是t了很多发才过，感觉线段树还是手写一

喜欢ヅ旅行/ 2024年03月27日 13:17/ 0 赞/ 101 阅读

相关埃氏筛+线段树——cf731F

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

矫情吗；*/ 2023年10月12日 08:21/ 0 赞/ 36 阅读

相关埃氏筛法(埃氏算法)

埃氏筛法 > 埃拉托色尼筛选法，简称埃氏筛法，是针对自然数列中的自然数而实施的，用于求一定范围内的质数。也就是给定整数n，求小于n的所有质数（素数）。 > 埃拉托斯

阳光穿透心脏的1/2处/ 2023年09月28日 16:07/ 0 赞/ 25 阅读

相关寻找素数，普通实现，埃氏筛法

一：素数的概念素数就是除了1和它本身再也没有其他因数的数，例如数字7只能被1和7整除，所以数字7是素数。与素数相对的是合数，合数是出去1和它本身还有别的因数的数。

ゝ一世哀愁。/ 2023年02月17日 11:22/ 0 赞/ 17 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 161 阅读

相关算法埃氏筛法求素数个数

思路原理要得到自然数n以内的全部素数，必须把不大于根n的所有素数的倍数剔除，剩下的就是素数。给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除

雨点打透心脏的1/2处/ 2022年06月13日 12:36/ 0 赞/ 269 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 284 阅读

相关筛选素数的方法（埃氏和欧拉筛）

include<bits/stdc++.h> using namespace std; int v[10000],record[10000];

た入场券/ 2022年03月20日 06:48/ 0 赞/ 216 阅读