本原勾股数

每个本原勾股数组$(a,b,c)$（其中a为奇数b为偶数）都满足

$$a=st \quad b=\frac {s^2-t^2}{2} \quad c=\frac {s^2+t^2}{2} \quad (s > t \ge 1 \; and \; gcd(s,t)=1 \; and \; s,t为奇数)$$

恒等式

$$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$$

线性筛

以筛质数为例

Miller–Rabin素数测试

测试$N$是否为素数，记$2^s d=N-1$

对$a \in [1,N-1]$且$a \nmid n$

若$a^d \mod N \neq 1$且$a^{2^{r}d} \mod N \neq -1 \quad (r \in [0, s-1])$

则N是合数

否则，N有3/4的概率为素数

Pollard_rho质因素分解

费马大定理

当$n \ge 3$时方程

$$a^n+b^n=c^n$$

没有正整数解

费马小定理

$$\quad a^{p-1} \equiv  1 \pmod{p}$$

变式：（前提$gcd(a,n)=1$）

$$a^{\varphi(n)} \equiv 1 \pmod n \quad（欧拉定理）$$

威尔逊定理

$$(p-1)! \equiv -1 \pmod p$$

乘法逆元

①数$a$在$\pmod p$意义下的逆元为$a^{p-2}$

②数$a$在$\pmod n$意义下的逆元需要通过Exgcd求解（有可能不存在逆元）

中国剩余定理（CRT）

解方程组$x \equiv a_i(mod\;m_i)$，其中$m_i$两两互质

解法：

令

$$M_i=\prod_{j \not = i}m_j$$

解

$$M_ip_ia_i \equiv a_i \quad \Rightarrow \quad M_ip_i \equiv 1\pmod{m_i}$$

所有$p_i$解完累加起来，$\sum M_ip_ia_i \pmod{M}$就是答案了

欧几里德算法

扩展欧几里德算法

解线性方程$Ax+By=gcd(A,B)$

在求gcd的基础上加上求x和y

原理：$By+(A\;mod\;B)x \Rightarrow B(y-A/B*B*x/B)+Ax \Rightarrow Ax+B(y-A/B*x)$

线性同余方程

求$Ax \equiv B \pmod p$解

解法：

设$d=gcd(A,p)$，先用Exgcd求$Ax+py=d$的解

由线性同余式定理可得，如果B不能整除d则无解

否则$mod\;p$意义下的解有d个，可以对某个解不断增加$p/d$得到

多解证明：

$$\frac{Ap}{d=gcd(A,p)}=lcm(A,p) \equiv 0 \pmod p$$

Gray码

性质：一个$0\rightarrow2^n-1$的排列且相邻两项（包括头尾相邻）的二进制数中只有一位不同

高阶代数方程求根

数值积分

AKS素数测试