邯郸哪家公司做企业网站比较专业,网页设计工资怎么算,php众筹网站程序源码,建站平台 phpwind文章目录 整除分块的思考与运用整除分块的时间复杂度证明 分块数量整除分块的公式 公式证明公式证明 代码code↓ 整除分块的思考与运用
整除分块是为了解决一个整数求和问题 题目的问题为#xff1a; ∑ i 1 n ⌊ n i ⌋ \sum_{i1}^{n} \left \lfloor \frac{n}{… 文章目录 整除分块的思考与运用整除分块的时间复杂度证明 分块数量整除分块的公式 公式证明公式证明 代码code↓ 整除分块的思考与运用
整除分块是为了解决一个整数求和问题 题目的问题为 ∑ i 1 n ⌊ n i ⌋ \sum_{i1}^{n} \left \lfloor \frac{n}{i} \right \rfloor i1∑n⌊in⌋
求出上述式子的值为多少
上述问题等同于 c o d e code code↓
int sum0;
for(int i1;in;i) sumn/i;//int是整除类型所以可以直接整除
return sum;注意事项 ⌊ x ⌋ \left \lfloor x \right \rfloor ⌊x⌋代表不大于 x x x 的最大整数也可以成为向下取整 我们不难看出如果我们直接按题意暴力模拟则时间复杂度为 O ( n ) O(n) O(n)如果 n n n 比较大就会超时(TLE警告QWQ)
而如果我们将 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋ ( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n) 的值输出一下就会发现其中有许多值是重复的
输出 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋值的 c o d e code code↓
for(int i1;in;i) coutn/iendl;我们可以举例来看一下
我们令 n 8 n8 n8 则有 i i i 的值 i i i 1 1 1 i i i 2 2 2 i i i 3 3 3 i i i 4 4 4 i i i 5 5 5 i i i 6 6 6 i i i 7 7 7 i i i 8 8 8 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋ 的值 8 8 8 4 4 4 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1
此时我们可以明显的看出 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋ 的值被明显的分成了几个块每个块中的块值相同
分块 [ 1 , 1 ] [1,1] [1,1] [ 2 , 2 ] [2,2] [2,2] [ 3 , 4 ] [3,4] [3,4] [ 5 , 8 ] [5,8] [5,8]块值 8 8 8 4 4 4 2 2 2 1 1 1
整除分块的时间复杂度证明 分块数量
总共需要分少于 2 n 2 \sqrt{n} 2n 种块证明如下 i ≤ n i \leq n i≤n 时 n i \frac{n}{i} in 的值有 { n 1 , n 2 , n 3 . . . n n } \left \{ \frac{n}{1} ,\frac{n}{2},\frac{n}{3} ...\frac{n}{\sqrt{n} }\right \} {1n,2n,3n...n n} n i ≥ n \frac{n}{i} \ge \sqrt{n} in≥n 共 n \sqrt{n} n 个此时 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋ 有 n \sqrt{n} n 种取值 i ≥ n i \ge n i≥n 时有 n i ≤ n \frac{n}{i} \le \sqrt{n} in≤n 此时 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋ 也有 n \sqrt{n} n 种取值
两者相加共 2 n 2 \sqrt{n} 2n 种所以整除分块的数量为 O ( n ) O(\sqrt{n}) O(n ) 种所以整除分块的时间复杂度为 O ( n ) O(\sqrt{n}) O(n )
整除分块的公式 公式证明
结论 R n ⌊ n L ⌋ R\frac{n}{\left \lfloor \frac{n}{L} \right \rfloor} R⌊Ln⌋n 每个块中的元素个数为 ( R − L 1 ) (R-L1) (R−L1)
每个块中元素的 ⌊ n i ⌋ \left \lfloor \frac{n}{i} \right \rfloor ⌊in⌋ 值为 ⌊ n L ⌋ \left \lfloor \frac{n}{L} \right \rfloor ⌊Ln⌋
每个块中的和为 a n s ( R − L 1 ) × ⌊ n L ⌋ ans(R-L1) \times \left \lfloor \frac{n}{L} \right \rfloor ans(R−L1)×⌊Ln⌋
公式证明
整除分块出现在能被 n n n 完全整除的数之后到下一个能被 n n n 整除的数之间
令当前能被 n n n 整除的数为 x x x下一个能被 n n n 整除的数为 y y y
则有整除分块的区间为 [ ( x 1 ) ∼ y ] [(x1) \sim y] [(x1)∼y]
令 L x 1 Lx1 Lx1 R y Ry Ry v a l u e value value为分块区间的值则有 v a l u e ⌊ n x 1 ⌋ ⌊ n L ⌋ value \left \lfloor \frac{n}{x1} \right \rfloor\left \lfloor \frac{n}{L} \right \rfloor value⌊x1n⌋⌊Ln⌋ 因为 y y y 能被 n n n 完全整除(PS余数为 0 0 0)
所以 ⌊ n y ⌋ n y \left \lfloor \frac{n}{y} \right \rfloor \frac{n}{y} ⌊yn⌋yn且 n y v a l u e \frac{n}{y}value ynvalue则有 n y v a l u e \frac{n}{y}value ynvalue y n v a l u e y \frac{n}{value} yvaluen
将 v a l u e ⌊ n x 1 ⌋ value \left \lfloor \frac{n}{x1} \right \rfloor value⌊x1n⌋ 代入原式得 y n ⌊ n x 1 ⌋ y \frac{n}{\left \lfloor \frac{n}{x1} \right \rfloor} y⌊x1n⌋n
我们将 L x 1 Lx1 Lx1 R y Ry Ry 代入原式得 R n ⌊ n L ⌋ R \frac{n}{\left \lfloor \frac{n}{L} \right \rfloor} R⌊Ln⌋n 因为 ⌊ n L ⌋ ⌊ n R ⌋ \left \lfloor \frac{n}{L} \right \rfloor\left \lfloor \frac{n}{R} \right \rfloor ⌊Ln⌋⌊Rn⌋ 且因为 ⌊ n R ⌋ n R \left \lfloor \frac{n}{R} \right \rfloor \frac{n}{R} ⌊Rn⌋Rn 因为 ( n / R ) (n/R) (n/R) 能被 n n n 完全整除
所以可以保证 n n n 能完全整除 ⌊ n L ⌋ \left \lfloor \frac{n}{L} \right \rfloor ⌊Ln⌋
所以我们可以得证 ⌊ n ⌊ n L ⌋ ⌋ n ⌊ n L ⌋ {\left \lfloor \frac{n}{{\left \lfloor \frac{n}{L} \right \rfloor}} \right \rfloor} \frac{n}{\left \lfloor \frac{n}{L} \right \rfloor} ⌊⌊Ln⌋n⌋⌊Ln⌋n
证明完毕 细节详解
在 i n t l o n g l o n g intlong long intlonglong 等整数类型中可以直接进行整除所以上面的得证等同于 R ( n / ( n / L ) ) R(n/(n/L)) R(n/(n/L))
代码code↓
#include bits/stdc.h
using namespace std;
long long n,L,R,ans0;
int main(){cinn;for(L1;Ln;LR1){//LR1是代表进入下一个块Rn/(n/L);//公式ans(R-L1)*(n/L);//求和coutL~R:n/R n/Lendl;//打印分块情况}coutans;//打印和return 0;
}当 n 8 n8 n8 时的运行结果↓
