整除分块学习笔记

Luogu P2261 [CQOI2007]余数求和

题目：

给定\(n, k\)（\(n,k\leq 10^9\)），求\[\sum_{i=1}^n i\rm \;mod \;k\]

分析：

\[\sum_{i=1}^n i\rm \;mod \;k\]

由取模意义可得：

\[=\sum_{i=1}^n k-i\times \left\lfloor\frac{k}{i}\right\rfloor\]

\[=nk-\sum_{i=1}^n i\times \left\lfloor\frac{k}{i}\right\rfloor\]

分析样例：

发现\(\left\lfloor\frac{k}{i}\right\rfloor\)取值很少（在\(\sqrt{k}\)左右），对于一个区间\([l,r]\)，满足

\[\forall x,y\in[l,r]\quad\left\lfloor\frac{k}{x}\right\rfloor=\left\lfloor\frac{k}{y}\right\rfloor\]

那么，若已知区间左端点\(l\)，如何求出\(r\)?

设\(p=\left\lfloor\frac{k}{l}\right\rfloor\)，即所有\(x\in[l,r]\)的\(\left\lfloor\frac{k}{x}\right\rfloor\)的值

要求区间的右端点，即使\(x\)最大并且满足：

\[\left\lfloor\frac{k}{x}\right\rfloor=p\]

由向下取整定义可得

\[\frac{k}{x}\geq p\]

\[\because x>0\]

\[\therefore k\geq px\]

\[x\leq \frac{k}{p}\]

由\(x\)取最大正整数（区间右端点）可得：

\[x=\left\lfloor\frac{k}{p}\right\rfloor\]

所以区间右端点：\[r=\left\lfloor\frac{k}{\left\lfloor\frac{k}{l}\right\rfloor}\right\rfloor\]

回到开始的式子，我们已经求出了区间，对于区间内的答案，为（此处省略\(nk\)，因为可以一开始就算好）：

\[\sum_{i=l}^r i\times \left\lfloor\frac{k}{i}\right\rfloor\]

因为区间内的\(\left\lfloor\frac{k}{i}\right\rfloor\)相同，所以可以直接取\(\left\lfloor\frac{k}{l}\right\rfloor\)

\[\sum_{i=l}^r i\times \left\lfloor\frac{k}{l}\right\rfloor\]

\[=\frac{(l+r)(r-l+1)}{2}\times\left\lfloor\frac{k}{l}\right\rfloor\]

最后的答案即为\(nk\)减去所有区间答案的和

（注意：若\(\left\lfloor\frac{k}{l}\right\rfloor=0\)，则区间为\([l,\infty]\)，实现时设置成\(n\)即可，运算中出现\(r>n\)也需要设置\(r=n\)）

若还有不理解，参考代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll ans = 0, l = 1, r = 0, n, k;

int main()
{
    cin >> n >> k;
    while(r < n)
    {
        r = (k / l ? min(k / (k / l), n) : n);
        ans += (l + r) * (r - l + 1) / 2 * (k / l);
        l = r + 1;
    }
    cout << n * k - ans << endl;
    return 0;
}

后记：

发现没有多少个题解（也有可能是我没看到）完整的解释了右边界\(r\)的来历，于是花了一个下午（没办法我太弱了\(qwq\)）来写出完整过程，过程会有点啰嗦，\(\rm dalao\)不要介意。

\[\frak {The\;End}\]

【旧博客搬运】整除分块学习笔记

原文：https://www.cnblogs.com/zhylj/p/10090625.html