## **1、费马小定理**
- 若存在整数 $a , p$ 且gcd(a,p)=1,即二者互质，则有$a^{p-1} ≡ 1$ $(\, mod \: p)$ 。
- (这里的 ≡ 指的是恒等于，$a^{p-1} ≡ 1$ $(\, mod \: p)$ 是指$a$的$(p-1)$次幂取模$p$与$1$取模$p$恒等)

### 费马小定理的两种等价形式
- 基本形式：若p为素数，a为任意整数则$a^p ≡ a$ $(\, mod \: p)$
- 常用形式：若$a$与$p$互质，则$a^{p-1} ≡ 1$ $(\, mod \: p)$


## **2、容斥原理**
![](/file/2/76marYmxrx6OnUK4EkGGh.png)


## **3、乘法逆元**
![](https://buersn.top/p/957/file/50F0wNAF0FCP94mvpcBeb.png)

同时：
若整数 $b，m $互质，并且对于任意的整数 $a$，如果满足 $b|a$($b$能整除$a$)，则存在一个整数 $x$，使得 $\frac{a}{b}≡a × x(mod$   m)，则称$ x $为$ b$ 的模 $m$ 乘法逆元，记为 $b^{−1}$(mod  m)。

$b$ 存在乘法逆元的充要条件是 $b $与模数 $m$ 互质。**当模数 $m$ 为质数时，$b^{m−2}$ 即为 $b$ 的乘法逆元。**


## **4、整数唯一分解定理**
整数唯一分解定理：亦称算术基本定理，是数论的重要定理之一。

**该定理断言：任何一个大于1的整数n都可以分解成若干个素因数的连乘积，如果不计各个素因数的顺序，那么这种分解是惟一的，即若n>1，则有:**
- (1) $n = p_1*p_2*…*p_m$;

其中$p_1≤p_2≤…≤p_m$皆素数，上式常简记为:
- (2) $n = p_1^{a_1} * p_2^{a_2} * ...* p_k^{a_k}$

其中，$p_1<p_2<…<p_k$皆素数，$a_i(i=1，2，…，k)$皆正整数. (2) 式称为n的标准分解式，又称为质因数分解式、素数幂分解式等，若(2)式成立，则n的任一正因数d都可表示成:
- (3) $d = p_1^{b_1} * p_2^{b_2} * ...* p_k^{b_k}$

其中$a_i≥b_i≥0 (i=1，2，…，k)$.

**标准分解式的应用： 利用标准分解式(可查素数幂分解表)容易写出任二正整数的最大公因数。**

即若有$n = p_1^{a_1} * p_2^{a_2} * ...* p_k^{a_k}$，$m = p_1^{b_1} * p_2^{b_2} * ...* p_k^{b_k}$. 其中$a_i≥0,b_i≥0$。则$m,n$的最大公约数$gcd(m,n) = p_1^{r_1} * p_2^{r_2} * ...* p_k^{r_k}$. 其中$r_i = min(a_i,b_i)(i=1，2，…，k)$

## **5.埃氏筛**
```cpp
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n;
bool sieve[N]; // true被筛选过，false未被筛选过 
int main(){
	scanf("%d", &n);
	sieve[0] = true; // 被筛选过 
	sieve[1] = true; // 被筛选过 
	for(int i = 2; i * i <= n; i++){
		if(!sieve[i]){ // i没有被筛选过，则说明i是素数 
			for(int j = i*i; j <= n; j += i){
				sieve[j] = true;
			} 
		}
	}
	for(int i = 0; i <= n; i++){
		if(!sieve[i]) printf("%d ", i);
	} 
	return 0;
}

```

## **6.欧拉筛（线性筛）**

```cpp
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n, ans = 0;
bool sieve[N];
int prime[N];
int main(){
	scanf("%d", &n);
	sieve[0] = true; // 筛选过
	sieve[1] = true; // 筛选
	for(int i = 2; i <= n; i++){
		if(!sieve[i]) prime[ans++] = i;// i是素数，加入数组prime
		for(int j = 0; j < ans; j++){
			if(prime[j] * i > n) break; // 如果超出n，就没必要筛选了 
			sieve[prime[j] * i] = true;
			// 如果i是prime[j]的倍数，则i一定可以表示成prime[j]*k的模式
			// 也就是，i*prime[j]早就被i的质因子prime[j]筛选过了 
			if(i % prime[j] == 0) break;
		} 
	} 
	for(int i = 0; i < ans; i++){
		printf("%d ", prime[i]);
	} 
	return 0;
}

```