关于[x/y]一些小想法

时间:2023-03-08 17:08:32

[x/y],即x除以y下取整

(不会LATEX)

1.对于给定的x,对于所有的1<=y<=x,

[x/y]一共有√x种取值。

证明:

对于y<=√x,y有根号种,所以值最多根号种。对于y>√x,[x/y]<√x, 最多有根号种。

这种思想在根号分块处理的时候也很常见。

(必备技能:)

√x求[x/y]的和。

小于√x暴力枚举y。

大于√x,值只有√x中,所以暴力枚举[x/y]的值k,

等于k的区间长度就是,[x/(k-1)]+1 ~ [x/k],可以计算。

[x/y]再乘个什么数,也可以考虑转化成[x/y]的和,再计算。

2.数论分块。

不会留坑。

3.哪里会用到[x/y]呢?

反演(我不会)

a%b=a-[a/b]*b

可以考虑。尤其在之前出现类似的[a/b]时

在exgcd证明,裴属定理证明也用到过。

毕竟a%b不这么处理怎么办?

例题:9.10模拟赛T1mmt

4.如果我们要枚举连续的一些x,

假如y是固定的,[x/y]的值会发生变化,

当且仅当,x是y的倍数时,在x位置会比之前大1

所以,还有的启发是:若x|y,那么对于z∈(x~x+y-1),[z/y]=[x/y]

可以枚举y的倍数,在O(up/y)的时间内算出[x/y]的值。

如果y也从1~up,那总复杂度就是O(uplogup)的。

如果x不变,y从1~up,那就是上面的"必备技能”处理的了。

例题:EOJ 262 润清的烦恼

5.还有一个什么公式:[x/y/z]=[[x/y]/z]

可以直接根据[x/y]的定义,把x=[x/y]*y+x%y引入余数x%y=q

即可证明。

相关文章