首先说说什么是分块。所谓分块就是将规模为n的问题划分为就是将规模为n问题划分为k块，每块规模为s。那么对块内的操作和整个范围内的操作的复杂度要平均，即令k=s=sqrt(n)通过这个思想可以把O(n)的复杂度降到O(sqrt(n))，达到优化算法的目的。
看道例题：中文题，题目就是求
而可以通过变换得到：
转换到这步的时候。注意到对于某些连续的i，[k/i]的值是相同的。我们可以在O(1)的时间求出[k/i]相同的时候i*[k/i]的和。注意一下当i>k的时候k mod i的值是k。所以总的复杂度是O(sqrt(k))。代码君：
View Code #include#include #include #include using namespace std;int main() { long long n, k, ans = 0; scanf("%lld %lld", &n, &k); if (n > k) { ans += (long long)(n - k) * k; n = k; } ans += n * k; for (long long i = 1, last; i <= n; i = last + 1) { last = min((long long)n, k/(k/i)); ans -= (k/i) * (i+last) * (last-i+1) / 2; } printf("%lld\n", ans); return 0;}
分块思想很少单独出到题目里。但有些题目需要用这种思想才能顺利Accepted，或者利用这个思想来优化你的程序。比如，不用分块来做耗时是5.76s，用了分块之后，耗时可以缩小到1s以内。(PS：这道题的主要考点并不是分块，而是莫比乌斯反演)。