CSP-S 数学讲解

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-08-11 10:37:27

发布于：北京

57阅读

0回复

0点赞

本篇只讲解大部分提高组考纲内的数论，主要目的为自我分析与积累学习。部分数学会有代码

1 矩阵

接下来的 $A$ 和 $B$ 都分别代表矩阵

1.1 矩阵的概念

矩阵是行和列排列的数表。 $n$ 行 $m$ 列的矩阵称为 $n\times m$ 矩阵。
${A_i}_j$ 表示第 $i$ 行，第 $j$ 列的元素。

1.2 特殊的矩阵

方阵： $n=m$ 的矩阵
零矩阵：所有元素都是 $0$ 的矩阵
单位矩阵：主对角线都是 $1$ ，其它位置都是 $0$ 的矩阵
对角矩阵：除主对角线外（主对角线可以随意），其它位置都是 $0$ 的矩阵。单位矩阵是特殊的对角矩阵

1.3 矩阵的转置

简单来说，就是 $行 \rightarrow 列,列 \rightarrow 行$
将矩阵加一个 $^T$ ，表示转置

$\begin{bmatrix} 1,2,3 \\ 4,5,6 \end{bmatrix}^T \rightarrow \begin{bmatrix} 1,2 \\ 3,4 \\ 5,6 \end{bmatrix}$

1.4 矩阵的加法

矩阵加法的前提：同型矩阵（ $A的n=B的n且A的m=B的m$ ）

${(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}$

矩阵加法满足交换律与结合律

1.5 矩阵的乘法

矩阵乘法的前提： $A 为 n \times m,B为m\times p$ ，矩阵乘法后的结果大小为 $n\times p$

${(AB)_i}_j=\sum_{k=1}^{n} {A_i}_k{B_k}_j$

也就是用 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列相乘后求和。

$比如 \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列的值\\ 然后以此类推，可以得到结果$

矩阵乘法满足结合律和分配律，但一般不满足交换律
代码实现也很简单，时间复杂度 $O(n^3)$

1.6 矩阵快速幂

拿斐波那契数列举例子
朴素递归实现 $O(2^n)$ ，递推/记忆化搜索 $O(n)$ ，但是这样对于 $n\ge 10^{9}$ 会超时
而矩阵快速幂可以在 $O(log~n)$ 的时间复杂度内解决
原理是通过矩阵乘法

$先构造一个矩阵\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.7 由递推式子构造转移矩阵完整步骤

感谢@Xylophone的建议

1.7.1 第一步：写出线性递推公式

要求只能是常系数线性递推公式（无常数项、无平方项）
咱们这次换个复杂的例子 $f_n=2f_{n-1}+f_{n-2}+1（n\ge3）$

1.7.2 第二步：构造状态列向量 $\vec{F_n}$

向量里放递推需要用到的最近若干项，项数 = 递推阶数
这里是 $3$ 阶递推，向量长度 $= 3$
我们希望：

$\begin{bmatrix} f_n\\f_{n-1}\\1 \end{bmatrix}=T\begin{bmatrix} f_{n-1}\\f_{n-2}\\1 \end{bmatrix}$

1.7.3 第三步：推导矩阵 $T$

拆开左边：
$\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}\\$
于是构造如下矩阵 $T$ :

$T=\begin{bmatrix} 2,1,1\\1,0,0\\0,0,1 \end{bmatrix}$

2 筛法

2.1 埃氏筛

从小到大枚举，未标记数为质数，从 $p^2$ 开始标记其倍数
时间复杂度 $O(n~log~log~n)$
代码：

bool is_prime[N];
void prime(int n){
	memset(is_prime,true,sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	for(int i = 2;i * i <= n;i ++){
		if(is_prime[i]){
			for(int j = i * i;j <= n;j += i){
				is_prime[j] = false;
			}
		}
	}
}

2.2 线性筛

使用已找到的质数筛去合数，每个合数只由最小质因子筛一次
时间复杂度 $O(n)$
代码：

int prime[N];
int cnt;
void prime(int n){
	memset(is_prime,true,sizeof(is_prime));
	cnt = 0;
	is_prime[0] = is_prime[1] = false;
	for(int i = 2;i <= n;i ++){
		if(is_prime[i]){
			prime[++ cnt] = i;
		}
		for(int j = 1;j <= cnt;j ++){
			int p = prime[j];
			if(1LL * i * p > n) break;
			is_prime[i * p] = false;
			if(i % p == 0) break;
		}
	}
}

3 欧拉函数

$φ(n)$ 代表： $\le n$ 且和 $n$ 互质的正整数一共有多少个
$比如~φ(6)=2\rightarrow 1和5,φ(5)=4\rightarrow 1,2,3,4$

规律1：如果 $p$ 是质数，则 $φ(p)=p-1$
规律2： $φ(1)=1$
规律3：如果 $p$ 为质数，则 $p$ 的幂 $p^k$ 有 $φ(p^k)=p^k-p^{k-1}$

3.1 计算方式

把 $n$ 拆成质数相乘： $n={p_1}^{k_1}\times{p_2}^{k_2}\times\cdots\times{p_n}^{k_n }$
然后就是 $n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_n})$

$φ(n)=n\prod_{i=1}^{k(n的不同质因子个数)} (1-\frac{1}{p_i})$

3.2 实现代码（线性筛+递推）

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int phi[N];// φ函数第i项的值
vector<int> primes;
bool vis[N];

void get_phi(int n) {
    phi[1] = 1;// φ(1)=1
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            primes.push_back(i);
            phi[i] = i - 1; //质数φ(p)=p‑1
        }
        for (int p : primes) {
            if (1LL * i * p > n) break;
            vis[i * p] = true;
            if (i % p == 0) {
                /*
                p是i的最小质因子，i包含p
                那么后面乘的都一样，只有刚开始乘的i需要再额外乘p
                */
                phi[i * p] = phi[i] * p;
                break;
            } else {
                /*
                i与p互质 φ(i*p)=φ(i)*φ(p)
                说明需要乘一个1-(1/p)，也就是乘一个p-1
                */
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
}

int main() {
    get_phi(100);
    cout << phi[6] << endl; //输出2
    cout << phi[8] << endl; //输出4
    return 0;
}

3.3 欧拉定理

同余符号为 $\equiv$ ，如果 $a$ 与 $b$ 除以正整数 $m$ 的余数相同，记作 $a\equiv b(mod~m)$

若 $gcd(a,n)=1$ 则：

$a^{φ(n)}\equiv1(mod~n)\\ a^{-1}\equiv a^{φ(n)-1}(mod~n)$

3.3.1 欧拉定理的扩展 $\rightarrow$ 费马小定理

若 $n$ 为质数，则 $φ(n)=n-1$
那么

$a^{n-1}\equiv1(mod~n) \rightarrow 费马小定理$

3.4 （扩展）有关约数的计算

3.4.1 约数个数

$(a_1+1)\times(a_2+1)\times\cdots\times(a_n+1)$

3.4.2 约数之和

$(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})$

4 乘法逆元

4.1 定义

若 $ax\equiv1(mod~m)$ ，则 $x$ 是 $a~mod~m$ 的乘法逆元
逆元存在的条件为： $gcd(a,m)=1$
在这种情况下， $a^{-1}$ 代表 $a$ 的逆元

4.2 逆元的帮助

一般来说，除法是无法“边除边模”的

$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)$

但是通过这样的计算，就可以把除法转化为乘法，从而使得除法也可以“边除边模”

4.3 逆元的常用计算方式

4.3.1 当 $m$ 为质数时，可以使用费马小定理

$a^{φ(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}$

4.3.2 当 $m$ 不为质数，无法使用费马小定理，因此可以使用扩展欧几里得

4.3.2.1 前置知识：裴蜀定理

裴蜀定理：对于任意正整数 $a,b$ ，一定存在非零整数 $x,y$ ，使得 $ax+by=gcd(a,b)$

4.3.2.2 前置知识：欧几里得算法

欧几里得算法： $gcd(a,b)=gcd(b,a~mod~b)~~~~~~~~~~b=0时gcd(a,b)=a$

4.3.2.3 扩展欧几里得算法

先是根据裴蜀定理得到 $x$ 和 $y$

int gcd(int a, int b, int &x, int &y){
    if (b == 0){
        x = 1, y = 0;
        // ax+0=gcd(a,b)=a;这样x=1,y=任何数都可以满足裴蜀定理
        return a;
    }
    int d = gcd(b, a % b, y, x);
    // 因为可以看成b的系数是y，a%b的系数是x，因此x和y的参数位置也要调换}

然后这里引入一个算式：

$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)$

继续代码：

int gcd(int a, int b, int &x, int &y){
    if (b == 0){
        x = 1, y = 0;
        // ax+0=gcd(a,b)=a;这样x=1,y=任何数都可以满足裴蜀定理
        return a;
    }
    int d = gcd(b, a % b, y, x);
    // 因为可以看成b的系数是y，a%b的系数是x，因此x和y的参数位置也要调换}
    y -= a / b * x;
    return d;
}

这样就能计算出 $x$ 和 $y$ 的值了
然后我们回到逆元 $ax\equiv1(mod~m)$
对比两个式子： $ax\equiv1(mod~m)~~~~~~~~~~ax+by=gcd(a,b)$
当 $b=m$ 时， $ax+my=gcd(a,m)$
既然逆元的存在条件是 $gcd(a,m)=1$ ，那么可以得到 $ax+my=1$
然后 $my$ 这部分在 $mod~m$ 的情况下为 $0$ ，因此 $ax\equiv1(mod~m)$
所以扩展欧几里得算法计算完毕后，得到的 $x$ 就是 $a$ 的逆元

5 中国剩余定理

中国剩余定理用于求形如：

$x\equiv a_1(mod~m_1)\\ x\equiv a_2(mod~m_2)\\ \cdots\\ x\equiv a_n(mod~m_n)\\ 这个方程组中x的值$

求解方法：

$令 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 的逆元，这里是M_i在mod~m_i意义下的逆元\\ 此时x=\sum_{i=1}^{n} a_i\times M_i\times M_i^{-1}$

证明：

$举个例子：x=a_1\times M_1\times M_i^{-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，满足第一个方程\\ 以此类推，可以证明对于所有方程，此算式均成立$

有问题，直接喷！非常接纳大家的建议！

$\huge{\orange 版 \purple 本} 2.0.1$

手工制作（无AI，全部为学习所得），制作不易，点个赞呗~

@AC君求加精

有帮助，赞一个

去预览

0/2000

全部评论 9

Lin.Zikang
@AC君，强烈建议设为精华！

1周前来自浙江
1
- 科技起源‍‍‍‍‍‍‍‍‍‍‍‍
  回复
  Lin.Zikang
  o(￣︶￣)o
  
  1周前来自北京
  0
Eucatastrophe‌
似乎只是基础没有例题？

1周前来自浙江
1
- 科技起源‍‍‍‍‍‍‍‍‍‍‍‍
  回复
  Eucatastrophe‌
  等我找时间加上
  
  1周前来自北京
  0
Xylophone
怎么被 oiwiki 和洛谷专栏包含了

1周前来自广东
1
Xylophone
你强强。但是矩阵加速怎么从转移方程推出原矩阵你怎么不讲。真成背书比赛了。

1周前来自广东
1
科技起源‍‍‍‍‍‍‍‍‍‍‍‍
d

昨天来自天津
0
科技起源‍‍‍‍‍‍‍‍‍‍‍‍
d

6天前来自北京
0
凡·普·孤
看不懂@_@

1周前来自浙江
0
科技起源‍‍‍‍‍‍‍‍‍‍‍‍
d

1周前来自甘肃
0
TQjc
沙发

2026-08-05 来自湖北
0
- 科技起源‍‍‍‍‍‍‍‍‍‍‍‍
  回复
  TQjc
  椅子
  
  1周前来自甘肃
  0