数论-整除分块
- 2020 年 3 月 8 日
- 筆記
数论-整除分块
这个蒟蒻太蒻了，希望这篇文章能成为自己恶补数论的开始。
参考资料
https://blog.csdn.net/beautiful_CXW/article/details/83143756
跳转按钮
(texttt{讲解证明})
整除分块就是用来求像
[sumlimits_{i=1}^nlfloor frac{n}{i}rfloor]
这样的式子的。
很明显，直接求要 (Theta(n))，但是整除分块只需要 (Theta(sqrt n))。
整除分块的第一步是发现不同的 (lfloor frac{n}{i}rfloor) 的数量。
如果 (ilesqrt n)：
很明显，因为 (i) 最多 (sqrt n) 种，所以 (lfloor frac{n}{i}rfloor) 最多 (sqrt n) 种。
如果 (i>sqrt n)：
因为 (frac{n}{i}<sqrt n)，所以 (lfloor frac{n}{i}rfloor) 也不到 (sqrt n) 种。
总结：不同的 (lfloor frac{n}{i}rfloor) 不到 (2sqrt n) 种。
第二步是计算答案。因为 (f(i)=lfloor frac{n}{i}rfloor) 的单调性，所以 (lfloor frac{n}{i}rfloor) 相同的 (i) 是相邻的。
显而易见的结论：对于 (lfloor frac{n}{i}rfloor=d)，(iin(lfloorfrac{n}{d+1}rfloor,lfloorfrac{n}{d}rfloor])。
比如 (n=100,d=6)。所以 (iin(14,16])
所以可以以 (l=lfloorfrac{n}{d+1}rfloor+1,r=lfloorfrac{n}{d}rfloor) 为循环变量，
[l=texttt{上一次的}r+1,r=lfloorfrac{n}{lfloorfrac{n}{l}rfloor}rfloor]
。
(texttt{代码实现})
讲解证明一定要仔细看，要不然代码是看不懂的。特短。必须要全局开 (texttt{long long})，这代码可是要过 (n=10^{12}) 的数据的！
code
#include <bits/stdc++.h> using namespace std; //&Start #define lng long long #define lit long double const int inf=0x3f3f3f3f; const lng Inf=1e17; //&Main lng n,ans; int main(){ scanf("%lld",&n); for(lng l=1,r;l<=n;l=r+1) r=n/(n/l),ans+=(r-l+1)*(n/l); printf("%lldn",ans); return 0; }(texttt{经典例题})
[CQOI2007]余数求和
求 (G(n,k)=sumlimits_{i=1}^nkbmod i)。
数据范围：(1le n,kle 10^9)。
推一下（这总得看得懂吧）：
[sumlimits_{i=1}^nkbmod i=nk-sumlimits_{i=1}^n itimeslfloorfrac{k}{i}rfloor]
[sumlimits_{i=1}^n itimeslfloorfrac{k}{i}rfloor=sumlimits_{l,r}^nlfloorfrac{k}{l}rfloortimesfrac{(l+r)(r-l+1)}{2}]
（首项加末项乘项数除以 (2)）。
注意了，有可能 (k<n)。所以
[ r= begin{cases} min(lfloorfrac{k}{lfloorfrac{k}{l}rfloor}rfloor,n)~~(lfloorfrac{k}{l}rfloor>0)\ n~~~~~~~~~~~~~~~~~~~~~~~(lfloorfrac{k}{l}rfloor=0) end{cases} ]
。
code
#include <bits/stdc++.h> using namespace std; //&Start #define lng long long #define lit long double const int inf=0x3f3f3f3f; const lng Inf=1e17; //&Main lng n,k,ans; int main(){ scanf("%lld%lld",&n,&k),ans=n*k; for(lng l=1,r;l<=n;l=r+1) r=(k/l)?min(k/(k/l),n):n,ans-=(l+r)*(r-l+1)/2*(k/l); printf("%lldn",ans); return 0; }我还是太蒻了 ，祝大家学习愉快！
