@总结 - 9@ 那些繁琐零碎却又不得不记住的数学

浅浅的花香味﹌ 2021-11-10 01:36 124阅读 0赞

*  @0 - 引言@
 *  @1 - 欧几里得算法@
    
     *  @1.1 - 欧几里得算法@
     *  @1.2 - 扩展欧几里得算法@
     *  @1.3 - 类欧几里得算法（留坑待填）@
 *  @2 - 逆元@
 *  @3 - 中国剩余定理@
    
     *  @3.1 - 中国剩余定理@
     *  @3.2 - 扩展中国剩余定理@
 *  @4 - 欧拉定理@
    
     *  @4.1 - 费马小定理@
     *  @4.2 - 欧拉定理@
     *  @4.3 - 扩展欧拉定理@
 *  @5 - 离散对数@
    
     *  @5.1 - 原根@
     *  @5.2 - BSGS（大步小步法）@
     *  @5.3 - exBSGS（扩展大步小步法）@
 *  @6 - 高次剩余@
    
     *  @6.1 - 利用离散对数@
     *  @6.2 - 二次剩余@
 *  @7 - 各类筛法@
    
     *  @7.1 - 线性筛@
     *  @7.2 - min\_25筛@
     *  @7.3 - 其他筛法（咕咕咕）@
 *  @8 - 莫比乌斯反演@
 *  @9 - 大数素性测试与因数分解@
    
     *  @9.1 - Miller-Rabin 算法@
     *  @9.2 - Pollard-Rho 算法@
 *  @10 - 组合数取模@
    
     *  @10.1 - lucas 定理@
     *  @10.2 - 扩展 lucas 定理@
 *  @11 - burnside 引理@

--------------------

## @0 - 引言@ ##

我发现学习数学要记住的东西实在太多了。。。  
所以专门开一个 blog 来整理收集一下。  
该篇博客应该会时刻保持 update。

如果是太过简单的东西就不予证明了。

## @1 - 欧几里得算法@ ##

### @1.1 - 欧几里得算法@ ###

**作用：用于求解两个整数的最大公因数。**

从最基础的开始吧。  
这个算法又被叫作“辗转相除法”，非常生动形象地表现了这个算法的流程。

只需要一句话就可以描述：  
\\\[gcd(a, b) = gcd(b, a \\mod b)\\\]

时间复杂度初步估计为 O(log n)。据说斐波拉契数列可以卡到 gcd 的最大时间。

### @1.2 - 扩展欧几里得算法@ ###

**作用：用于求解模线性方程：kx = a (mod m)。**

现在，我们来看一个比较难（？）的算法吧。  
稍微变化一下就可以等价的变为 kx + my = a。

显然 gcd(k, m) 如果不是 a 的因数，则无解。  
如果我们求解 kx' + my' = gcd(k, m) ，可以得到 x = x'*(a/gcd(k,m)), y = y'*(a/gcd(k,m))。  
我们仿照 gcd 的求法，稍微进行变换：

\\\[kx\_0 + my\_0 = gcd(k, m) = gcd(m, k \\mod m) = mx\_1 + (k \\mod m)y\_1\\\]  
\\\[kx\_0 + my\_0 = mx\_1 + (k - m\*\\lfloor \\frac\{k\}\{m\} \\rfloor)y\_1\\\]  
\\\[k(x\_0 - y\_1) + m(y\_0 - x\_1 + \\lfloor \\frac\{k\}\{m\} \\rfloor y\_1) = 0\\\]

注意我们现在只需要求出一组特解，而代入 \\(x\_0 = y\_1, y\_0 = x\_1 - \\lfloor \\frac\{k\}\{m\} \\rfloor y\_1\\) 即可使等式成立。

该算法和欧几里得算法一样只需要 O(log n) 的时间即可得出一组特解。

令 t = gcd(k, m)，则可以得到通解 x = x0 + a\*m/t, y = y0 - a\*k/t。  
求解通解（包括下面的涉及求解通解的算法）有一个常规的方法，假设存在另一组解，寻找两组解之间的关系。

### @1.3 - 类欧几里得算法（留坑待填）@ ###

咕咕咕。

## @2 - 逆元@ ##

**作用：实现模意义下的除法。**

比较简单的一个东西，大概主要是为后面作铺垫。  
可以发现模意义下是不可以直接除的，但是我们可以通过两边同时乘以 a 的逆元来间接实现除法。  
比如 \\(ab = c\\)，两边同时乘 \\(a\\) 的逆元 \\(a^\{-1\}\\) 可以得到 \\(b = c\*a^\{-1\}\\)。

可以发现逆元是满足 \\(ax = 1\\) 的解，所以直接扩欧即可。  
另外，根据我们即将要讲的费马小定理/欧拉定理 \\(a^\{\\phi(m)\} = 1\\mod m\\)，就可以得到 \\(a^\{phi(m)-1\} = 1\\mod m\\)。

预处理多个数的逆元还有着均摊 O(1) 的算法，也有两种方法：  
一种是处理 1~n 的逆元，可以采用以下方法推导：  
\\\[令 m = \\lfloor\\frac\{m\}\{p\}\\rfloor\*p + m\\mod p = k\*p + r\\\]  
\\\[k\*p + r = 0 \\mod m\\\]  
\\\[r = -k\*p -> p^\{-1\} = -k\*r^\{-1\}\\\]

因为 r 始终小于 p，所以就可以递推求出 p 的逆元。初始条件 1 的逆元为 1。

还有一种适用于求解任意 n 个数的逆元的方法。  
我们先求出 n 个数的前缀积，记为 S\[i\]，然后我们通过扩欧或者其他什么的求解出 S\[n\] 的逆元。  
因为 \\(S\[i\]\*A\[i+1\] = S\[i+1\]\\)，所以 \\(\\frac\{A\[i+1\]\}\{S\[i+1\]\} = \\frac\{1\}\{S\[i\]\}\\)，即我们可以线性递推出所有前缀积的逆元。  
又因为 \\(\\frac\{S\[i\]\}\{S\[i+1\]\} = \\frac\{1\}\{A\[i+1\]\}\\) 所以又可以求解出所有数的逆元。

## @3 - 中国剩余定理@ ##

### @3.1 - 中国剩余定理@ ###

**作用：求解模数互质情况下的模线性方程组。**

我们通过扩欧算法解决了模线性方程，而通过这个算法我们就可以解决模线性方程组。

已知 \\(x = a\_0 \\mod m\_0, x = a\_1 \\mod m\_1, ..., x = a\_n (mod m\_n)\\)。  
如果 mi 之间两两互质，则可以仿照拉格朗日插值的方法得到 x 的解。

记 \\(M = m\_0\*m\_1\*...\*m\_n\\)，再记 \\(inv(a, m)\\) 表示模 m 意义下 a 的逆元，则：  
\\\[x = \\sum\_\{i=0\}^\{n\}a\_i\*\\frac\{M\}\{m\_i\}\*inv(\\frac\{M\}\{m\_i\}, m\_i) \\mod M\\\]

只需要证明这是一组特解与通解也具有这种形式即可。

### @3.2 - 扩展中国剩余定理@ ###

**作用：求解任意模数的模线性方程组。**

这个时候就不能用插值的思想来做了。  
为简化问题，我们不妨先只考虑两个方程组成的方程组，记这两个方程为 x = a0 mod m0, x = a1 mod m1。

首先我们将其等价地写为 x = m0\*p + a0, x = m1\*q + a1。  
于是我们就有 x = m0\*p + a0 = m1\*q + a1，稍微变形可以得到扩欧的基本形式之一 m0\*p - m1\*q = (a1 - a0)。  
通过上面的理论，该方程可以解得 p = b0 + k0\*t, q = b1 + k1\*t。  
将 p 代入最开始的式子，可以得到 x = m0\*(b0 + k0\*t) + a0 = m0\*b0 + a0 + m0\*k0\*t。  
于是就有 x = m0\*b0 + a0 mod m0\*k0。

根据如上的推导，我们可以每次将两个方程合并，直到只剩下一个方程为止。  
注意这中间的扩欧可能是会无解的，此时整个方程组也无解。

## @4 - 欧拉定理@ ##

### @4.1 - 费马小定理@ ###

**作用：在模数是质数的情况下，用于指数的取模、求解逆元。**

定理的描述只有一个公式：  
\\\[a^\{p-1\} = 1 \\mod p\\\]

其中 p 是质数。使用条件只需要 a 不是 p 的倍数即可。  
稍微变化一下就可以得到 a 的逆元 \\(a^\{p-2\} = a^\{-1\} \\mod p\\)。  
一般情况下写费马小定理比写扩欧要快得多，而且快速幂本身作为一个基础功能也可以用于其他地方。

指数取模的意思是 \\(a^b = a^\{b\\mod p-1\} \\mod p\\)，至于正确性是很显然的。

证明需要用到剩余系什么的，因为过于数论所以就暂且不提。

### @4.2 - 欧拉定理@ ###

**作用：在模数与底数互质的情况下，用于指数的取模、求解逆元。**

定理的描述一样只有一个公式：  
\\\[a^\{\\phi(m)-1\} = 1 \\mod m\\\]

适用条件是 gcd(a, m) = 1。可以发现这也是扩欧有解的条件。  
取 m 为质数，则 \\(\\phi(m) = m - 1\\)。于是费马小定理就是欧拉定理的一个特例。  
但是因为欧拉函数 \\(\\phi\\) 并不好求，所以一般实用性不如费马小定理。

证明一样要用什么既约剩余系，太过于数论所以暂且不提。

### @4.3 - 扩展欧拉定理@ ###

**作用：用于指数的取模。**

这个定理相比上述两条不需要任何的适用条件，具有普适性。描述如下：  
\\\[a^\{p\} = a^\{phi(m) + p\\mod phi(m)\}\\mod m\\\]

证明提及一下简要的过程。首先我们从 m 中提取某个质因子 p，使得 m = s\*p^r（其中 s 与 p 互质）。然后：  
\\\[p^\{\\phi(s)\} = 1 \\mod s\\\]  
\\\[p^\{\\phi(m)\} = 1 \\mod s(由积性函数的性质)\\\]  
\\\[p^\{k\*\\phi(m)\} = 1 \\mod s\\\]  
\\\[p^\{k\*\\phi(m) + r\} = p^r \\mod s\*p^r = p^r \\mod m\\\]

将 a 也拆成质因子相乘的形式，如果 a 的某个质因子 m 不含有就套用欧拉定理，否则如上所示。

## @5 - 离散对数@ ##

### @5.1 - 原根@ ###

**作用：理论依据。**

阶是满足 \\(a^p = 1\\mod m\\) 的最小正整数 p（显然要求 gcd(a, m) = 1）。  
我们需要的有关阶的性质一般只用得着 \\(p|\\phi(m)\\) 这一个。

模 m 意义下的原根 g 的阶为 \\(phi(m)\\)。或者说，对于 0 < i <= phi(m) 满足 g^i 的值互不相同。  
怎么检验一个原根呢？貌似按照定义需要检验 1~phi(m) 的所有数作为幂。  
但是我们有阶一定是 \\(\\phi(m)\\) 的因数。考虑进行唯一分解： \\(\\phi(m) = p\_0^\{a\_0\}\*p\_1^\{a\_1\}\*...\\)。  
于是如果 x 的阶不为 \\(phi(m)\\)，则存在一个 i 使得 \\(x^\{\\frac\{\\phi(m)\}\{p\_i\}\} = 1 \\mod m\\)。  
然后就可以比较快地检验原根。至于寻找原根可以采用枚举 + 检验的方法。

原根还有一些其他性质，比如当模数为 2, 4, p^a, 2\*p^a 时才有原根，以及原根个数为 \\(\\phi(\\phi(m))\\) 个。

通过原根 g 可以将所有数表示为 g^p 的形式，实现在模意义下的“对数”。也即是 离散对数 或 指标。  
于是就可以将乘法转为加法，将模型进行转化（比如将下标作乘法的卷积变为下标作加法的卷积然后 fft）。

### @5.2 - BSGS（大步小步法）@ ###

**作用：在模数为质数的要求下求解离散对数 a^x = b mod p。**

刚刚我们介绍了原根，但是即使使用原根也没有什么高效的算法。事实上，这个问题也没什么高效的解法（比如线性或对数时间复杂度）  
不过我们可以写一个勉强可以接受的时间复杂度：\\(O(\\sqrt\{p\})\\)。  
看到这个时间复杂度想必大家都知道应该怎么做了：分块。

我们令 \\(c = \\sqrt\{p\}, x = kc - b(1 \\le b \\le c, k \\ge 1)\\)（注意这里是减法，因为用减法下面的推导更为方便）（还要注意两个参数的取值范围，只有这样才能全覆盖）。  
则可以得到 \\(A^\{kc-b\} = B\\mod p\\)，稍作变换可得 \\(A^\{kc\} = B\*A^\{b\}\\mod p\\)。  
注意等式左边与右边分别只有根号种取值。我们将右边的所有可能值预处理出来存入 hash 中，然后再枚举左边并在 hash 中寻找。

暴力而优雅的分块。

### @5.3 - exBSGS（扩展大步小步法）@ ###

**作用：任意模数下求解离散对数 a^x = b mod p。**

事实上不带扩展的版本可以解决 gcd(a, p) = 1 的情况。  
主要的问题是当 gcd(a, p) ≠ 1 时，a 的逆元不一定存在。

令 t = gcd(a, p)，我们尝试在等式两边及模数同时除以 t，得到 \\(\\frac\{a\}\{t\}\*a^\{x-1\} = \\frac\{b\}\{t\} \\mod \\frac\{p\}\{t\}\\)。  
此时因为 a/t 与 p/t 互质，所以有 \\(a^\{x-1\} = \\frac\{b\}\{t\}\*(\\frac\{a\}\{t\})^\{-1\}\\mod \\frac\{p\}\{t\}\\)。  
于是就可以这样迭代到 a 与新的模数 p' 互质然后使用 BSGS 即可。

然而这个过程有两个问题：  
一是，当 t 不能整除 b 时会出现问题；二是，a 上的指数在不断减，如果真正的解小于迭代次数（比如 x = 0）会出问题。

当 b = 1 时，其实存在解 x = 0。当 b 不为 1 也不为 t 的倍数时，无解。因此我们解决了第一个问题。  
我们通过特判 b = 1，就可以避免我们的第二个问题：因为所有可能的解要么在最后的 BSGS 中求解出来，要么在特判时求解出来。

实现中可以不用真的去求 \\(\\frac\{a\}\{t\}\\) 的逆元，用一些等价的方法判断即可。

## @6 - 高次剩余@ ##

这个我会的也不是很多。。。数论学得不太好。。。

### @6.1 - 利用离散对数@ ###

**作用：有原根的情况下求解高次剩余 x^a = n mod p。**

将 x 和 b 都表示为原根的幂，得到：  
\\\[g^\{y\*a\} = g^\{k\}\\mod p\\\]

根据上面的什么欧拉定理就可以指数取模，然后得到一个模线性方程，然后 exgcd 即可。

### @6.2 - 二次剩余@ ###

**作用：模数为素数的情况下求解二次剩余 x^2 = n mod p。**

首先素数分 2 和奇素数。2 不必多说，我们接下来只考虑奇素数。

先来看看怎么判断一个数 k 是否为二次剩余。由费马小定理我们有 \\(k^\{p-1\}=1\\mod p\\)，于是就有 \\(k^\{\\frac\{p-1\}\{2\}\} = 1或-1\\mod p\\)  
假设 k 有二次剩余 x，则有 \\(k^\{\\frac\{p-1\}\{2\}\} = x^\{p-1\} = 1\\mod p\\)。  
假设 \\(k^\{\\frac\{p-1\}\{2\}\} = 1\\mod p\\)，用原根表示 k 得到 \\(g^\{ \{\\frac\{p-1\}\{2\}\}\*a\} = 1 = g^\{p-1\} \\mod p\\)，所以 a 为偶数，所以 \\(g^\{\\frac\{a\}\{2\}\}\\) 是 k 的二次剩余。  
我们就得到了 k 是二次剩余的充要条件。这个好像叫作欧拉准则。

随机一个 a，取 w = a^2 - n。我们要随机出一个合适的 a 使得 w 为非二次剩余。  
因为二次剩余与非二次剩余的数量相同，所以期望 2 次就可以找到这样一个 a。  
然后求 \\((a+\\sqrt\{w\})^\{\\frac\{p+1\}\{2\}\}\\) 就可以得到 n 的二次剩余。  
这里的 \\(a+\\sqrt\{w\}\\) 可以类比复数中的 \\(i=\\sqrt\{-1\}\\) 来理解。

为什么？首先我们证明 \\((a+\\sqrt\{w\})^\{p+1\} = n\\)。  
因为 \\((a+\\sqrt\{w\})^p = a^p + \\sqrt\{w\}^p + \\sum\_\{i=1\}^\{p-1\}C\_p^ia^i\*\\sqrt\{w\}^\{p-i\}\\)，又因为 \\(C\_p^i\\) 一定是 p 的倍数（因为 p 是素数），所以就可以得到 \\((a+\\sqrt\{w\})^p = a^p + \\sqrt\{w\}^p\\)。  
由于 w 是非二次剩余，所以就有 \\(w^\{\\frac\{p-1\}\{2\}\} = \\sqrt\{w\}^\{p-1\} = -1\\)。又因费马小定理可得 \\(a^p = a\\)，所以原式变为 \\(a - \\sqrt\{w\}\\)。  
所以 \\((a+\\sqrt\{w\})^\{p+1\} = (a+\\sqrt\{w\})(a - \\sqrt\{w\}) = a^2 - w = n\\)。

再证明 \\((a+\\sqrt\{w\})^\{\\frac\{p+1\}\{2\}\}\\) 中 \\(\\sqrt\{w\}\\) 的系数为 0。  
令 \\((a+\\sqrt\{w\})^\{\\frac\{p+1\}\{2\}\} = u + v\*\\sqrt\{w\}\\)，所以有 \\((u + v\*\\sqrt\{w\})^2 = u^2 + v^2\*w + 2\*u\*v\*\\sqrt\{w\} = n\\)。  
所以 u = 0 或 v = 0 成立。我们反证，不妨假设 u = 0 而 v ≠ 0，则 \\(v^2\*w = n\\)。  
左边不是二次剩余，而右边是二次剩余，矛盾。

一个 O(log n) 的算法，但是非常具有构造性。。。

## @7 - 各类筛法@ ##

### @7.1 - 线性筛@ ###

### @7.2 - min\_25筛@ ###

### @7.3 - 其他筛法（咕咕咕）@ ###

## @8 - 莫比乌斯反演@ ##

## @9 - 大数素性测试与因数分解@ ##

### @9.1 - Miller-Rabin 算法@ ###

### @9.2 - Pollard-Rho 算法@ ###

## @10 - 组合数取模@ ##

### @10.1 - lucas 定理@ ###

### @10.2 - 扩展 lucas 定理@ ###