本篇只讲解大部分提高组考纲内的数论，主要目的为自我分析与积累学习。部分数学会有代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 矩阵
> 接下来的 AAA 和 BBB 都分别代表矩阵
1.1 矩阵的概念
矩阵是行和列排列的数表。nnn 行 mmm 列的矩阵称为 n×mn\times mn×m 矩阵。
Aij{A_i}_jAi j 表示第 iii 行，第 jjj 列的元素。
1.2 特殊的矩阵
* 方阵：n=mn=mn=m 的矩阵
* 零矩阵：所有元素都是 000 的矩阵
* 单位矩阵：主对角线都是 111，其它位置都是 000 的矩阵
* 对角矩阵：除主对角线外（主对角线可以随意），其它位置都是 000 的矩阵。单位矩阵是特殊的对角矩阵
1.3 矩阵的转置
简单来说，就是 行→列,列→行行 \rightarrow 列,列 \rightarrow 行行→列,列→行
将矩阵加一个 T^TT，表示转置
[1,2,34,5,6]T→[1,23,45,6]\begin{bmatrix} 1,2,3 \\ 4,5,6 \end{bmatrix}^T \rightarrow \begin{bmatrix} 1,2 \\ 3,4 \\ 5,6 \end{bmatrix} [1,2,34,5,6 ]T→ 1,23,45,6
1.4 矩阵的加法
矩阵加法的前提：同型矩阵（A的n=B的n且A的m=B的mA的n=B的n且A的m=B的mA的n=B的n且A的m=B的m）
(A±B)ij=Aij±Bij比如[1,2,34,5,6]+[1,2,34,5,6]=[2,4,68,10,12]{(A \pm B)_i}_j={A_i}_j \pm {B_i}_j\\ 比如 \begin{bmatrix} 1,2,3 \\ 4,5,6 \end{bmatrix}+ \begin{bmatrix} 1,2,3\\4,5,6 \end{bmatrix}=\begin{bmatrix} 2,4,6\\8,10,12 \end{bmatrix} (A±B)i j =Ai j ±Bi j 比如[1,2,34,5,6 ]+[1,2,34,5,6 ]=[2,4,68,10,12 ]
矩阵加法满足交换律与结合律
1.5 矩阵的乘法
矩阵乘法的前提：A为n×m,B为m×pA 为 n \times m,B为m\times pA为n×m,B为m×p，矩阵乘法后的结果大小为 n×pn\times pn×p
(AB)ij=∑k=1mAikBkj{(AB)_i}_j=\sum_{k=1}^{m} {A_i}_k{B_k}_j (AB)i j =k=1∑m Ai k Bk j
也就是用 AAA 的第 iii 行与 BBB 的第 jjj 列相乘后求和。
比如[1,2,34,5,6]×[1,2,3,45,6,7,89,10,11,12]=[38,44,50,5683,98,113,128]因为1×1+2×5+3×9=38→这就是第1行第1列的值然后以此类推，可以得到结果比如 \begin{bmatrix} 1,2,3 \\ 4,5,6 \end{bmatrix}\times \begin{bmatrix} 1,2,3,4\\5,6,7,8\\9,10,11,12 \end{bmatrix}=\begin{bmatrix} 38,44,50,56\\83,98,113,128 \end{bmatrix}\\ 因为
1\times1+2\times5+3\times9=38\rightarrow这就是第1行第1列的值\\ 然后以此类推，可以得到结果 比如[1,2,34,5,6 ]× 1,2,3,45,6,7,89,10,11,12 =[38,44,50,5683,98,113,128 ]因为1×1+2×5+3×9=38→这就是第1行第1列的值然后以此类推，可以得到结果
矩阵乘法满足结合律和分配律，但一般不满足交换律
代码实现也很简单，时间复杂度 O(n3)O(n^3)O(n3)
1.6 矩阵快速幂
拿斐波那契数列举例子
朴素递归实现 O(2n)O(2^n)O(2n)，递推/记忆化搜索 O(n)O(n)O(n)，但是这样对于 n≥109n\ge 10^{9}n≥109 会超时
而矩阵快速幂可以在 O(log n)O(log~n)O(log n) 的时间复杂度内解决
原理是通过矩阵乘法
先构造一个矩阵[1,11,0]然后[1,11,0]×[F1(斐波那契数列的第1项)F0(斐波那契数列的第0项)]=[1×F1+1×F01×F1+0×F0]=[F2F1]先构造一个矩阵\begin{bmatrix} 1,1 \\ 1,0 \end{bmatrix}\\ 然后 \begin{bmatrix} 1,1 \\ 1,0 \end{bmatrix}\times \begin{bmatrix} F_1(斐波那契数列的第1项)\\F_0(斐波那契数列的第0项) \end{bmatrix}=\begin{bmatrix} 1\times F_1+1\times F_0\\1\times
F_1+0\times F_0 \end{bmatrix}=\begin{bmatrix} F_2\\F_1 \end{bmatrix} 先构造一个矩阵[1,11,0 ]然后[1,11,0 ]×[F1 (斐波那契数列的第1项)F0 (斐波那契数列的第0项) ]=[1×F1 +1×F0 1×F1 +0×F0 ]=[F2 F1 ]
这样就可以快速求出斐波那契数列的所有项了，即
[1,11,0]n−1[F1F0]=[FnFn−1] \begin{bmatrix} 1,1 \\ 1,0 \end{bmatrix}^{n-1}\begin{bmatrix} F_1\\F_0\end{bmatrix}=\begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} [1,11,0 ]n−1[F1 F0 ]=[Fn Fn−1 ]
1.7 由递推式子构造转移矩阵完整步骤
感谢@Xylophone的建议
1.7.1 第一步：写出线性递推公式
要求只能是常系数线性递推公式（无常数项、无平方项）
咱们这次换个复杂的例子 fn=2fn−1+fn−2+1（n≥3）f_n=2f_{n-1}+f_{n-2}+1（n\ge3）fn =2fn−1 +fn−2 +1（n≥3）
1.7.2 第二步：构造状态列向量 FN⃗\VEC{F_N}FN
向量里放递推需要用到的最近若干项，项数 = 递推阶数
这里是 333 阶递推，向量长度 =3= 3=3
我们希望：
[fnfn−11]=T[fn−1fn−21]\begin{bmatrix} f_n\\f_{n-1}\\1 \end{bmatrix}=T\begin{bmatrix} f_{n-1}\\f_{n-2}\\1 \end{bmatrix} fn fn−1 1 =T fn−1 fn−2 1
1.7.3 第三步：推导矩阵 TTT
拆开左边：
{fn=2×fn−1+1×fn−2+1×1fn−1=1×fn−1+0×fn−2+0×11=0×fn−1+0×fn−2+1×1 \begin{cases} f_n=2\times f_{n-1}+1\times f_{n-2}+1\times 1 \\ f_{n-1}=1\times f_{n-1}+0\times f_{n-2}+0\times 1\\ 1=0\times f_{n-1}+0\times f_{n-2}+1\times 1 \end{cases}\\ ⎩⎨⎧ fn =2×fn−1 +1×fn−2 +1×1fn−1 =1×fn−1 +0×fn−2 +0×11=0×fn−1
+0×fn−2 +1×1
于是构造如下矩阵 TTT:
T=[2,1,11,0,00,0,1]T=\begin{bmatrix} 2,1,1\\1,0,0\\0,0,1 \end{bmatrix} T= 2,1,11,0,00,0,1
2 筛法
2.1 埃氏筛
从小到大枚举，未标记数为质数，从 p2p^2p2 开始标记其倍数
时间复杂度 O(n log log n)O(n~log~log~n)O(n log log n)
代码：
2.2 线性筛
使用已找到的质数筛去合数，每个合数只由最小质因子筛一次
时间复杂度 O(n)O(n)O(n)
代码：
3 欧拉函数
φ(n)φ(n)φ(n) 代表：≤n\le n≤n 且和 nnn 互质的正整数一共有多少个
比如 φ(6)=2→1和5,φ(5)=4→1,2,3,4比如~φ(6)=2\rightarrow 1和5,φ(5)=4\rightarrow 1,2,3,4比如 φ(6)=2→1和5,φ(5)=4→1,2,3,4
* 规律1：如果 ppp 是质数，则 φ(p)=p−1φ(p)=p-1φ(p)=p−1
* 规律2：φ(1)=1φ(1)=1φ(1)=1
* 规律3：如果 ppp 为质数，则 ppp 的幂 pkp^kpk 有 φ(pk)=pk−pk−1φ(p^k)=p^k-p^{k-1}φ(pk)=pk−pk−1
3.1 计算方式
把 nnn 拆成质数相乘：n=p1k1×p2k2×⋯×pnknn={p_1}^{k_1}\times{p_2}^{k_2}\times\cdots\times{p_n}^{k_n }n=p1 k1 ×p2 k2 ×⋯×pn kn
然后就是 n×(1−1p1)×(1−1p2)×⋯×(1−1pn)n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_n})n×(1−p1 1 )×(1−p2 1 )×⋯×(1−pn 1 )
φ(n)=n∏i=1k(n的不同质因子个数)(1−1pi)φ(n)=n\prod_{i=1}^{k(n的不同质因子个数)} (1-\frac{1}{p_i}) φ(n)=ni=1∏k(n的不同质因子个数) (1−pi 1 )
3.2 实现代码（线性筛+递推）
3.3 欧拉定理
> 同余符号为 ≡\equiv≡，如果 aaa 与 bbb 除以正整数 mmm 的余数相同，记作 a≡b(mod m)a\equiv b(mod~m)a≡b(mod m)
若 gcd(a,n)=1gcd(a,n)=1gcd(a,n)=1 则：
aφ(n)≡1(mod n)a−1≡aφ(n)−1(mod n)a^{φ(n)}\equiv1(mod~n)\\ a^{-1}\equiv a^{φ(n)-1}(mod~n) aφ(n)≡1(mod n)a−1≡aφ(n)−1(mod n)
3.3.1 欧拉定理的扩展 →\RIGHTARROW→ 费马小定理
若 nnn 为质数，则 φ(n)=n−1φ(n)=n-1φ(n)=n−1
那么
an−1≡1(mod n)→费马小定理a^{n-1}\equiv1(mod~n) \rightarrow 费马小定理 an−1≡1(mod n)→费马小定理
3.4 （扩展）有关约数的计算
3.4.1 约数个数
(a1+1)×(a2+1)×⋯×(an+1)(a_1+1)\times(a_2+1)\times\cdots\times(a_n+1) (a1 +1)×(a2 +1)×⋯×(an +1)
3.4.2 约数之和
(1+p11+p12+⋯+p1a1)×(1+p21+p22+⋯+p2a2)×⋯×(1+pn1+pn2+⋯+pnan)(1+{p_1}^1+{p_1}^2+\cdots+{p_1}^{a_1})\times(1+{p_2}^1+{p_2}^2+\cdots+{p_2}^{a_2})\times\cdots\times(1+{p_n}^1+{p_n}^2+\cdots+{p_n}^{a_n}) (1+p1 1+p1 2+⋯+p1 a1 )×(1+p2 1+p2 2+⋯+p2 a2 )×⋯×(1+pn 1+pn 2+⋯+pn an )
4 乘法逆元
4.1 定义
若 ax≡1(mod m)ax\equiv1(mod~m)ax≡1(mod m)，则 xxx 是 a mod ma~mod~ma mod m 的乘法逆元
逆元存在的条件为：gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1
在这种情况下，a−1a^{-1}a−1 代表 aaa 的逆元
4.2 逆元的帮助
一般来说，除法是无法“边除边模”的
ax≡1(mod m) ba≡b×a−1(mod m)ba≡b×a−1(mod m)=b≡b×a−1×a(mod m)=1≡a−1a(mod m)=a×a−1≡1(mod m)ax\equiv1(mod~m)~~~~~~~~~~\frac{b}{a}\equiv b\times a^{-1}(mod~m)\\ \frac{b}{a}\equiv b\times a^{-1}(mod~m)\\ =b\equiv b\times a^{-1}\times a(mod~m)\\ =1\equiv a^{-1}a(mod~m)\\ =a\times
a^{-1}\equiv1(mod~m) ax≡1(mod m) ab ≡b×a−1(mod m)ab ≡b×a−1(mod m)=b≡b×a−1×a(mod m)=1≡a−1a(mod m)=a×a−1≡1(mod m)
但是通过这样的计算，就可以把除法转化为乘法，从而使得除法也可以“边除边模”
4.3 逆元的常用计算方式
4.3.1 当 MMM 为质数时，可以使用费马小定理
aφ(n)≡1(mod m)=am−1≡1(mod m)对比两个式子：a×a−1≡1(mod m)和am−1≡1(mod m)可以得到：a×a−1=am−1那么：a−1=am−2a^{φ(n)}\equiv1(mod~m)\\ =a^{m-1}\equiv1(mod~m) \\ 对比两个式子：a\times a^{-1}\equiv1(mod~m)和a^{m-1}\equiv1(mod~m)\\ 可以得到：a\times a^{-1}=a^{m-1}\\ 那么：a^{-1}=a^{m-2}
aφ(n)≡1(mod m)=am−1≡1(mod m)对比两个式子：a×a−1≡1(mod m)和am−1≡1(mod m)可以得到：a×a−1=am−1那么：a−1=am−2
这里就不展示代码了，只需要掌握快速幂的模板即可，用扩欧也可以求
4.3.2 当 MMM 不为质数，无法使用费马小定理，因此可以使用扩展欧几里得
4.3.2.1 前置知识：裴蜀定理
裴蜀定理：对于任意正整数 a,ba,ba,b，一定存在非零整数 x,yx,yx,y，使得 ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)
4.3.2.2 前置知识：欧几里得算法
欧几里得算法：gcd(a,b)=gcd(b,a mod b) b=0时gcd(a,b)=agcd(a,b)=gcd(b,a~mod~b)~~~~~~~~~~b=0时gcd(a,b)=agcd(a,b)=gcd(b,a mod b) b=0时gcd(a,b)=a
4.3.2.3 扩展欧几里得算法
先是根据裴蜀定理得到 xxx 和 yyy
然后这里引入一个算式：
by+(a mod b)×x=gcd(a,b)其中 a mod b=a−⌊ab⌋×b也就是 by+(a−⌊ab⌋×b)×x=gcd(a,b)那么 ax+b(y−⌊ab⌋x)=gcd(a,b)by+(a~mod~b)\times x=gcd(a,b)\\ 其中~a~mod~b=a-\lfloor\frac{a}{b}\rfloor\times b\\ 也就是~by+(a-\lfloor\frac{a}{b}\rfloor\times b)\times x=gcd(a,b)\\ 那么~ax+b(y-\lfloor\frac{a}{b}\rfloor x)=gcd(a,b)
by+(a mod b)×x=gcd(a,b)其中 a mod b=a−⌊ba ⌋×b也就是 by+(a−⌊ba ⌋×b)×x=gcd(a,b)那么 ax+b(y−⌊ba ⌋x)=gcd(a,b)
继续代码：
这样就能计算出 xxx 和 yyy 的值了
然后我们回到逆元 ax≡1(mod m)ax\equiv1(mod~m)ax≡1(mod m)
对比两个式子：ax≡1(mod m) ax+by=gcd(a,b)ax\equiv1(mod~m)~~~~~~~~~~ax+by=gcd(a,b)ax≡1(mod m) ax+by=gcd(a,b)
当 b=mb=mb=m 时，ax+my=gcd(a,m)ax+my=gcd(a,m)ax+my=gcd(a,m)
既然逆元的存在条件是 gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1，那么可以得到 ax+my=1ax+my=1ax+my=1
然后 mymymy 这部分在 mod mmod~mmod m 的情况下为 000，因此 ax≡1(mod m)ax\equiv1(mod~m)ax≡1(mod m)
所以扩展欧几里得算法计算完毕后，得到的 xxx 就是 aaa 的逆元
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
还有一种手算逆元的方法，仅适用于模数较小的时候：
要求 aaa 在模 mmm 意义下的逆元，就是要找 xxx 使得 ax≡1 (mod m)ax\equiv1~(mod~m)ax≡1 (mod m)
使用枚举的方法，从1开始枚举，直到找到第一个 xxx 满足上方算式即可
注意仍然要检查逆元存在的充要条件（gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1）
5 中国剩余定理
中国剩余定理用于求形如：
x≡a1(mod m1)x≡a2(mod m2)⋯x≡an(mod mn)这个方程组中x的值x\equiv a_1(mod~m_1)\\ x\equiv a_2(mod~m_2)\\ \cdots\\ x\equiv a_n(mod~m_n)\\ 这个方程组中x的值 x≡a1 (mod m1 )x≡a2 (mod m2 )⋯x≡an (mod mn )这个方程组中x的值
注意普通中国剩余定理只适合求所有模数 mmm 都互质的情况，若不满足则需要使用扩展中国剩余定理，但考纲里没有，所以先不讲解
求解方法：
令M=m1×m2×⋯×mn令Mi=M÷mi（此时的Mi就是∏j=1且j≠inmj）求Mi在mod mi意义下的逆元此时x=∑i=1nai×Mi×Mi−1令 M=m_1\times m_2\times \cdots\times m_n\\ 令 M_i=M\div m_i（此时的M_i就是\prod_{j=1且j\neq i}^{n} m_j）\\ 求 M_i在mod~m_i意义下的逆元\\ 此时x=\sum_{i=1}^{n} a_i\times M_i\times M_i^{-1} 令M=m1 ×m2 ×⋯×mn 令Mi =M÷mi （此时的Mi 就是j=1且j=i∏n mj ）求Mi
在mod mi 意义下的逆元此时x=i=1∑n ai ×Mi ×Mi−1
注意编程题（或者普通题）中基本要求输出最小非负整数解
所以最终答案应该是
x mod Mx~mod~M x mod M
证明：
举个例子：x=a1×M1×M1−1+a2×M2×M2−1那么对于 x≡a1(mod m1)的意义下，有两种情况：第一种：当前就是a1×M1×M1−1，那么：M1M1−1，且逆元相乘模完=1，因此这部分=1第二种：当前不是a1×M1×M1−1，那么：a2×M2×M2−1这部分是包含m1的，如果 mod m1则这部分就是0最终这个式子就是a1×1+0=a1，满足第一个方程以此类推，可以证明对于所有方程，此算式均成立举个例子：x=a_1\times M_1\times M_1^{-1}+a_2\times M_2\times M_2^{-1}\\ 那么对于~x\equiv a_1(mod~m_1)
的意义下，有两种情况：\\ 第一种：当前就是a_1\times M_1\times M_1^{-1}，那么：\\ M_1 M_1^{-1}，且逆元相乘模完=1，因此这部分=1\\ 第二种：当前不是a_1\times M_1\times M_1^{-1}，那么：\\ a_2\times M_2\times M_2^{-1} 这部分是包含 m_1 的，如果 ~mod~m_1则这部分就是0\\ 最终这个式子就是a_1\times1+0=a_1，满足第一个方程\\ 以此类推，可以证明对于所有方程，此算式均成立 举个例子：x=a1 ×M1 ×M1−1 +a2 ×M2 ×M2−1 那么对于 x≡a1
(mod m1 )的意义下，有两种情况：第一种：当前就是a1 ×M1 ×M1−1 ，那么：M1 M1−1 ，且逆元相乘模完=1，因此这部分=1第二种：当前不是a1 ×M1 ×M1−1 ，那么：a2 ×M2 ×M2−1 这部分是包含m1 的，如果 mod m1 则这部分就是0最终这个式子就是a1 ×1+0=a1 ，满足第一个方程以此类推，可以证明对于所有方程，此算式均成立
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有问题，直接喷！非常接纳大家的建议！
版本4.3.3.1\huge{\orange 版 \purple 本} 4.3.3.1版本4.3.3.1
手工制作（无AI，全部为学习所得），制作不易，点个赞呗~
@AC君 求加精
