差别

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

--- 2020-2021:teams:namespace:素数幂次与p进数问题 [2020/06/06 17:00]
great_designer [2进数]
+++ 2020-2021:teams:namespace:素数幂次与p进数问题 [2020/08/01 23:12] (当前版本)
great_designer [二项式展开的部分和]
@@ 行 1: / 行 1: @@
-======素数幂次问题======
+======素数幂次与p进数问题======
 =====记号约定=====
@@ 行 138: / 行 138: @@
 与等比数列求和公式很相似。由于涉及各位数字和，利用数学归纳法可以轻松证明。
+特别地，阶乘中2的幂次是：
+$$v_2(n!)=n-S_2(n)$$
 =====p进数的指对数=====
@@ 行 159: / 行 163: @@
 在2进数中，仅当被4整除的数可以计算指数，被4除余1的数可以计算对数。这比奇素数时要严格。
-（其实所有奇数均可计算对数，均在对数收敛域内。但是全体被4除余3的数算出来的对数不满足后文的双射条件，算出的对数值再代入指数无法得到原数，而是它的相反数——被4除余1的数，因此不再讨论）
+其实所有奇数均在对数收敛域内。但是全体被4除余3的数算出来的对数不满足后文的双射条件，算出的对数值再代入指数无法得到原数，而是它的相反数——被4除余1的数。这是由于如果代入计算$\ln (-1)$，会算出它等于0。
 我们可以计算2进数下的$e^4$和$\ln 5$，进而直观了解指对数：任意指数都是$e^4$的指数，利用换底公式可以转换成以5为底的对数，从而与前一篇缩系乘法群中以5为底的对数对比。
@@ 行 203: / 行 207: @@
 =====素数在组合数中的幂次=====
-（一个公式待补充）
+组合数对一个数取模的结果，往往构成分形结构，例如著名的谢尔宾斯基三角形就可以通过组合数模2得到。
+$$v_p(C_m^n)=\frac{S_p(n)+S_p(m-n)-S_p(m)}{p-1}$$
 如果仔细分析，p是否整除组合数其实和上下标在p进制下减法是否需要借位有关。这就有了下面的定理。
-（待补充）
+**p在组合数$C_m^n$中的幂次，恰好是p进制下m减掉n需要借位的次数。**
+特别地，组合数中2的幂次是：
+$$v_2(C_m^n)=S_2(n)+S_2(m-n)-S_2(m)$$
 =====Lucas定理=====
+====定理====
 <html><span style="color:white">不是Lucario</span></html>
@@ 行 215: / 行 227: @@
 结合上面“素数在组合数中的幂次”一同分析。上面的部分用于计算当组合数被p整除时，一共能被多少个p整除（仅判断模p的幂是否为0）；而这里则研究当组合数不被p整除时，模p余多少。
-（待补充）
+对于组合数，有同余式：
+$$C_{m_1p+m_2}^{n_1p+n_2}\equiv C_{m_1}^{n_1}C_{m_2}^{n_2} \mod p$$
 至于到算法层面，还有与中国剩余定理结合的扩展卢卡斯算法（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偶数条件以外，只与一位有效数字有关，与再左边全没关系。

CVBB ACM Team

用户工具

站点工具

差别

页面工具