整除分块 学习笔记
2022/4/25 23:15:57
本文主要是介绍整除分块 学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
板子题
板子题-UVA11526
题目大意:
给定一个 \(n\),求 \(\sum\limits_{i-1}^{n}\lfloor \frac{n}{i} \rfloor\)。其中 \(n\) 为 \(32\) 位无符号整数。
题目解析
显然如果暴力求解肯定是不可行的,显然会 TLE,所以我们需要找一种复杂度更优的算法。
我们可以先令 \(n=10\),观察一下函数 \(\operatorname{f}(x)=\lfloor\frac{n}{x}\rfloor\) 的图像:
观察可以发现,不难发现:
当 \(x=1\) 的时候,\(\operatorname{f}(x)=10\)。
当 \(x=2\) 的时候,\(\operatorname{f}(x)=5\)。
当 \(x=3\) 的时候,\(\operatorname{f}(x)=3\)。
当 \(x=4,5\) 的时候,\(\operatorname{f}(x)=2\)。
当 \(x=6,7,8,9,10\) 的时候,\(\operatorname{f}(x)=1\)。
我们是否能够预处理出每个使 \(\operatorname{f}(x)\) 相同的区间来更快地计算答案呢?
不难发现以下结论:
\[\forall n\in\mathbb{N}_+, \left| \{ \lfloor\frac{n}{i}\rfloor \mid i\in\mathbb{N}_+,i\le n \} \right| \le 2 \lfloor\sqrt{n}\rfloor \]证明:
当 \(i\le \lfloor\sqrt{n}\rfloor\) 时,\(\lfloor\frac{n}{i}\rfloor\) 最多 \(\lfloor\sqrt{n}\rfloor\) 个数字。
当 \(\lfloor\sqrt{n}\rfloor<i\le n\) 时,\(1\le\lfloor\frac{n}{i}\rfloor\le\lfloor\sqrt{n}\rfloor\),最多有 \(\lfloor\sqrt{n}\rfloor\) 个数字。
因此最多只有 \(2\sqrt{n}\) 个数字。
整除分块结论
对于一个数字 \(n\),如果 \(\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor\) 成立,那么满足 \(i<j\le n\) 最大的 \(j\) 为 \(\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\)
根据前面的结论,这种做法的复杂度为 \(\Theta\left(\sqrt{n}\right)\)。
代码:
#include<cstdio> #define ll long long using namespace std; ll n,ans; void work(){ scanf("%lld",&n); ans=0; ll l=1,r; while(l<=n){ r=n/(n/l); ans+=(r-l+1)*(n/l); l=r+1; } printf("%lld",ans),putchar('\n'); return; } int main(){ int T; scanf("%d",&T); while(T--) work(); return 0; }
引申
显然在一般的求值题目中的式子不会这么简单,一般都形如
\[\sum_{i=1}^{n}\operatorname{f}(i)\lfloor\frac{n}{i}\rfloor \]此时预处理出 \(\operatorname{f}(x)\) 的前缀和 \(\operatorname{g}(x)\) 就可以在 \(\Theta\left(\sqrt{n}\right)\) 求出这个式子的值了。
代码大致如下:
l=1,sum=0; while(l<=n){ r=n/(n/l); ans+=(g(r)-g(l-1))*(n/l); l=r+1; }
多维数论分块
如果求值的函数中含有 \(\lfloor\frac{a_1}{i}\rfloor+\lfloor\frac{a_2}{i}\rfloor+\dots+\lfloor\frac{a_n}{i}\rfloor\),
那么我们只需要将前面的结论的 \(\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\) 改为 \(\min \limits^{n}_{j=1} \lfloor\frac{a_j}{\lfloor\frac{a_j}{i}\rfloor}\rfloor\) 即可。
(当然 \(n=2,n=3\) 的情况比较常见)
这篇关于整除分块 学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?