数论与线性代数——整除分块【数论分块】的【运用】&【思考】&【讲解】&【证明(作者自己证的QWQ)】-Toy模板网

这篇具有很好参考价值的文章主要介绍了数论与线性代数——整除分块【数论分块】的【运用】&【思考】&【讲解】&【证明(作者自己证的QWQ)】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

整除分块的思考与运用

整除分块是为了解决一个整数求和问题

题目的问题为： $\sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor$

求出上述式子的值为多少？

上述问题等同于 $co d e$ ↓

int sum=0;
for(int i=1;i<=n;i++) sum+=n/i;//int是整除类型，所以可以直接整除
return sum;

注意事项： $\left \lfloor x \right \rfloor$ 代表不大于 $x$ 的最大整数，也可以成为向下取整

我们不难看出，如果我们直接按题意暴力模拟，则时间复杂度为 $O (n)$ ，如果 $n$ 比较大就会超时(TLE警告QWQ)

而如果我们将 $\left \lfloor \frac{n}{i} \right \rfloor$ ( $\le i \le n$ ) 的值输出一下，就会发现其中有许多值是重复的

输出 $\left \lfloor \frac{n}{i} \right \rfloor$ 值的 $co d e$ ↓

for(int i=1;i<=n;i++) cout<<n/i<<endl;

我们可以举例来看一下：

我们令 $n = 8$ ，则有

$i$ 的值	$i$ = $1$	$i$ = $2$	$i$ = $3$	$i$ = $4$	$i$ = $5$	$i$ = $6$	$i$ = $7$	$i$ = $8$
$\left \lfloor \frac{n}{i} \right \rfloor$ 的值	$8$	$4$	$2$	$2$	$1$	$1$	$1$	$1$

此时我们可以明显的看出 $\left \lfloor \frac{n}{i} \right \rfloor$ 的值被明显的分成了几个块，每个块中的块值相同

分块	$[1, 1]$	$[2, 2]$	$[3, 4]$	$[5, 8]$
块值	$8$	$4$	$2$	$1$

整除分块的时间复杂度证明 & 分块数量

总共需要分少于 $\sqrt{n}$ 种块，证明如下：

$\leq n$ 时， $\frac{n}{i}$ 的值有 $\left \{ \frac{n}{1} ,\frac{n}{2},\frac{n}{3} ...\frac{n}{\sqrt{n} }\right \}$ ， $\frac{n}{i} \ge \sqrt{n}$ ，共 $\sqrt{n}$ 个，此时 $\left \lfloor \frac{n}{i} \right \rfloor$ 有 $\sqrt{n}$ 种取值

$\ge n$ 时，有 $\frac{n}{i} \le \sqrt{n}$ ，此时 $\left \lfloor \frac{n}{i} \right \rfloor$ 也有 $\sqrt{n}$ 种取值

两者相加，共 $\sqrt{n}$ 种，所以整除分块的数量为 $O(\sqrt{n})$ 种，所以整除分块的时间复杂度为 $O(\sqrt{n})$

整除分块的公式 & 公式证明

结论： $R=\frac{n}{\left \lfloor \frac{n}{L} \right \rfloor}$
每个块中的元素个数为： $(R - L + 1)$

每个块中元素的 $\left \lfloor \frac{n}{i} \right \rfloor$ 值为 $\left \lfloor \frac{n}{L} \right \rfloor$

每个块中的和为 $\times \left \lfloor \frac{n}{L} \right \rfloor$

公式证明

整除分块出现在能被 $n$ 完全整除的数之后，到下一个能被 $n$ 整除的数之间

令：当前能被 $n$ 整除的数为 $x$ ，下一个能被 $n$ 整除的数为 $y$

则有，整除分块的区间为 $\sim y]$

令： $L = x + 1$ ， $R = y$ ， $v a l u e$ 为分块区间的值，则有，
$=\left \lfloor \frac{n}{x+1} \right \rfloor=\left \lfloor \frac{n}{L} \right \rfloor$
因为， $y$ 能被 $n$ 完全整除(PS：余数为 $0$ )

所以， $\left \lfloor \frac{n}{y} \right \rfloor= \frac{n}{y}$ ，且， $\frac{n}{y}=value$ ，则有，
$\frac{n}{y}=value$ $\frac{n}{value}$

将 $=\left \lfloor \frac{n}{x+1} \right \rfloor$ 代入原式得：
$\frac{n}{\left \lfloor \frac{n}{x+1} \right \rfloor}$

我们将 $L = x + 1$ ， $R = y$ 代入原式得：
$\frac{n}{\left \lfloor \frac{n}{L} \right \rfloor}$
因为
$\left \lfloor \frac{n}{L} \right \rfloor=\left \lfloor \frac{n}{R} \right \rfloor$
且因为 $\left \lfloor \frac{n}{R} \right \rfloor= \frac{n}{R}$
因为 $(n / R)$ 能被 $n$ 完全整除

所以可以保证 $n$ 能完全整除 $\left \lfloor \frac{n}{L} \right \rfloor$

所以我们可以得证：
${\left \lfloor \frac{n}{{\left \lfloor \frac{n}{L} \right \rfloor}} \right \rfloor}= \frac{n}{\left \lfloor \frac{n}{L} \right \rfloor}$

证明完毕

细节详解：

在 $in t ， l o n g l o n g$ 等整数类型中，可以直接进行整除，所以上面的得证等同于 $R = (n / (n / L))$

代码code↓

#include <bits/stdc++.h>
using namespace std;
long long n,L,R,ans=0;
int main(){
	cin>>n;
	for(L=1;L<=n;L=R+1){//L=R+1是代表进入下一个块
		R=n/(n/L);//公式
		ans+=(R-L+1)*(n/L);//求和
		cout<<L<<"~"<<R<<":"<<n/R<<" "<<n/L<<endl;//打印分块情况
	}
	cout<<ans;//打印和
	return 0;
}