数论分块
首先我们需要知道数论分块的用途:它可以快速计算含有除法向下取整的和式。形如\(\sum_{i=1}^{n}f(i)g(\lfloor{\frac{n}{i}}\rfloor)\).为什么可以快速计算呢,因为那个g的部分我们可以采用分块的思想快速求解。也就是就\(O(\sqrt{n})\)的时间复杂度里面求解。
下面讲解为什么是这样的:
因为\(\lfloor{\frac{n}{i}}\rfloor\)的值是一个块状分布,就是所有的值聚集在一个连续的快里面。例如:n=21时,我们按照\(\lfloor{\frac{21}{i}}\rfloor\)的值不同,可以把i的值域分为8块:{1},{2},{3},{4},{5},{6,7},{8,9,10}.{11,12,13,\(\cdots,21\)}.
这里我们可以根据图像进行理解:
证明1:分块的快数需要\(\leq2 \lfloor{\sqrt{n}}\rfloor\)
当我们的\(i\leq\lfloor{\sqrt{n}}\rfloor\),\(\lfloor{\frac{n}{i}}\rfloor\)有\(\lfloor{\sqrt{n}}\rfloor\)种取值。这里我们可以这么记忆,也就是i从\(1\sim \sqrt{n}\)有多少种不同的取值。然后下取整一下就好了。
当\(i\ge\sqrt{n}\)时,\(\lfloor{\frac{n}{i}}\rfloor \leq \lfloor{\sqrt{n}},所以\lfloor{\frac{n}{i}}\rfloor最多有根号n种取值。\)
证明2:i所在块的右端点是\(\lfloor{\frac{n}{\lfloor{\frac{n}{i}}\rfloor}}\rfloor\)
一定要注意这个k是指i所在块的值,也就是函数的纵坐标.
例题讲解
[题目链接]([CQOI2007]余数求和 - 洛谷)
核心思路:首先我们应该对于k mod i 进行化简。\(k\pmod{i}=k-(k/i)*i\).然后我们会惊奇的发现后面那一部分就是我们刚开始的求和公式。然后我们就可以采用在\(\sqrt{n}\)的时间复杂度求出来\(t=\lfloor{\frac{k}{i}}\rfloor\).
具体的思路是我们可以利用t在这个\([L,R]\)这个区间里面的分块值不变,注意我们的L和R是已经在一个块里面的。然后我们在不断地迭代更新L和R,因为我们的R是可以通过数论分块的公式求出来的,所以我们可以L=R+1来迭代更新.
\(对于\sum_{i=1}^{r}i\)这个求和就是很容易的了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, M = 11, MOD = 1e8;
int main()
{
LL n, k;
cin >> n >> k;
LL res = n * k;
LL l = 1,r;
while (l <= n)
{
if (k / l)
r = min(k / (k / l), n);
else//因为一旦k/l等于0就说明这个l已经很大了.所以k/(k/l)就是一个无穷的数了,但是我们右端点最大都是不可以超过n的
r = n;
res -= (k / l) * (r - l + 1) * (l + r) / 2;
l = r + 1;//迭代更新
}
cout << res << endl;
}
标签:lfloor,frac,分块,数论,sqrt,rfloor,我们
From: https://www.cnblogs.com/xyh-hnust666/p/16949595.html