计算形如

\sum^{n}_{1}\lfloor \frac{n}i\rfloor

的式子,直接求复杂度为 O(n) ,需要使用「整除分块」来优化复杂度。


所谓「分块」,是把 n 除以每一个 i 的商相同的分成了一块(即相同的\lfloor \frac{n}{i} \rfloor) 。

假设我们已经知道一个分块的左端点为 l ,想要求出该分块的右端点 r ,设该分块的数值为 k ,对于该分块的每一个数 i ,有

k=\lfloor \frac{n}{i} \rfloor=\lfloor \frac{n}{l} \rfloor

便有性质

k*i \leq n

而我们想要求出的 r 便是满足 k*i \leq n最大的 i ,即 r=max(i)k*i\leq n

便有

i\leq \frac{n}{k}

i\leq \frac{n}{\lfloor \frac{n}{l} \rfloor}

r=\frac{n}{\lfloor \frac{n}{l} \rfloor}

代码实现:

    ans = 0;
for(int l = 1, r; l <= n; l = r + 1){
    r = n / (n / l);
    ans += n / l * (r - l + 1);
}

复杂度为O(\sqrt{n}),证明如下:

\lfloor \frac {n}{i}\rfloor 最多只有 2\sqrt{n} 种取值

证明:对于 i \leq \sqrt{n} ,只有 \sqrt{n} 种取值,对于 i \geq \sqrt{n}, \lfloor \frac {n}{i}\rfloor \leq \sqrt{n} ,共计 2\sqrt{n} 种取值。


实际应用:计算 \sum^{n}_{1}\lfloor \frac{x}i\rfloor

区间右端点 r 不能超过 n

\lfloor \frac{x}l\rfloor >0 时,r=min(\frac{n}{\lfloor \frac{n}{l} \rfloor},n)

\lfloor \frac{x}l\rfloor=n 时,r=n


向上取整的情况

计算

\sum^{n}_{1}\lceil \frac{n}i\rceil

设:

A=\lceil \frac{n}{i} \rceil

对于 每一个分块值 A ,有

(A-1)*i<n\leq A*i

\frac{A}{n}\leq i<\frac{n}{A-1}

因为 i 为整数,所以

\lceil \frac{n}{A} \rceil \leq i \leq \lfloor \frac{n-1}{A-1} \rfloor

所以区间左端点为 \lceil \frac{n}{A} \rceil (可以不用管,主要是右端点)

右端点为 \lfloor \frac{n-1}{A-1} \rfloor

注意要特判 A=1 的情况

对于取整性质的补充:

小知识:

①:
下取整(又称floor(x)函数,向负无穷方向取整):设原数为x,取整后的y是小于等于x的整数。其定义为:

y=\lfloor x \rfloor = -\lceil -x\rceil
​ 若所取位数之右有非0的数字,当原数为正数时舍去,当原数为负数时进位。例如:23.7向下取整为23,−23.2向下取整为−24。取整后的数总是小于等于原数,因此“下取整”也称“向负无穷方向取整”。
​ 又称为高斯符号

  • 上取整(又称ceil(x)函数,向正无穷方向取整):设原数为x,取整后的y是大于等于x的整数。其定义为:

y=\lfloor x \rfloor = -\lceil -x \rceil

​ 若所取位数之右有非0的数字,当原数为正数时进位,当原数为负数时舍去。例如:23.2向上取整为24,−23.7向上取整为−23。取整后的数总是大于等于原数,因此“上取整”也称“向正无穷方向取整”。

  • 截尾取整(又称truncate(x)函数,向原点方向取整):设原数为x,取整后的y是0与x之间(含x)最接近x的整数。若原数值为正数,则下取整;若原数值为负数,则上取整(也相当于对原数绝对值下取整,然后再加上负号)。其定义为:
    y=sgn(x)\lfloor |x|\rfloor
    ​ 若所取位数之右有非0的数字,则一律无条件舍去。例如:23.7截尾后为23,−23.7截尾后为−23。正数取整后总是小于等于原数,负数取整后的数总是大于等于原数,因此“截尾取整”也称“向原点方向取整”。

  • 无条件进位(远离于原点,正、负数各自向正、负无穷方向取整):设原数为x,取整后的y是0与y(含y)之间最接近x的整数(也可定义为0与y(含y)之间最接近0的整数,两者等价)。若原数值为正数,则上取整;若原数值为负数,则下取整(也相当于对原数绝对值上取整,最后再加上负号)。其定义为:
    y=sgn(x)\lceil |x|\rceil
    ​ 若所取位数之右有非0的数字,则一律无条件进位。例如:23.2取整后为24,−23.2取整后为−24。正数取整后总是大于等于原数,负数取整后总是小于等于原数,因此“无条件进位”也称“远离原点方向取整”或“正、负数各自向正、负无穷方向取整”。

对于下取整函数,有如下性质:

\lfloor x \rfloor = -\lceil -x\rceil

\lfloor x \rfloor \leq x <\lfloor x \rfloor+1 ,等号成立当且仅当 x 为整数

下取整符号为等幂运算 \lfloor \lfloor x \rfloor \rfloor
对于任意的整数 k 和任意实数 x ,有 \lfloor k+x \rfloor=k+\lfloor x \rfloor
x 为一个实数,n 为整数,则由定义,n ≤ x 当且仅当 n ≤ \lfloor x\rfloor
如果 x 为整数 \lfloor x \rfloor +\lfloor -x \rfloor =0 ,否则 \lfloor x \rfloor +\lfloor -x \rfloor =-1

定义 y 为实数 x 四舍五入后的值,y=\lfloor x+0.5\rfloor

\lfloor \frac{a}{kz} \rfloor =\lfloor \frac{\lfloor \frac{a}{k} \rfloor }{z} \rfloor

对于上取整函数:有如下性质:

\lceil x \rceil = -\lfloor -x\rfloor

x\leq \lceil x \rceil <x+1 ,等号成立当且仅当 x 为整数

\lceil \frac{a}{kz} \rceil =\lceil \frac{\lceil \frac{a}{k} \rceil }{z} \rceil

分类: 数论

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注