算法基础课：第四讲——数学知识
时间：2023-05-28 21:07:00
目录
- 前言
- 质数
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 约数
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 欧拉函数
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 快速幂
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 扩展欧几里得算法
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 中国剩余定理
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 高斯消元
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 求组合数
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 容斥原理
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 博弈论
-
-
- 算法思想：
-
前言
质数
在所有严格大于1自然数(所有<=自然数既不是质数也不是合数)只两个约数只包括1和本身，称为质数，或素数。
算法思想：
(1)质数的判断——试除法：复杂度O(√n)
朴素做法：循环2—n判断n % i 是否 == 0.如果有等于0，则不仅包括1和本身的约数，而且不是质数。时间的复杂性是 O(n)，较高
若d能整除n 则 n|d 也能整除 n，所以我们只需要枚举 d <= n|d，变形得 d <= √n。这里有许多不同的写法：sqrt(n)：执行函数每次都需要影响速度 ；i * i <=n：有溢出风险，所以我们使用它 i <= n / i 枚举写法
（2）分解质因数——试除法:
从小到大枚举 n 所有因数，n最多只包含一个大于一个√n质因子也只需要枚举√n
（3）朴素筛质数：将1—n中所有数 x 删除倍数(使用bool数组标记)，筛选后剩余数量为质数，时间复杂度为O(nlogn)
(4)优化筛质数——埃氏筛：对于简单的筛质数，我们只需要质数的倍数删掉即可，时间复杂度为O(nloglogn)
（5）线性筛：n 它只会被他的最小质因子筛选出来。如果不是质数，加入数组，从小到大列举所有质数，筛选质数倍数，时间复杂度为O
模板：
// 试除法判断素数 bool is_prime(int n) {
if (n < 2) return false; for (int i = 2; i <= n / i; i ) if (n % i == 0) return false;
return true;
}
// 分解质因数
void divide(int n)
{
for (int i = 2; i <= n / i; i ++)
if (n % i == 0)
{
int s = 0;
while (n % i == 0)
{
s ++;
n /= i;
}
cout << i << ' ' << s << endl;
}
if (n > 1) cout << n << ' ' << 1 << endl;
cout << endl;
}
// 朴素筛质数
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
primes[cnt ++] = i;
}
for (int j = i + i; j <= n; j += i) st[j] = true; // i的倍数都标记true
}
}
// 埃氏筛
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
primes[cnt ++] = i;
for (int j = i + i; j <= n; j += i) st[j] = true; // i的倍数都标记true
}
}
}
// 线性筛
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i]) primes[cnt ++] = i;
for (int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break; // primes[j] 一定是i的最小质因子
}
}
}
例题：
AcWing 866. 试除法判定质数
AcWing 867. 分解质因数
AcWing 868. 筛质数
AC代码：
// 试除法
#include 约数
算法思想：
（1）试除法求约数
（2）约数个数：int范围内约数最多一个数约数个数大概在1500个，根据算术基本定理：
由于 N = (p1x1)(P1x2)(p3x3)…(pkxk)
所以约数个数 = (x1 + 1)(x2 + 1)(x3 + 1)…(xk + 1)
例如 24 = 23 + 31，所以2可以取0,1,2,3，而3可以取0,1 所以24的约数共 4 x 2 = 8 种情况，分别为1,2,3,4,6,8,12,24
（3）约数之和：约数之和 = (p10+p11+p12+……+p1x1)……(pk0+pk1+pk2+……+pkx1)
（4）欧几里得算法：gcd(a, b) = gcd(b, a mod b)
模板：
// 欧几里得算法
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
例题：
AcWing 869. 试除法求约数
AcWing 870. 约数个数
AcWing 871. 约数之和
AC代码：
// 试除法求约数
#include 欧拉函数
算法思想：
定义：
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中，N = p1a1p2a2…pmam，则：
ϕ(N) = N × (p1 − 1) / p1× (p2 − 1) / p2 × … × (pm − 1) / pm
即由由容斥原理可证
筛法 求欧拉函数：通过线性筛，求1~n的欧拉函数，证明略见模板
欧拉定理： 若 a 与 n 互质 => aφ(n) mod n == 1
费马小定理： 由欧拉定理推得，当 a 与 p 互质时， aφ(n) mod n = 1，若 n 为质数，则 φ(n) = n - 1，所以原公式推得 a n-1 mod n = 1
即
a n-1 mod n = 1 当 a 与 n 互质且 n 为质数
模板：
LL get_eulars(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
primes[cnt ++] = i;
phi[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
{
phi[primes[j] * i] = phi[i] * primes[j];
break; // primes[j] 一定是i的最小质因子
}
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
LL res = 0;
for (int i = 1; i <= n; i ++) res += phi[i];
return res;
}
例题：
AcWing 873. 欧拉函数
AcWing 874. 筛法求欧拉函数
AC代码：
// 求欧拉函数
#include 
