1. 群与环

交换群

设 $G$ 是一个非空集合， $x \in G,y \in G,x\oplus y$ 是一个二元运算。当下面的四个条件都成立时，则称 $G$ 是一个交换群

• 交换率: $ x \oplus y = y \oplus x, \forall x,y\in G$
• 结合律: $ (x \oplus y) \oplus z = x \oplus (y \oplus z), \forall x,y,z\in G$
• 单位元: $ \exists e, \forall x, x \oplus e = x $
• 可逆: $ \forall x, \exists y, x \oplus y = e, x = y^{-1} $

环

设 $R$ 是一个非空集合， $R$上定义了两个运算 $ \oplus $ 和 $ \otimes $，且符合下面三个条件，则称 $R$ 是一个$环$

• $(R,\oplus)$是一个交换群
• 结合律: $ (x \otimes y) \otimes z = x \otimes (y \otimes z), \forall x,y,z\in R$
• 分配律 $(\otimes \rightarrow \oplus)$: $(x \oplus y) \otimes z = x \otimes z \oplus y \otimes z $

2. 多项式相关

(同理，略)

3. 大整数快速乘法

Karatusuba

(1)将大数 $A$ 和大数 $B$ 进行10进制展开，低次补$0$

• $A= a_0+a_110^1+a_210^2+\cdots+a_m10^m$
• $B= b_0+b_110^1+b_210^2+\cdots+b_m10^m$

(2)大数 $A$ 和大数 $B$ 可以分成两个部分

• $A =(a_0+\cdots +a_{m/2}10^{m/2})+(a_{m/2+1}+\cdots +a_{m}10^{m/2-1})10^{m/2+1}$
• $B =(b_0+\cdots +b_{m/2}10^{m/2})+(b_{m/2+1}+\cdots +b_{m}10^{m/2-1})10^{m/2+1}$
• $A = A_0+A_110^{m/2+1} \quad B= B_0+B_110^{m/2+1}$

(3)$AB$可以拆分

• $AB=(A_0+A_110^{m/2+1})(B_0+B_110^{m/2+1})$
• $AB=A_0B_0+A_1B_110^{m/2+m/2+2}+(A_1B_0+A_0B_1)10^{m/2+1}$
• $(A_1B_0+A_0B_1)=(A_0+A_1)(B_0+B_1)-A_0B_0-A_1B_1$
• $AB=A_0B_0+A_1B_110^{m/2+m/2+2}+((A_0+A_1)(B_0+B_1)-A_0B_0-A_1B_1)10^{m/2+1}$

(4)递归，直到计算式中$A$和$B$仅包含一项（计算过程中除号向下取整）

FFT

待补充

DCT

待补充

4. 数论部分

基本概念

• $a$整除$b$: $a\vert b$，$b$是被除数，$a$是除数
• $a$被$b$整除: $b\vert a$，$b$是除数，$a$是被除数

基本性质

1. 传递性: 若 $a\vert b,b\vert c$，则 $a\vert c$
2. 线性组合: 若 $a\vert b,a\vert c$，则 $a\vert (q_0b+q_1c)$
3. 自整除: 若 $a\vert b,b\vert a$，则 $ a= \pm b $
4. 欧几里得除法: 设 $a,b$ 是两个整数，其中 $b>0$，存在唯一的整数 $p,r$ 使得 $a=bq+r,0\le r<b$
5. 多项式同理，多项式可类比成用$10$进制表示的整数

除法余数

• 完全剩余系：对于整数 $m$ 及一个整数集合$R$，当任意一个在$R$中的元素模$m$的结果唯一且$\vert R \vert $恰好为 $m$时，则称$R$是模$m$的完全剩余系

横重复平方计算法（快速幂）

• $y=(x^b)\%m, b=a_02^0+a_12^1+\dots+a_n2^n,a_i\in \lbrace 0,1 \rbrace$，后面相当于将 $b$ 二进制展开
• $y=(x^{a_02^0+a_12^1+\dots+a_n2^n})\%m$
• $y=(x^{a_02^0}\%m)\cdot(x^{a_12^1}\%m)\dots (x^{a_n2^n}\%m)$，显然当$a_i=0$时所在项为1，$a_i=1$时所在项为$x^{2^i}\%m$
• 上述的$n$项中，可以发现$x^{2^i}=x^{2^{i-1}}\cdot x^{2^{i-1}}$，通过$n-1$自乘运算，$\lbrace x^{2^0}\%m,x^{2^1}\%m,\cdots，x^{2^n}\%m \rbrace$将全部被计算出，再根据$a_i$的值考虑该项是否参与计算即可。

小步大步算法（Baby Step Giant Step）

目的在于求解 $y=g^x\%p$中$x$的值，下面过程忽略$(\%p)$符号

• $x = im+j$，通常的情况下$m=\sqrt{p}$最佳
• $y = g^{im+j}$
• $yg^{-j}=g^{im}$
• 枚举$yg^{-j}$中的$j$，枚举$g^{im}$中的$i$，计算出两列长度为$\sqrt{p}$的值表
• 最后找到两列中相同的值

欧几里得算法相关（最大公因子）

通常建立在模数为质数的情况下进行考虑，否则情况相对复杂且以下方法不完全成立

1. $0$ 与任何整数 $b$ 的最大公因子为 $b$:

   \[gcd(0,b) = b \tag{1}\]
2. 设$a,b,c$是三个不全为$0$的整数，如果 $a=qb+c$，其中$q$是整数，则$gcd(a,b)=gcd(b,c)$
   • $ d= gcd(a,b), d’=gcd(b,c)$，则 $d\vert a , d \vert b,d’ \vert b,d’ \vert c $
   • 基于整除的线性组合性质，因为 $d\vert a , d \vert b,c=a-qb$，所以$ d\vert (a-qb) \rightarrow d\vert c$
   • 由 $d\vert b,d\vert c $，可以得到$d$是$b,c$的公因子，但是不一定是最大的，可得$d\le d’$
   • 基于整除的线性组合性质，因为 $d’\vert b , d’ \vert c,a=qb+c$，所以 $ d’\vert (qb+c) \rightarrow d’\vert a$
   • 由 $d’\vert a,d’\vert b $，可以得到 $d’$ 是 $a,b$ 的公因子，但是不一定是最大的，可得$d’\le d$
   • 综上 $d = d’ $

3. 欧几里得算法求最大公因子，基于第 $2$ 点的结论:\(a=qb+c,gcd(a,b)=gcd(b,c)\)当求 $a,b(a>b)$ 两个整数的最大公因子时，由上式可以不断进行转移，下面说明 $a,b$ 的值在转移的过程中在不断减小。
   虽然$a=qb+c$中 $q,c$ 有多种符合情况的结果，但是 $0\le c<b$ 的情况有且仅有一种，而且此时恰好为 $q=\lfloor a/b \rfloor,c=a\%b$，并且有$(a>b>c)$，显然可行，最终将出现 $a=x,b=0$ 的情况，此时的$x$即为最大公因子。

4. 复杂度为log级别，复杂度证明(待补充)。

5. 扩展欧几里得算法，求 $pa+qb=gcd(a,b)$ 中的$p$和$q$，基于第$3$点的求解过程，假设 $0$ 下标表示的为上层，$1$ 下标为下层，即

   \[b_0=a_1，c_0=b_1,a_0=p_0b_0+c_0 \rightarrow a_1=p_1b_1+c_1\]

• 正向计算：第$i$层传递$a_i,b_i$的同时包含四个参数 $x_a,y_a,x_b,y_b $，其含义为$a_i=x_aa+y_bb$, $b_i=x_ba+y_bb$，其中的 $a,b$ 即为最开始输入的 $a,b$ 值，通过不断这样的线性表示，即得到最后最大公因子的表示方法。

• 回溯计算：第$i$层传递$a_i,b_i$的同时包含两个参数 $ x,y $，区别在于该参数在往回传输，其含义为 $xa_i+yb_i=gcd(a,b)$，在回传的过程中不断通过线性变化更新$x,y$，即可以得到最初的 $x_0,y_0$，即 $p,q$。具体过程如下面公式$(1)-(6)$，除法为整除。

  \[\begin{cases} a_0=p_0b_0+c_0 \\ a_1=p_1b_1+c_1 \\ a_1=b_0,b_1=c_0=a_0-\frac {a_0}{b_0}b_0 \\ x_0a_0+y_0b_0=x_1a_1+y_1b_1=gcd \end{cases} \tag{1}\] \[x_0a_0+y_0b_0=x_1a_1+y_1b_1=gcd \tag{2}\] \[x_0a_0+y_0b_0=x_1b_0+y_1(a_0-\frac {a_0}{b_0}b_0) \tag{3}\] \[a_0(x_0-y_1)+b_0(y_0-x_1+y_1\frac {a_0}{b_0})=0 \tag{4}\] \[make :x_0-y_1=0,y_0-x1+y_1\frac {a_0}{b_0}=0 \tag{5}\] \[then :x_0=y_1,y_0=x1-y_1\frac {a_0}{b_0} \tag{6}\]

1. 模逆(求逆元)，在取模的计算中，假如需要计算$\frac ab$，相当于计算$a\cdot b^{-1}$，$b$和$b^{-1}$互为逆元，简单来说就是$b\cdot b^{-1}=1 \rightarrow \frac 1b=b^{-1}$。
   • 费马小定理: $a^{p-1}=1(mod\space p)$，简单可得$a\cdot a^{p-2}=1(mod\space p)$
   • 扩欧: $ax=1(mod\space p)\rightarrow ax+py=1(mod\space p) $，解出 $x$ 即可
2. $a,b$ 互质，$ax+by=1$有解
   • 充分：$d=gcd(a,b)$，$d\vert a,d\vert b$，$d\vert (ax+by=1)$，$d=1$
   • 必要：假设$gcd(a,b)=d\neq1$，$a=pd,b=qd$，$ax+by=pdx+qdy=d(px+dy)$，$d(px+dy)\neq 1$，故$gcd(a,b)=1$