2020-2021:teams:namespace:素数幂次与p进数问题

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:namespace:素数幂次与p进数问题 [2020/06/23 17:37]
great_designer
+++ 2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 23:12] (当前版本)
great_designer [二项式展开的部分和]
@@ 行 220: / 行 220: @@
 =====Lucas定理=====
+====定理====
 <html><span style="color:white">不是Lucario</span></html>
@@ 行 230: / 行 232: @@
 至于到算法层面，还有与中国剩余定理结合的扩展卢卡斯算法（exlucas），用于解决模p的幂的余数问题。由于本文注重数学部分，这里不再讲解。
+它的证明也不难。就以下两步，然后用到二项展开。
+$${(x+1)}^{n_1p+n_2}={(x+1)}^{n_1p}{(x+1)}^{n_2}$$
+$${(x+1)}^p\equiv x^p+1 \mod p$$
+====二项式展开的部分和====
+给定n、m、x，计算多项式取模意义下的值：
+$$\sum_{k=0}^{m} C_n^kx^k$$
+记带余除法：
+$$n=n_1p+n_2$$
+$$m=m_1p+m_2$$
+将幂和组合数同时用Lucas定理拆开，有：
+$$\sum_{k=0}^{m} C_n^kx^k\equiv\sum_{t=0}^{m_1-1}C_{n_1}^tx^t\sum_{r=0}^{p-1}C_{n_2}^rx^r+C_{n_1}^{m_1}x^{m_1}\sum_{r=0}^{m_2}C_{n_2}^rx^r={(1+x)}^{n_2}\sum_{t=0}^{m_1-1}C_{n_1}^tx^t+C_{n_1}^{m_1}x^{m_1}\sum_{r=0}^{m_2}C_{n_2}^rx^r\mod p$$
+可以对新的n_1继续迭代，最终只需预处理若干个C_{n_2}^rx^r即可。
 =====p进数中的平方元=====

2020-2021/teams/namespace/素数幂次与p进数问题.1592905069.txt.gz · 最后更改: 2020/06/23 17:37 由 great_designer