下取整函数

---

令$F(x)=\lfloor \frac{N}{x}\rfloor$, N为正数, 其定义域D = [1, 2, ..., N]
… 我们这里初步认识, 暂且只讨论 定义域为正数的情况, 此时a / b除法, 是下取整 或 向0取整, 都可以! 两者相同

以N = 37为例:
F( 1) = 37
F( 2) = 18
F( 3) = 12
F( 4) = 9
F( 5) = 7
F( 6) = 6
F( 7) = 5
F( 8, 9) = 4
F( 10, 11, 12) = 3
F( 13, 14, 15, 16, 17, 18) = 2
F( 19, 20, 21, ..., 35, 36, 37) = 1

可以发现, 定义域中, 有很多x值, 他们对应的y值 是相同的, 而且这些x是一段连续的区间
如果画出图形, 他们是一个个矩阵. 比如F( 8, 9) = 4表示 长为2高为4的矩阵, 故称之为: 数论分块.

其有很多性质:

• 性质一
  值域虽然在[1, N]范围, 但只会占据 $2\ast \sqrt{N}$个值
  将定义域所有点, 分为: $A类=[1,\sqrt{N}]$ 和 $B类=[\sqrt{N},N]$
  对于A类: 由于其只有$\sqrt{N}$个点, 故其值域最多占据了 $\sqrt{N}$个值.
  对于B类: 虽然他有 接近N个点, 但是 其值域范围均落在: $[\frac{N}{\sqrt{N}},\frac{N}{N}]=[\sqrt{N},1]$
  也是最多 $\sqrt{N}$个值.
  … 即, 虽然定义域是 O(N)级别的, 但是其值域 只会有 O($\sqrt{N}$)个不同的值 (虽然值域范围也是O(N)级别的)

• 性质二
  $\lfloor \frac{a}{bc}\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}\rfloor$, 即取整可以拆分开来
  因为b*c可能非常大, 无法存储, 但a,b,c都是LL范围的, 这样只有拆分开才能计算
  证明:
  $\frac{a}{b}=\lfloor \frac{a}{b}\rfloor +r,r\in (0,1)$, 将其带入 到$\lfloor \frac{a}{bc}\rfloor$中. 注意, 除法和下取整除法, 两者不要混肴
  $\lfloor \frac{a}{bc}\rfloor =\lfloor \frac{\lfloor \frac{a}{b}\rfloor }{c}+\frac{r}{c}\rfloor$, 而$\frac{r}{c}=0$ (注意他不是取整)

• 性质三
  $\lfloor \frac{a}{b}\rfloor \ne \lfloor \frac{a}{\lfloor b\rfloor }\rfloor$
  比如: 3 / 1.5的下取整为 2; 但3 / 1.5的下取整的下取整为 1
  … 因此, 对于$\lfloor \frac{a}{b}\rfloor$, 不要以为a b都是整数, 他可能会是小数;
  … 而小数要先参加除法运算, 而不是下取整, 下取整只是对最终的结果进行取整, 而不能影响过程
  … 只是F(x)函数定义在整数域, F( x)只是 下取整 的一个子集, 特例.

• 性质四
  若a b均为整数, $c=\lfloor \frac{a}{b}\rfloor$, 则有: $\lfloor \frac{a}{c}\rfloor \ge b$
  $\lfloor \frac{a}{c}\rfloor =\lfloor \frac{a}{\lfloor \frac{a}{b}\rfloor }\rfloor \ge \lfloor \frac{a}{\frac{a}{b}}\rfloor =\lfloor b\rfloor =b$
  … 比如: 2 = 17 / 6, 则17 / 2 = 8 >= 6;
  … 比如: 2 = 17 / 8, 则17 / 2 = 8 >= 8;

• 性质五
  所有的矩形 (块), 以x轴从左往右看, 其 矩阵的长度, 是递增的.
  即, 越往后, x值越大, 其块的长度越长, 即其y值 越大概率会相同.
  这是因为 $x\in [1,\sqrt{N}]$时, 有$\sqrt{N}$个y值.
  但到了后面$x\in [\sqrt{N},N]$, 这么多点, 却也只是有$\sqrt{N}$个y值.
  … 比如, 令两个相邻的矩形为: [l1, r1] y1 和 [l2, r2] y2 (自然有: r1 + 1 = l2, y1 > y2)
  … 则有: r2 - l2 >= r1 - l1

• 性质六
  所有矩阵的x轴的右端点 的集合 等于 值域集合. (两者互逆)
  以上面举例的N = 37为例:
  … 所有块的右端点为: 1, 2, 3, 4, 5, 6, 7, 9, 12, 18, 37
  … 值域集合为: 37, 18, 12, 9, 7, 6, 5, 4, 3, 2, 1
  这点非常重要, 即: 所有值域, 都是右端点; 所有的右端点, 也是值域

• 性质六
  令两个相邻的块为: 定义域为[l1, r1], y值为y1 和 定义域为[l2, r2], y值为y2
  (自然有: r1 + 1 = l2, y1 > y2)
  则有: $\lfloor \frac{N}{[y1/y1-1/.../y2+1]}\rfloor =r1$
  也就是: $对于y\in [y2+1,y1],有:\lfloor \frac{N}{y}\rfloor =r1$
  证明:
  根据性质五: y2是a块的右端点, y1是a块右侧块的右端点.
  根据性质七的找r端点定理, $r1=\lfloor \frac{N}{y1}\rfloor ,r2=\lfloor \frac{N}{y2}\rfloor$
  也就是: r2是a块的y值, r1是a块右侧块的y值;
  即: a块为定义域为:[ ..., y2-1, y2], y值为r2, a块右侧块为定义域为: [ y2+1, ..., y1], y值为r1
  看(a块右侧块)来说, 有: $对于y\in [y2+1,y1],有:\lfloor \frac{N}{y}\rfloor =r1$

• 性质七
  对于一个矩阵 (也就是块), 令其横坐标为[l, r], 高为y, 表示: F( [l, ..., r]) = y, 他们的函数值均相同
  对于任意一个$x\in [l,r]$, 记作$y=\lfloor \frac{N}{x}\rfloor$, 则有: $r=\lfloor \frac{N}{y}\rfloor$, $l=\lfloor \frac{N}{y+1}\rfloor +1$
  即, 根据任意块内的一点x, 找到他的左右端点
  证明: $r=\lfloor \frac{N}{y}\rfloor$
  … 由性质五, 块的右端点 和 值域, 是双射.
  证明: $l=\lfloor \frac{N}{y+1}\rfloor +1$
  … 由性质六, $\lfloor \frac{N}{y+1}\rfloor$ 为左侧块的右端点

负数域

如果我们将 /除号, 定义为; 向0取整, 此时: N / i = - ( N / -i)
函数就是对称的 F( i) = -F( -i), 这样很方便. (如果是下/上取整, 不会有此性质)
当然, 还是要看题意 是怎么定义的. 如果没有规定, 选择(向0取整)最方便.

应用

求解: ${\sum }_{i=a}^{b}f(x)g(i),其中f(x)=\lfloor \frac{N}{i}\rfloor$下取整函数
N为常数, (这里只讨论a >= 1的情况)

暴力自然是O( b-a)的, 而由于下取整函数 只有2*log(N)个值域, 可以优化到: O( log( b-a))

假如某个块是: 定义域[l, r] 值为y
其在答案的贡献是: y*g( l) + y*g( l+1) + y*g( l+2) + ... + y*g( r) = y *( Sum[ r] - Sum[ l-1])

• Sum为 对g()函数的 前缀和.
• 如果b > N, 对于i > N的项, 因为f( > N) = 0, 所以, 这些项 不用考虑.

代码为:

Ll_ lef = a;
while( lef <= min( b, N)){ //< @Pos_0
    Ll_ rig = Get_right_boundary( lef);
    rig = min( rig, min( b, N)); //< @Pos_1
    ans += ( N / lef) * ( Sum[ rig] - Sum[ lef - 1]);
    lef = rig + 1;
}

Ll_ Get_right_boundary( Ll_ _x){
    return N / ( N / _x);
}
1
2
3
4
5
6
7
8
9
10
11

• @Pos_0 对于> N的项, 不用考虑;
  不仅如此, 下取整函数, 在x > N后, 值为0, 此时如果执行Get_right_boundary会(除0错误)
• @Pos_1这里非常重要! 非常容易在此出错
  lef虽然在范围, 但是其右端点rig, 虽然不会超过N, 但是, 可能超过b
  因此, 不仅lef要判断越界, rig也要再判断一次!

例题

• https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2521
  模板

• https://blog.csdn.net/weixin_42712593/article/details/126274824
  利用a%b = a - (a/b)*b公式转换