前言

开个大坑。

正文

取模运算性质
- $(a+b) \bmod p=((a \bmod p)+(b \mod p)) \mod p$ ，反之亦成立。
- $(a-b) \bmod p=((a \bmod p)-(b \mod p)) \mod p$ ，反之亦成立。
- $(a \times b) \bmod p=((a \bmod p) \times (b \mod p)) \mod p$ ，反之亦成立。
- 引流两篇讲解负数取模的文章 link1 link2
若 $\forall a,b \in \mathbb{N}$ ，则 $\gcd (a,b) \times \operatorname{lcm} (a,b)=a \times b$ 。
九章算术·更相减损术
- 若 $\forall a,b \in \mathbb{N},a \le b$ ，则 $\gcd (a,b)= \gcd (a,b-a)= \gcd (b,b-a)$ 。
  - 证明：设 $d= \gcd (a,b),k_1= \frac{a}{d},k_2= \frac{b}{d}$ ，移项得 $a=k_1 d,b=k_2 d$ ，又因为 $(b-a) \bmod d=0,b-a=(k_2-k_1)d$ ，故 $\gcd (a,b-a)= \gcd (k_1 d,(k_2-k_1)d)=d $ ，$b$ 与 $b-a$ 同理。
- 若 $\forall a,b \in \mathbb{N}$ ，则 $\gcd (2a,2b)= 2\gcd (a,b)$ 。
欧几里得算法
- 若 $\forall a,b \in \mathbb{N}$ ，则 $\gcd (a,b)= \gcd(b,a \bmod b)$ 。
  - 证明
    - 若 $a<b $ ，则 $\gcd(b,a \bmod b)=\gcd(b,a)=\gcd(a,b)$ 。
    - 若 $a \ge b$ ，设 $ d= \gcd(a,b),a=q \times b+r(0 \le r <b)$ ，则 $r=a \bmod b=a-q \times b$ ，又因为 $ d|a,d|b,d|(q \times b) $ ，则 $d|(a-q \times b)$ ，即 $d|r$ ，故 $\gcd(a,b)=\gcd(b,r)=\gcd(b,a \bmod b)$ 。
- 时间复杂度为 $O(log(a+b))$ 。
- 代码实现
```
int gcd(int a,int b){return b ? gcd(b,a % b) : a;}
```