From ae9e9d2161741c2d6eb90f07206fff345b5f07bb Mon Sep 17 00:00:00 2001
From: sshwy <jy.cat@qq.com>
Date: Thu, 18 Jul 2019 09:26:49 +0800
Subject: [PATCH] =?utf8?q?=E8=A1=A5=E5=85=85=E6=95=B0=E5=AD=A6=E9=83=A8?=
 =?utf8?q?=E5=88=86=E7=AE=80=E4=BB=8B=EF=BC=8C=E6=B7=BB=E5=8A=A0=E5=B8=B8?=
 =?utf8?q?=E7=94=A8=E7=AC=A6=E5=8F=B7=E4=BB=8B=E7=BB=8D?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/math/index.md | 77 ++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 60 insertions(+), 17 deletions(-)

diff --git a/docs/math/index.md b/docs/math/index.md
index 0c178fa8..2311315c 100644
--- a/docs/math/index.md
+++ b/docs/math/index.md
@@ -10,28 +10,31 @@
 
 * * *
 
-### 以下是你可以在本部分找到的知识（部分未完成，待补充）
-
-1.  进制相关
-2.  位运算——二进制下的按位运算
-3.  高精度——当语言变量类型不足以表达需要表达的数时的处理方法
-4.  整除性质（数论）
-5.  同余相关（数论）
-6.  高斯消元（矩阵/概率期望）
-7.  数论反演
-8.  杜教筛/洲阁筛
-9.  多项式（FFT, NTT, FWT, 拉格朗日插值）
-10. 排列组合 (Lucas, Catalan)
-11. 概率与期望
-12. 置换
-13. 线性规划
-14. 线性基
+## 以下是你可以在本部分找到的知识（部分未完成，待补充）
+
+1.  进制：多种进制的介绍与互相转化。
+2.  位运算：二进制下的按位运算（与、或、非等）。
+3.  高精度：当数字过大，语言变量类型不足以存储时的处理方法。
+4.  整除：质数、最大公约数、欧拉函数与欧拉定理、（类）欧几里德算法。
+5.  同余：裴蜀定理、逆元、中国剩余定理、大步小步（BSGS）算法、阶与原根。
+6.  线性代数基础：矩阵、高斯消元（矩阵/概率期望）、线性基。
+7.  复数与复平面
+8.  数论反演：主要有莫比乌斯反演。
+9.  筛法：埃氏筛、欧拉筛（线性筛）、杜教筛/洲阁筛。
+10.  多项式：快速傅里叶变换（FFT）、快速数论变换（NTT），拉格朗日插值、多项式的各种变换。
+11.  组合数学：排列组合、卡特兰数、斯特林数、康托展开、容斥原理、抽屉原理。
+12.  概率与期望
+13.  置换
+14.  线性规划
+15.  单纯形算法
+16.  博奕论算法
+17.  其他算法
 
 * * *
 
 OI 中的数学以高中，大学的数学为基础，考察选手对数学知识的掌握，利用计算机的计算能力来解决问题。
 
-### NOIP 中有可能会考察的知识点
+## NOIP 中有可能会考察的知识点
 
 然而 NOIP 可能考察更多的知识点，这里只是利用之前的题总结出来的，考过或者考的概率比较大的知识点。
 
@@ -44,3 +47,43 @@ NOIP 对数学的考察还处在一个比较简单的范围。
 5.  同余相关—— $exgcd$ ，逆元，中国剩余定理
 6.  概率期望——概率 DP，以及有可能用到高斯消元解决的概率 DP
 7.  排列组合——杨辉三角，二项式定理，卢卡斯定理，卡特兰数
+
+## 常见符号
+
+在学习数论的过程中大家会见到许多复杂的公式符号。因此在学习具体内容之前，建议大家首先理解下列常见符号的含义。一些特殊的符号会在对应的章节中讲到，而这里则有一些极为常见的符号需要大家提前掌握。
+
+### 复杂度函数
+
+1. 大 $\text{O}$ 符号：当且仅当存在正实数 $M$ 和实数 $x_0$，使得 $\forall x\geq x_0,\ |f(x)|\leq M|g(x)|$ ，我们就可以认为，$f(x)=O(g(x))$。
+2. 大 $\Omega$ 符号：当且仅当存在正实数 $M$ 和实数 $x_0$，使得 $\forall x\geq  x_0,\ f(x)\geq Mg(x)$ ，我们就可以认为，$f(x)=\Omega (g(x))$. 大 $\text{O}$ 与大 $\Omega$ 恰好相反，即 $f(x)=\text{O}(g(x))\Leftrightarrow g(x)=\Omega(f(x))$。
+3. 大 $\Theta$ 符号：大 $\Theta$ 符号是大 $\text{O}$ 和大 $\Omega$ 的结合，即 $f(x)=\text{O}(g(x))\wedge f(x)=\Omega(g(x))\ \Rightarrow f(x)=\Theta(g(x))$。
+
+### 整除/同余理论常见符号
+
+1. 整除符号：$x\mid y$，表示$x$整除$y$，即$x$是$y$的因数。
+2. 取模符号：$x\bmod y$，表示$x$除以$y$得到的余数。
+3. 互质符号：$x\perp y$，表示 x,y 互质。
+4. 最小公倍数：$\gcd(x,y)$，在无混淆意义的时侯可以写作 $(x,y)$。
+5. 最大公约数：$\operatorname{lcm}(x,y)$，在无混淆意义的时侯可以写作 $[x,y]$。
+
+### 数论函数常见符号
+
+求和符号：$\sum$符号，表示满足特定条件的数的和。举几个例子：
+
+- $\sum_{i=1}^ni$ 表示$1+2+\cdots+n$的和。其中$i$是一个变量，在求和符号的意义下$i$通常是**正整数或者非负整数**（除非特殊说明）。这个式子的含义可以理解为，$i$从$1$循环到$n$，所有$i$的和。这个式子用代码的形式很容易表达。当然，学过简单的组合数学的同学都知道$\sum_{i=1}^n=\frac{n(n+1)}{2}$。
+- $\sum_{S\subseteq T}|S|$表示所有被$T$包含的集合的大小的和。
+- $\sum_{p\le n,p\perp n}1$ 表示的是$n$以内有多少个与$n$互质的数，即$\varphi(n)$，$\varphi$是欧拉函数。
+
+求积符号：$\prod$ 符号，表示满足特定条件的数的积。举几个例子：
+
+- $\prod_{i=1}^ni$表示$n$的阶乘，即$n!$。在组合数学常见符号中会讲到。
+- $\prod_{i=1}^na_i$表示$a_1\times a_2\times a_3\times \cdots\times a_n$的积。
+- $\prod_{x|d}x$表示$d$的所有因数的乘积。
+
+在行间公式中，求和符号与求积符号的上下条件会放到符号的上面和下面，这一点要注意。
+
+### 其他常见符号
+
+1. 阶乘符号 $!$，$n!$ 表示 $1\times 2\times 3\times \cdots\times n$。
+
+另外，还请大家学好高一数学，这样学习数论的时侯会省很多功夫。
\ No newline at end of file
-- 
2.11.0