算法基础课:第四讲——数学知识
时间: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
#include
#include
using namespace std;
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;
}
int main()
{
int n;
cin >> n;
while (n --)
{
int a;
cin >> a;
if (is_prime(a)) cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
// 分解质因数
#include
#include
using namespace std;
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;
}
int main()
{
int n;
cin >> n;
while (n --)
{
int a;
cin >> a;
divide(a);
}
}
// 朴素筛质数
#include
using namespace std;
const int N = 1e6 + 5;
int cnt;
int primes[N];
bool st[N];
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
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
}
约数
算法思想:
(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
#include
#include
using namespace std;
vector<int> get_divisiors(int n)
{
vector<int> res;
for (int i = 1; i <= n / i; i ++)
if (n % i == 0)
{
res.push_back(i);
if (i != n / i) res.push_back(n / i); // n 可能是 i 的平方
}
sort(res.begin(), res.end());
return res;
}
int main()
{
int n;
cin >> n;
while (n --)
{
int a;
cin >> a;
auto res = get_divisiors(a);
for (auto item : res)
cout << item << ' ';
cout << endl;
}
return 0;
}
// 约数个数
#include
#include
#include
#include
using namespace std;
const int N = 105, MOD = 1e9 + 7;
int n;
typedef long long LL;
int main()
{
cin >> n;
unordered_map<int, int> hash;
while (n --)
{
int x;
cin >> x;
// 分解质因子
for (int i = 2; i <= x / i; i ++)
while (x % i == 0)
{
hash[i] ++; // 质因子的指数 + 1
x /= i;
}
if (x > 1) hash[x] ++;
}
LL res = 1;
for (auto item : hash) res = res *(item.second + 1) % MOD;
cout << res << endl;
return 0;
}
// 约数之和
#include
#include
#include
#include
using namespace std;
const int N = 105, MOD = 1e9 + 7;
int n;
typedef long long LL;
int main()
{
cin >> n;
unordered_map<int, int> hash;
while (n --)
{
int x;
cin >> x;
// 分解质因子
for (int i = 2; i <= x / i; i ++)
while (x % i == 0)
{
hash[i] ++; // 质因子的指数 + 1
x /= i;
}
if (x > 1) hash[x] ++;
}
LL res = 1;
for (auto item : hash)
{
int p = item.first, a = item.second; // 取质因子和它的指数
LL t = 1; // 秦九韶算法
while (a --) t = (t * p + 1) % MOD;
res = res * t % MOD;
}
cout << res << endl;
return 0;
}
// 欧几里得算法
#include
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
int n;
cin >> n;
while (n --)
{
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
}
return 0;
}
欧拉函数
算法思想:
定义:
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
using namespace std;
int main()
{
int n;
cin >> n;
while (n --)
{
int x;
cin >> x;
int res = x;
for (int i = 2; i <= x / i; i ++)
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
cout << res << endl;
}
return 0;
}
// 筛法求欧拉函数
#include
#include
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
bool st[N];
int primes[N], cnt;
int phi[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;