整除分块你在房间 像幻灯片你在我眼里蔓延你在手机 你在笔电 无法隔绝你在深夜 像黑咖啡你在我心里面 陪我失眠可是却不在 我身边前言文章主要记录关键推导与相关题目后续有变种会在此进行更新~~(所以别说水了)~~。UVA11526 H(n) - 洛谷我们通过一个例题引入整除分块的操作顺便给大家分享一下我看到的一个特别牛逼的题解仅凭一张图居然可以收获佬们的一致好评。题意long long H(int n) { long long res 0; for (int i 1;i n;i i 1) { res (res n / i); } return res; }∑ i 1 n ⌊ n i ⌋ \sum_{i1}^n\lfloor\frac{n}{i}\rfloori1∑n⌊in⌋也就是这个公式当然n肯定超过int范围。整除分块引入从一个具体例子引入设x 10 x10x10我们列出i 1 i1i1到1010 10101010时⌊ 10 i ⌋ \lfloor\frac{10}{i}\rfloor⌊i10⌋的值i12345678910⌊ 10 i ⌋ \lfloor\frac{10}{i}\rfloor⌊i10⌋10532211111观察关键现象值相同的i是连续的比如 4,5 都是26-10 都是1这种连续性不是巧合而是必然的数学性质显然我们如果能够将连续数的大小和连续的个数联系起来我们的时间复杂度就能降很多重要的是如何做分块处理题解来源UVA11526 H(n) - 洛谷虽然我数学不好当这个图很显然就是∫ 1 10 10 x d x ∑ i 1 n ⌊ n i ⌋ 2 ∑ i 1 ⌊ n ⌋ ⌊ n i ⌋ − ⌊ n ⌋ 2 \int_1^{10}\frac{10}{x}dx\\ \sum_{i1}^n\lfloor\frac{n}{i}\rfloor2\sum_{i1}^{\lfloor\sqrt{n}\rfloor}\lfloor\frac{n}{i}\rfloor-\lfloor\sqrt{n}\rfloor^2∫110x10dxi1∑n⌊in⌋2i1∑⌊n⌋⌊in⌋−⌊n⌋2依据函数图做出这题的思想所以我觉得这个解法真的很牛但是这个解法有局限性所以不是通解。代码int f(int n){ int msqrt(n),ans0; for(int i1;im;i)ansn/i; return ans*2-m*m; }接下来我们看需要通解的题目并理解推导原理B-不同的商_河南萌新联赛2026第二场河南农业大学题意理解给定正整数xy求∑ i 1 y ⌊ x i ⌋ \sum_{i1}^y\lfloor\frac{x}{i}\rfloori1∑y⌊ix⌋(1 x 10 12 ; 1 y 10 18 1x10^{12};1y10^{18}1x1012;1y1018)思路我们通过分出每一个x i \frac{x}{i}ix相同的块知道了他们的左右边界就可以知道块的大小不用一个个遍历改为一块一块遍历的方法降低时间复杂度到根号级别。推导假设我们当前处理到位置l并且知道这一块的商是v x / l。我们想知道这一块最远能到哪里也就是寻找最大的r使得x / r v因为商等于v或更大。因为x / r要大于等于v所以r必须小于等于x / v。我们用反证法理解如果r比⌊x/v⌋大那么⌊x/r⌋就会小于v它就不属于当前块了。所以⌊x/v⌋就是当前值的最大范围。代码#include bits/stdc.h using namespace std; using int64 long long; int main() { int64 x, y; cin x y; int64 ans 0; for (int64 l 1, r; l y; l r 1) { int64 v x / l; // 当前块内每个数的商 if (v 0) break; // 后续商全为0直接结束 r min(y, x / v); // 当前块的右端点 ans v * (r - l 1); } cout ans endl; return 0; }重要的还是分块的这种思想可以多参考
)
