数论-整除分块
这个蒟蒻太蒻了，希望这篇文章能成为自己恶补数论的开始。
参考资料
https://blog.csdn.net/beautiful_CXW/article/details/83143756
跳转按钮
\(\texttt{讲解证明}\)
整除分块就是用来求像
\[\sum\limits_{i=1}^n\lfloor \frac{n}{i}\rfloor\]
这样的式子的。
很明显，直接求要 \(\Theta(n)\)，但是整除分块只需要 \(\Theta(\sqrt n)\)。
整除分块的第一步是发现不同的 \(\lfloor \frac{n}{i}\rfloor\) 的数量。
如果 \(i\le\sqrt 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\) 不到 \(2\sqrt n\) 种。
第二步是计算答案。因为 \(f(i)=\lfloor \frac{n}{i}\rfloor\) 的单调性，所以 \(\lfloor \frac{n}{i}\rfloor\) 相同的 \(i\) 是相邻的。
显而易见的结论：对于 \(\lfloor \frac{n}{i}\rfloor=d\)，\(i\in(\lfloor\frac{n}{d+1}\rfloor,\lfloor\frac{n}{d}\rfloor]\)。
比如 \(n=100,d=6\)。所以 \(i\in(14,16]\)
所以可以以 \(l=\lfloor\frac{n}{d+1}\rfloor+1,r=\lfloor\frac{n}{d}\rfloor\) 为循环变量，
\[l=\texttt{上一次的}r+1,r=\lfloor\frac{n}{\lfloor\frac{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("%lld\n",ans);
return 0;
}\(\texttt{经典例题}\)
[CQOI2007]余数求和
求 \(G(n,k)=\sum\limits_{i=1}^nk\bmod i\)。
数据范围：\(1\le n,k\le 10^9\)。
推一下（这总得看得懂吧）：
\[\sum\limits_{i=1}^nk\bmod i=nk-\sum\limits_{i=1}^n i\times\lfloor\frac{k}{i}\rfloor\]
\[\sum\limits_{i=1}^n i\times\lfloor\frac{k}{i}\rfloor=\sum\limits_{l,r}^n\lfloor\frac{k}{l}\rfloor\times\frac{(l+r)(r-l+1)}{2}\]
（首项加末项乘项数除以 \(2\)）。
注意了，有可能 \(k<n\)。所以
\[ r= \begin{cases} \min(\lfloor\frac{k}{\lfloor\frac{k}{l}\rfloor}\rfloor,n)~~(\lfloor\frac{k}{l}\rfloor>0)\\ n~~~~~~~~~~~~~~~~~~~~~~~(\lfloor\frac{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("%lld\n",ans);
return 0;
}我还是太蒻了 ，祝大家学习愉快！