数论 整除分块
0.1 前言
一个常常与莫比乌斯反演一起使用的技巧,单独使用也有一定用武之地。
1.1 问题
整除分块用以解决以下问题:
\]
1.2 暴力法
失去算法,失去很多;失去暴力,失去一切
暴力是显然的,照着公式打一遍就好。
for(int i=1;i<=n;++i) ans+=(n/i);
1.3 整除分块
这暴力的过程中发现:虽然\(i\)的确是从\(1\)枚举到了\(n\),但是\(\lfloor \frac{n}{i} \rfloor\)的值其实极其有限,具体而言,只有\(2\sqrt n\)种。证明如下:
对于\(\frac{n}{i}\),的\(n\)和\(i\)
若\(i\leq \sqrt n\),显然\(\lfloor \frac{n}{i} \rfloor\)的个数不会超过\(\sqrt n\)种
若\(i> \sqrt n\),则\(\lfloor \frac{n}{i} \rfloor\)的取值不会超过\(\sqrt n\),因为\(\lfloor \frac{n}{i} \rfloor\)至大是\(\sqrt n\)
综上,结论成立φ(゜▽゜*)♪
显然,思路更进一步:假如我们每一次都能确定一个极大的范围,范围内的整除结果都是特定值,那么只需至多转移\(2\sqrt n\)次。复杂度\(O(\sqrt n)\)
问题转换为:如何确定一个范围,使的整除结果是一个特定的值?
结论:\(i\to\lfloor\frac{n}{\lfloor \frac{n}{i}\rfloor} \rfloor\),是满足整除结果一致的极大范围。
证明:
设\(i\)是左边界,则\(i'\)是右边界,值是\(d=\frac{n}{i}\)
\(\frac{n}{i'}=d \Rightarrow i'=\lfloor \frac{n}{d} \rfloor\)
展开得\(\lfloor\frac{n}{\lfloor \frac{n}{i}\rfloor} \rfloor\)
因此,结论得证(๑•̀ㅂ•́)و✧
那么借用上述结论优化一下求值:
ll l=1,r;
for(l;l<=n;l=r+1){
r=min(k/(k/l),min(n,k-1));
ans+=(k/l)*(r-l+1)/2;
}
终了╰( ̄ω ̄o)
原文链接: https://www.cnblogs.com/ticmis/p/13210789.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/360328
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!