关于 Lucas 定理
  • 板块学术版
  • 楼主WYXkkZzz Zzz
  • 当前回复18
  • 已保存回复18
  • 发布时间2020/11/21 14:24
  • 上次更新2023/11/5 07:36:38
查看原帖
关于 Lucas 定理
130151
WYXkkZzz Zzz楼主2020/11/21 14:24

众所周知,有个定理叫做 Lucas 定理。洛谷还有道模板题。它的含义是:

(nm)(n/pm/p)×(nmodpmmodp)(modp)\dbinom nm \equiv \dbinom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\times\dbinom{n\mod p}{m\mod p}\pmod p

但我学 MO 的时候学到了另一个 Lucas 定理,它的含义是:

vp((nm))=Sp(m)+Sp(nm)Sp(n)p1v_p\left(\dbinom nm\right)=\dfrac{S_p(m)+S_p(n-m)-S_p(n)}{p-1}

(左边并不是两个括号,外括号是表示函数的)

其中 vp(n)v_p(n) 表示 nn 的质因数分解中 pp 的出现次数,Sp(n)S_p(n) 表示 nnpp 进制下的数字和。右边式子的含义是 m+(nm)m+(n-m)pp 进制下的进位次数。

昨天有人和我说我 MO 学的那个叫库默尔定理,但是我在哪里看到的都是卢卡斯定理 /yun

所以有人知道这是怎么回事吗 /yun 是两个都叫 Lucas 定理,还是 MO 的那个不叫啊,如果是那为什么会这样呢

2020/11/21 14:24
加载中...