提示：本篇文章只讲数论分块(也叫整除分块)的基本形式，感兴趣可以自行查阅资料。
几个定义
- 分块：
顾名思义，就是把一个区间分成几小块，然后对于每个块进行单独的处理。它的核心思想是将一个大规模的输入划分成更小的“块”，然后针对每一块单独处理。（只需要了解就行） - {\left\lfloor\dfrac{}{}\right\rfloor} 符号，作用是向下取整，如 \(\dfrac{13}{5}=2.6\)，则 \(\left\lfloor\dfrac{13}{5}\right\rfloor=2\)。
推销一波我的洛谷号
考虑这道题：
给出 \(n\), \(k\), 求： \(\displaystyle f(n,k)=\sum_{i=1}^nk\%i\)
首先把%去掉
那么关键就是求出：\(\sum_{i=1}^ni\left\lfloor\dfrac{n}{i}\right\rfloor\),这就是数论分块的功能了。
注意到\(\left\lfloor\dfrac{n}{i}\right\rfloor\)其实是有很多是相同的,比如当n=9时
| \(i\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) |
|---|---|---|---|---|---|---|---|---|---|
| \(\left\lfloor\dfrac{n}{i}\right\rfloor\) | \(9\) | \(4\) | \(3\) | \(2\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
那么我们完全可以将\(\left\lfloor\dfrac{n}{i}\right\rfloor\)的数一起计算，这种思想利用了分块思想，也是数论分块名字的由来。
那么如何计算每个块？也就是问对于固定数 \(l\),且 \(\left\lfloor\dfrac{n}{l}\right\rfloor=\left\lfloor\dfrac{n}{r}\right\rfloor\)，求 \(max(r)\)。
先给结论：\(max(r)=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor\)
证明：
令 \(k=\left\lfloor\dfrac{n}{l}\right\rfloor\)。
则由向下取整的定义：\(k\le\dfrac{n}{l}\lt k+1\)。
取倒数得: \(\dfrac{n}{k}\geq l>\dfrac{n}{k+1}\)
所以 \(l\) 的最大值为 \(\dfrac{n}{k}\),即\(\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor\)。
所以可以从上一块末尾编号+1作为当前块的起点，再用以上结论求出末尾，用等差数列公式一次计算整个块之和。
洛谷P2261
#include<bits/stdc++.h>
using namespace std;
long long n,k,ans;
void solve()
{ans=n*k;int l=1,r;for(;l<=n;l=r+1){if(k/l) r=min(k/(k/l),n);else r=n;ans-=(k/l)*(r-l+1)*(l+r)>>1;}
}
int main()
{while(cin>>n>>k)solve(),cout<<ans<<'\n';return 0;
}
时间复杂度分析：\(\mathcal{O(\sqrt{n})}\)
未完待续...