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

差别

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

到此差别页面的链接

--- 2020-2021:teams:namespace:素数幂次与p进数问题 [2020/06/09 10:42]
great_designer [2进数]
+++ 2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 23:12] (当前版本)
great_designer [二项式展开的部分和]
@@ 行 220: / 行 220: @@
 =====Lucas定理=====
+====定理====
 <html><span style="color:white">不是Lucario</span></html>
@@ 行 231: / 行 233: @@
 至于到算法层面，还有与中国剩余定理结合的扩展卢卡斯算法（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进数中的平方元=====
+首先要在p进数中引入类似于二次剩余的概念。根据p进数的定义，即取p的幂次模后能区分的程度作为p进数右侧的数位，模p的幂中的平方元放在p进数中就变为了p进数中相应的平方元。
+首先来对比一下整数、有理数和实数中的平方元：
+整数的平方元是离散的，分别为0，1，4，9，……。
+有理数的平方元，就是整数平方元之比。
+实数中的平方元是全体非负数，并且全体负数都是非平方元。
+注意，在这里就出现了负数和非负数的区分。这一点其实很重要。
+首先，p进数的书写方法与p进制数相同，但是右边有限，左边无穷，这点已经提到了。
+于是，每一个p进数都可以**唯一**表示为p的n次方乘u的形式。其中u小数点后没有内容，并且小数点前一位非0。
+（相当于将p的因子全部提出来）
+于是，p进数为平方元的充要条件为：n是偶数，并且u小数点前一位是模p的二次剩余。
+这体现了p进数中的平方元具有某种聚集的特征，除了含p偶数条件以外，只与一位有效数字有关，与再左边全没关系。

2020-2021/teams/namespace/素数幂次与p进数问题.1591670572.txt.gz · 最后更改: 2020/06/09 10:42 由 great_designer