一、质数
二、约数
三、欧拉函数
四、快速幂
五、扩展欧几里得算法
六、中国剩余定理
七、高斯消元
八、组合计数
九、容斥原理
十、简单博弈论

一、质数

质数：在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数

（一）质数的判定——试除法

1、sqrt(x)
时间复杂度O（n½）
sqrt(x)这个函数执行的比较慢，所以不推荐

bool is_prime(int x) 
{
    
    // 1、质数大于1
    if(x < 2) return false;
    for(int i = 2; i <= sqrt(x); i++) 
    {
    
        if(x % i == 0) // 2、只包含1和本身这两个约数
        	return false;	
     }
    return true; 
}

2、推荐此方法i ≤ n / i
核心：i <= x / i可以有效提高性能

bool is_prime(int x) 
{
    
    // 质数大于1
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i++) 
    {
    
        if(x % i == 0) 
        	return false;
    }
    return true;
}

（二）分解质因数——试除法

时间复杂度O（n½）
思想：从小到大尝试n的所有因数

解释代码里面x % i == 0的i一定是质数，这里可以怎么理解：i = c，如果c是合数且满足x % c == 0，那么一定存在比它小的另外两个数a,b，满足c = a * b。但是由于i是从2开始递增的，所以早在i递增到a或者b（这两个比c小的数的时候），x就已经被整除了，所以根本到不了i = c这个地方。来个实际的例子，x = 16，x就会在i = 2的时候被整除完，根本不会到所谓的i = 4。也就是说到i = c这个地方的时候x已经不存在2~i-1的任何质因子了
代码：

//试除法分解质因数 
void divide(int x)
{
    
    for (int i = 2; i <= x / i; i ++ )
	{
    
        if (x % i == 0)	// i一定是质数，具体解释看上面蓝色字体
        {
    
            int s = 0;	// s代表x可以被i整除的次数
            while (x % i == 0) x /= i, s ++ ;
            printf("%d %d\n", i, s);	// 这里可以使用vector<int, int> res;来记录
        }
	}
    if (x > 1) printf("%d %d\n", x, 1);	// 输出那个大于根号x的最大质因子
}

（三）筛法求素数

1、朴素筛法求素数

算法核心：把每个质数的所有倍数筛掉，所有剩下的数就是质数

调和级数：1 + 1/2 + 1/3 +…+ 1/n = lnn + c(c欧拉常数=0.577)

算法时间复杂度：内部循环总次数是n/2,n/3,n/4…1，累加得n(1/2 + 1/3 + 1/4 +…+1/n)=nlnn=nlogn
模板代码：

const int N = 1000010;

int primes[N], cnt;	// primes[]记录素数，cnt记录素数的个数，作为primes[]的索引
bool st[N];			// st[x]存储x是否被筛掉 true 说明被筛过

void get_primes(int n) 
{
    
    for (int i = 2; i <= n; i ++ )
    {
    
        if (!st[i])  //i如果没被筛过，说明i是质数，将i加入质数数组中
			primes[cnt ++ ] = i;
        
        //接下来对该质数的所有倍数进行筛选
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

缺点：同一个合数可能会被重复筛，比如8，会被2,4同时筛一次

2、埃式筛法O(nloglogn)

算法核心：把每个质数的所有倍数筛掉

质数定理：1~n中有n/logn个质数

实际算法时间复杂度：当数据不是足够大时与O(n)接近
代码：

const int N = 1000010;

int primes[N], cnt;	// primes[]记录素数，cnt记录素数的个数，作为primes[]的索引
bool st[N];			// st[x]存储x是否被筛掉 true 说明被筛过

void get_primes(int n) 
{
    
    for (int i = 2; i <= n; i ++ )
    {
    
        if (!st[i]) //st如果是true 说明被筛过，那么它的倍数肯定被筛过，所以直接跳过
        {
    
        	primes[cnt ++ ] = i;
	        for (int j = i + i; j <= n; j += i)	//接下来对该质数的所有倍数进行筛选
	            st[j] = true;
        }
    }
} 

3、线性筛法——每次用这个！

思路：把每一个合数用他的质因子筛掉就可以了，x只会被它的最小质因数筛去，即每个数字只被筛选一次，因此是线性的n。
算法时间复杂杂度：因为每个数只被它的最小质因子筛过一次，因此为O(n)

int primes[N], cnt;	// primes[]记录素数，cnt记录素数的个数，作为primes[]的索引
bool st[N];			// st[x]存储x是否被筛掉 true 说明被筛过

void get_prime(int x)
{
    
    for(int i = 2 ; i <= x ; i++)
    {
    
        if(!st[i]) primes[cnt ++] = i;
        // 现在是从小到大筛掉所有合数，每个合数只会被它的最小质因子筛一次。所以时间复杂度是O（n）
        for(int j = 0 ; primes[j] <= x / i ; j++)
        {
    										
            st[primes[j] * i] = true; //筛去primes[j]的倍数   
             /*
			 针对st[primes[j] * i] = true;本质上分两种情况
			 1.i % primes[j] == 0, 因为primes[j]是顺序遍历，因此当第一次模为零时，primes[j]一定为i的最小质因子，
			 primes[j]也一定为primes[j] * i的最小质因子
			 
			 2.i % primes[j] != 0, 同样因为primes[j]是顺序遍历，primes[j]一定小于i的所有质因子所以primes[j]也
			 一定为primes[j] * i最小质因子
			 */
            if(i % primes[j] == 0) break;	// 这句话成立的时候说明，primes[j]一定是i的最小质因子
        }
        
    }
} 
这里以9为例子，当i取到3的时候，并且primes[j]取到3的时候，此时就会被筛掉，而且这个primes[j]=3是9的最小质因子
以24为例子，当i取到12的时候，并且primes[j]取到2的时候，此时就会被筛掉，而且这个primes[j]=2是9的最小质因子
x=24的时候，筛掉数的顺序是
4___i = 2 primes[] = 2
6___i = 3 primes[] = 2
9___i = 3 primes[] = 3
8___i = 4 primes[] = 2
10__i = 5 primes[] = 2
15__i = 5 primes[] = 2
12__i = 6 primes[] = 2
14__i = 7 primes[] = 2
21__i = 7 primes[] = 3
16__i = 8 primes[] = 2
18__i = 9 primes[] = 2
20__i = 10 primes[] = 2
22__i = 11 primes[] = 2
24__i = 12 primes[] = 2

4、把数x分解成质因数的乘积形式

eg：360 = 2³ * 3⁵ * 5¹
代码：

// 返回的是map，prime[a]=b 的含义是a的b次幂 
unordered_map<int , int> fenjie(int x)
{
    
	unordered_map<int , int> primes; //利用哈希表存储所有的指数和底数，prime[a]=b 的含义是a的b次幂 
    for(int i = 2 ; i <= x / i; i++)	// 求x的质因数
    {
    
        while(x % i == 0)
        {
    
        	x /= i;
        	primes[i] ++;	// x对应的这个质因数i，i的指数加一
        }
    }
    if(x > 1) primes[x] ++;	// 如果x大于1，说明现在的x是原始x的比较大的一个质因数

	return primes;
}
tips:
这里的primes可以使用(auto t : primes)迭代，然后用t.first，t.second来访问

二、约数

约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

（1）试除法求所有约数O(n½)

思路：从小到大枚举较小的约数即可

// 求x的所有约数
vector<int> get_divisors(int x)
{
    
    vector<int> res;
    
    for(int i = 1 ; i <= x / i ; i++) 
    {
    
        if(x % i == 0) 	// i是x的一个约数，且x / i 也是x的一个约数——i * (x / i) = x
        {
    
            res.push_back(i);
            if(i != x / i) res.push_back(x / i); // 避免i和x / i 相同，重复加入
        }
    }
    
    sort(res.begin() , res.end());
    
    return res;
}

（2）求某个数的约数个数

算法思想：
基于算数基本定理：
N = p₁^α1 * p₂^α2 * … * p_k^αk
N的任意一项约数d可以写成 d = p₁^β1+p₂^β2+…+p_k^βk (这里β是满足在0—α的)

不同的β数组，组合而成的约数d是不同（即因式分解不同）
同理不同的a数组组合而成的N也是不同的，

而α₁有α₁+1种选法，α₂有α₂+1种选法…α_k有α_k+1种选法
因此约数个数：(α₁+1)(α₁+1)(α₃+1)…(α_k+1)

如果看不懂这里的证明，可以去看b站这个视频，链接如下公式推导：约数个数和约数之和

题目描述
给定n个正整数a_i，请你输出这些数的乘积的约数个数，答案对1e9+7取模。
代码：

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int P = 1e9 + 7;

int main()
{
    
    unordered_map<int , int> primes; //利用哈希表存储所有的指数和底数，prime[a]=b 的含义是a的b次幂 
    int n;
    cin >> n; 
    while(n --) //分解质因数
    {
    
        int x;
        cin >> x;
        for(int i = 2 ; i <= x / i; i++)	// 求x的质因数
        {
    
            while(x % i == 0)
            {
    
            	x /= i;
            	primes[i] ++;	// x对应的这个质因数i，i的指数加一
            }
        }
        if(x > 1) primes[x] ++;	// 如果x大于1，说明现在的x是原始x的比较大的一个质因数
    }
    //至此上面代码求出来了n个数乘积的所有质因数，以及对应质因数的幂的大小
    
    ll ans = 1;
    
    for(auto p : primes) //迭代一次，套用公式即可
        ans = ans * (p.second + 1) % P;  
    cout << ans << endl; 
    return 0;
}

（3）求某个数的约数之和

如果看不懂这里的证明，可以去看b站这个视频，链接如下公式推导：约数个数和约数之和

同样的某个数N可以展开为 N = p₁^a1 * p₂^a2 * … * p_k^ak

约数之和为：(p₁⁰+p₁¹+p₁²+…+p₁^a1) * (p₂⁰+p₂¹+p₂²+…+p₂^a2) * …* (p_k⁰+p_k¹+p_k²+…+p_k^ak)
即排列问题，展开后就是每一个约数，且都不相等

代码：

// 求质因数primes与上方代码相同
for(auto prime : primes)
    {
    
        int p = prime.first , q = prime.second;
        ll res = 1;
        while(q --)  res = (res * p + 1) % P; //看下面的图示
        
        ans = ans * res % P;
    }

上面res式子的解释：

(4) 最大公约数——欧几里得算法

也叫做辗转相除法。这里记最大公约数为gcd。

核心：gcd(a, b) = gcd(a, a % b)a和b的最大公约数，等于a和a % b的最大公约数
代码：

int gcd(int a, int b)	// 返回a和b的最大公约数
{
    
	return b ? gcd(b , a % b) : a;	// b不为0，返回gcd(b , a % b)，b为0,代表着求a和0的最大公约数，返回a
}

三、欧拉函数——O(n*(sqrt(n)))

（一）欧拉函数定义以及求x的欧拉函数

1~N中与N互质的数的个数被称为欧拉函数，记为Φ(N)。
互质是公约数只有1的两个整数，叫做互质整数。
eg:求Φ(6)，和6只有公约数为1的数有1和5，一共两个数，所以Φ(6) = 2

p₁ 到 p_k 是N的质因子
若在算数基本定理中，有
$$N=p_1^{\alpha 1}\ast p_2^{\alpha 2}\ast ...\ast p_k^{\alpha k}$$

证明欧拉函数（使用容斥原理）：
首先我们假设N的所有质因数是p₁到p_k，求1 ~N-1中与N互斥的数的个数s
1、从1 ~ N中去掉p₁p₂…p_k的所有倍数
$$s=N-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}$$
2、加上所有p_i * p_j的倍数
$$s=N-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}+\frac{N}{p_1{p}_2}+\frac{N}{p_1{p}_3}+...+\frac{N}{p_i{p}_j}$$
3、减去所有p_i * p_j * p_k 的倍数
$$s=N-\frac{N}{p_1}-\frac{N}{p_2}-...-\frac{N}{p_k}+\frac{N}{p_1{p}_2}+\frac{N}{p_1{p}_3}+...+\frac{N}{p_i{p}_j}-\frac{N}{p_1{p}_2{p}_3}-\frac{N}{p_1{p}_2{p}_4}-...-\frac{N}{p_i{p}_j{p}_k}$$
4、以此类推…。
5、最后求出欧拉函数的核心公式(最重要)：
$$\Phi (N)=N\ast (1-\frac{1}{p_1})\ast (1-\frac{1}{p_2})\ast ...\ast (1-\frac{1}{p_k})=N\ast (\frac{p_1-1}{p_1})\ast (\frac{p_2-1}{p_2})\ast ...\ast (\frac{p_k-1}{p_k})$$
p₁ 到 p_k 是N的质因子

步骤：
1、求出x的所有质因子
2、在求每个质因子的途中，就可以循环记录ans
模板：

#include <bits/stdc++.h> 
using namespace std;
 
typedef long long ll;   // 数据范围较大记得用long long
const int N = 110;
 
int n;
 
int main()
{
    
    cin >> n;
    while(n--)
    {
    
        int cnt = 0;
        ll primes[N];
        int x;
        cin >> x;

        ll ans = x;

        // 先分解质因数
        for(int i = 2 ; i <= x / i ; i ++ )
        {
    
            if(x % i == 0)	// i是x的质因子
            {
    
                ans = ans / i * (i - 1);    // ans = ans * (1 - 1 / x)，需要化简，结果就是ans = ans / i * (i - 1)
                while(x % i == 0) x /= i;
            }
        }
        
        if(x > 1) ans = ans / x * (x - 1);  // 最后一个比较大的质因子x
 
         
        cout << ans << endl;
    }
    return 0;
}

例题：AcWing 873.欧拉函数

（二）线性筛法求欧拉函数

线性筛法求欧拉函数之和O(n)
核心：在找到质数和筛掉和筛掉合数时，利用欧拉函数的公式直接计得出其欧拉函数
Proof1：
1、f (i % primes[ j ] == 0),这里记primes[ j ]为pj
2、现在求φ(i primes[ j ]),已知
$$\Phi (i)=i\ast (1-\frac{1}{p_1})\ast (1-\frac{1}{p_2})\ast ...\ast (1-\frac{1}{p_k})$$
3、因为i % primes[ j ] == 0，说明pj本身就是i的一个质因子，而Φ(i)本身计算的时候就用到了他所有的质因子p1…pk，所以Φ(i * primes[ j ])的质因子也是p1到pk。只不过求Φ的时候前面的i变成了ipj
4、所以
$$\Phi (i\ast primes[j])=i\ast primes[j]\ast (1-\frac{1}{p_1})\ast (1-\frac{1}{p_2})\ast ...\ast (1-\frac{1}{p_k})$$
5、将Φ(i)代入后化简得
$$\Phi (i\ast primes[j])=primes[j]\ast \Phi (i)$$

Proof2：
1、如果i % primes[ j ] != 0，首先有pj本身是质数，而且pj不是i的质因数，但是pj是i * pj的质因数。
2、现在求Φ(i *primes[ j ]),已知
$$\Phi (i)=i\ast (1-\frac{1}{p_1})\ast (1-\frac{1}{p_2})\ast ...\ast (1-\frac{1}{p_k})$$
3、此时有
$$\Phi (i\ast primes[j])=i\ast primes[j]\ast (1-\frac{1}{p_1})\ast (1-\frac{1}{p_2})\ast ...\ast (1-\frac{1}{p_k})\ast (1-\frac{1}{p_j})$$
4、将Φ(i)代入后化简得
$$\Phi (i\ast primes[j])=(primes[j]-1)\ast \Phi (i)$$
代码：

int primes[N], cnt;     // primes[]存储所有质数
int phi[N];             // 存储每个数的欧拉函数
bool st[N];         	// st[x]存储x是否被筛掉

// 返回的是1~n中每个数的欧拉函数之和
ll get_eulers(int n)
{
    
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ )  // 大模板是线性筛法求质数
    {
    
        if (!st[i])     // i是质数
        {
    
            primes[cnt ++ ] = i;    // 首先把质数记录到primes数组中
            phi[i] = i - 1;         // 其次，可以由i是质数得到，与它互质的数一共有i-1个。所以记录pgi[i] = i - 1
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
    
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0) 
            {
    
                phi[t] = phi[i] * primes[j];	// 看上面Proof1
                break;
            }
            else
            {
    
				phi[t] = phi[i] * (primes[j] - 1);	// 看上面Proof2
			}            
        }
    }
	
	ll res = 0;
	for(int i = 1; i = n; i ++ ) res += phi[i];
	return res;
}

（三）欧拉定理

“ ≡ ”是数论中表示同余的符号。即给定一个正整数n，如果两个整数a和b满足a - b能被n整除，即(a - b) mod n = 0，那么就称整数a与b对模n同余，记作a≡b(modn)，同时可成立a mod n=b。
定理：若a与n互质，则a^(Φ(n)) ≡ 1(mod n) 理解成a的Φ(n)次方模上n的余数是1.
互质是公约数只有1的两个整数，叫做互质整数。

费马小定理
由欧拉定理可以马上推得费马定理。
当n为质数时，Φ(n) = n - 1
因此当p是质数时，a^p-1≡ 1 (mod p) 即费马定理！

四、快速幂

目的：能快速的求出来a^k mod p的结果，时间复杂度为 O(logk)
方法：

eg：

算法核心：将k用二进制表示，然后对每一位进行0 1判断，进而累乘即可。
模板代码：

// 求 a^k mod p，时间复杂度 O(logk)。
int qmi(int a, int k, int p)
{
    
    int res = 1;
    while (k)
    {
    
        if (k & 1) 	// a的末尾是1的话，才对res累乘并求模
        	res = res * a % p;
        a = a * a % p; 	// 记录每一轮的a
        k >>= 1;	// 去掉k的最后一位
    }
    return res;
}

快速幂求逆元

题目：给定n组ai , pi，其中pi是质数,求ai模pi的乘法逆元，若逆元不存在则输出impossible。

逆元定义：若整数b，p互质，并且对于任意的整数 a，如果满足b|a=0，则存在一个整数x，使得a/b≡a∗x(mod p)，则称x为b的模p乘法逆元，记为b−1(mod p)。

接下来进行推导：
若：a/b≡a∗x(mod p)
两边同除a,得：1/b ≡ x (mod p)
移项得：x*b ≡ 1 (mod p) ，即x满足该式子即可！

由费马小定理得：若p是质数，且b不是p的倍数， 则bp-1 ≡ 1 (mod p)
因此x = b p-2 就是解。
当b%p = 0时 ，x*b ≡ 1 (mod p)显然无解

五、扩展欧几里得算法

六、中国剩余定理

七、高斯消元

八、组合计数

九、容斥原理

十、简单博弈论