## 质数/素数
$\pi(x)$ 表示 $\le x$ 的素数个数。随着 $x$ 增大，会有 $\pi(x) \sim \frac{x}{\ln(x)}$。
### 素数判定
1. 枚举 $1\sim n$ 的每一个数，看看能不能被整除。
```cpp
bool isprime(int n){
if(n < 2) return 0;
for (int i = 2;i < n;i++) {
if(n % i == 0) return 0;
}
return 1;
}
```
2. 优化一下，我们发现，当 $x | n$ 时，有 $\frac{n}{x}|n$，所以，我们只需枚举到 $\sqrt{n}$ 即可。
```cpp
bool isprime(int n){
if(n < 2) return 0;
for (int i = 2;i * i <= n;i++) {
if(n % i == 0) return 0;
}
return 1;
}
```
3. 质数筛
一般的筛法，遇到质数 $x$ 把每一个 $kx$ 筛成合数，并且保证 $1\sim n$ 的每一个数都只筛一遍，时间复杂度就是 $\theta(n)$ 了。
```cpp
vector<int> pri;
bool not_prime[N];
void pre(int n) {
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
pri.push_back(i);
}
for (int pri_j : pri) {
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0) {
// i % pri_j == 0
// 换言之，i 之前被 pri_j 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
// pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
// 掉就好了
break;
}
}
}
}
```
## 最大公约数/最大公因数
### 前言
直讲做法 & 简单证明，详细证明会给出网址。
### 定义
rt。
### 求 gcd
先上 `STL` 做法。
```cpp
long long gcd (int x, int y) {
return __gcd(x, y);
}
```
辗转相除法。
通过证明得到 $\gcd (a, b) = \gcd(b,a \% b)$。
证明详见 [oi-wiki 最大公约数](https://oi-wiki.org/math/number-theory/gcd/)。
于是就有：
```cpp
int gcd (int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
```
更相减损术。
通过证明得到 $\gcd(a,b) = \gcd(b,a-b)$。
于是就有：
```cpp
int gcd (int a, int b) {
if (b == 0) return a;
return gcd(b, a - b);
}
```
例题：[高精度最大公约数](https://loj.ac/p/10205)，[最大公约数](https://www.luogu.com.cn/problem/B3736)。
### 最小公倍数
易证 $\text{lcm}(a, b) = \Large\frac{ab}{\gcd{a,b}}$。
```cpp
int lcm (int a, int b) {
return a * b / gcd(a, b);
}
```
## gcd 有关的问题
### 裴蜀定理 Bézout's lemma
#### 内容
若有不为 $0$ 的整数 $a,b, x, y$，满足 $\gcd(a, b)|ax + by$。若已知 $a,b$，必有 $ax+by = \gcd(a,b)$。
#### 证明
详见 [oi-wiki 裴蜀定理](https://oi-wiki.org/math/number-theory/bezouts/)。
### 费马小定理 fermat
#### 内容
若 $p$ 为质数，$\gcd(a,p) = 1$，有 $a^{p-1} \equiv 1\space (\bmod \space p)$。
#### 证明
详见 [oi-wiki 欧拉定理 & 费马小定理](https://oi-wiki.org/math/number-theory/fermat/)。
## 扩展欧几里得 exgcd
由裴蜀定理得到：
$ax + by = \gcd(a,b)$，现在已知 $a,b$，求 $x,y$。
### 过程
有 $ax_1+by_1=\gcd(a,b)bx_2 + (a \bmod b)y_2 = \gcd(b, a\bmod b)
\because \gcd(a,b) = \gcd(b, a \bmod b)
\therefore ax_1 + by_1 = bx_2 + (a \bmod b)y_2
\because a \bmod b = a-(\lfloor\frac{a}{b}\rfloor \times b)
\therefore ax_1+by_1 = bx_2 + (a-(\lfloor\frac{a}{b}\rfloor \times b))y_2
ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor \times by_2 = ay_2 + b(x_2 - \lfloor\frac{a}{b}\rfloor y_2)
\therefore x_1 = y_2, y_1 = x_2 - \lfloor\frac{a}{b}\rfloor y_2
最后，不断递归求解答案即可。
int Exgcd(int a, int b, int &x, int &y) {// from oi-wiki
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;// t = x1
x = y;// x1 = y2
y = t - (a / b) * y;// y1 = x2 - a/b * y2
return d;
}
exgcd 求同余方程
形如
ax \equiv b\space (\bmod \space n)
的方程被称为 线性同余方程。
定理
```cpp
int ex_gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = ex_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - a / b * y;
return d;
}
bool liEu(int a, int b, int c, int& x, int& y) {
int d = ex_gcd(a, b, x, y);
if (c % d != 0) return 0;
int k = c / d;
x *= k;
y *= k;
return 1;
}
```
## 乘法逆元
### 定义
如果一个线性同余方程 $ax \equiv 1\space (\bmod\space b)$，已知 $a,b$，称 $x$ 是 $a \mod b$ 的逆元。记作 $a^{-1}$。
### exgcd 求法
我们知道 exgcd 如何求 **线性同余方程**，于是可以带入进来。
### 快速幂求法
$$
\because ax \equiv 1\space(\bmod \space b)
$$
$$
\therefore ax \equiv a^{b-1}(\bmod \space b)_{\text{费马小定理}}
$$
$$
\therefore x \equiv a^{b-2}(\bmod \space b)
$$
使用快速幂求即可。
### 例题
[乘法逆元](https://loj.ac/p/110)
[乘法逆元 2](https://loj.ac/p/161)
***
至此，数论基础已经初步完成。
证明+资料出自 [oi-wiki](https://oi-wiki.org/)。
# 组合数学