目录
- 前言
- 质数
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 约数
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 欧拉函数
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 快速幂
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 扩展欧几里得算法
-
-
- 算法思想：
- 模板：
- 例题：
-
- AC代码：
-
- 中国剩余定理
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 高斯消元
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 求组合数
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 容斥原理
-
-
- 算法思想：
- 例题：
-
- AC代码：
-
- 博弈论
-
-
- 算法思想：
-
前言
质数
在所有自然数(所有<=自然数既不是质数也不是合数)，称为质数，或素数。
算法思想：
(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 <iostream>
#include <cstring>
#include <algorithm>
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 <iostream>
#include <algorithm>
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 <iostream>
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）约数个数：，根据算术基本定理： 由于 N = (p1x1)(P1x2)(p3x3)…(pkxk) 所以 例如 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）约数之和： （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 <iostream>
#include <algorithm>
#include <vector>
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 <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
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 <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
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 <iostream>
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 互质且 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 <iostream>
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 <iostream>
#include <cstring>
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;