【根号分治】ABC230 E - Fraction Floor Sum

矫情吗；* 2024-03-22 15:06 84阅读 0赞

[E - Fraction Floor Sum (atcoder.jp)][E - Fraction Floor Sum _atcoder.jp]

题意：

![86e990a1defd4310b8a6bf04408bf72d.png][]

思路：

考虑根号分治

即，对于1~sqrt(N)的暴力计算

对于sqrt(N)~N的单独算贡献

![292001f4b9f74bdf9321e31de346de8a.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    int N;
    
    void solve(){
    	cin>>N;
    	int ans=0;
    	for(int i=1;i<=(int)sqrt(N);i++) ans+=N/i;
    	for(int i=1;i<=N/((int)sqrt(N)+1);i++) ans+=(N/i-N/(i+1))*i;
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[E - Fraction Floor Sum _atcoder.jp]: https://atcoder.jp/contests/abc230/tasks/abc230_e
[86e990a1defd4310b8a6bf04408bf72d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/a4b05ede641e44ebbb8bb8822b83f003.png
[292001f4b9f74bdf9321e31de346de8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/57a2f2237179476fa885659badb4caff.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Atcoder ABC 139E

Atcoder ABC 139E 题意: > n支球队大循环赛，每支队伍一天只能打一场，求最少几天能打完。解法： > 考虑抽象图论模型，既然一天只...

爱被打了一巴掌/ 2024年04月20日 10:31/ 0 赞/ 91 阅读

相关【根号分治】CF1790 F

[Problem - F - Codeforces][] 题意： ![d39e51cdfd9b4fc1a390989f342b113c.png][] 思路： ![880

浅浅的花香味﹌/ 2024年03月22日 20:21/ 0 赞/ 71 阅读

相关【计数DP】ABC230 F - Predilection

计数DP，会不了一点.... [F - Predilection (atcoder.jp)][F - Predilection _atcoder.jp] ![c66088b

逃离我推掉我的手/ 2024年03月22日 15:08/ 0 赞/ 75 阅读

相关【根号分治】ABC230 E - Fraction Floor Sum

[E - Fraction Floor Sum (atcoder.jp)][E - Fraction Floor Sum _atcoder.jp] 题意： ![86e990

矫情吗；*/ 2024年03月22日 15:06/ 0 赞/ 85 阅读

相关【GCD+MST】ABC210 E

这道题告诉我们，一道题一定要去手摸样例，多造几个数据，然后找思路很多时候，题目看错了，码完发现思路错了，调半天调不出来，思路一直在旧框架打转，这些情况都是不去考察实际情况导

雨点打透心脏的1/2处/ 2024年03月17日 19:16/ 0 赞/ 81 阅读

相关【DP+博弈】ABC195 E

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp] 题意： ![44faf1c04ab542

ゞ浴缸里的玫瑰/ 2024年03月17日 15:40/ 0 赞/ 51 阅读

相关【根号分治+DP】CF797E

[Problem - 797E - Codeforces][] 题意： ![23760ea9c7e445d99782af22385a6467.png][] 思路：如果

女爷i/ 2024年03月16日 10:53/ 0 赞/ 52 阅读

相关【数学】ABC 319 E

[E - Bus Stops][] 题意： ![f19239bed77b4ffda13a74736273c59e.png][] ![7d16c61674c24f709d8

朱雀/ 2024年03月04日 08:04/ 0 赞/ 111 阅读

相关 AtCoder ABC 140E Second Sum

题目链接：[https://atcoder.jp/contests/abc140/tasks/abc140\_e][https_atcoder.jp_contests_abc1

布满荆棘的人生/ 2023年06月04日 14:57/ 0 赞/ 21 阅读

相关 AtCoder ABC 128E Roadwork

题目链接：[https://atcoder.jp/contests/abc128/tasks/abc128\_e][https_atcoder.jp_contests_abc1

末蓝、/ 2021年11月01日 06:18/ 0 赞/ 282 阅读