1. 质数的判断
质数：在大于1的整数中，如果只包含1和它本身这两个约数，就被成为质数，或者叫素数.
如果 d | n, 则(n / d) | n. ------ 可以发现n的所有约数都是成双成对出现的.
质数定理： 1 - n中有n / lnn 个质数.
调和级数： 1 + 1 / 2 + 1 / 3 + 1 / 4 + ··· = lnn + C(0.577)
1.朴素做法 ---- $O(n)$
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2; i < n; i ++){
if(n % i == 0){
return false;
}
}
return true;
}
2.改进版 ---- $O(\sqrt{n})$(一定是)
bool is_prime(int n){
if(n < 2) return false;
for(int i = 2; i <= n / i; i ++){//约数成对出现,i 和 n / i, 枚举到较小的那个即可.
if(n % i == 0){
return false;
}
}
return true;
}
尽量不要写成：
1. for(int i = 2; i * i <= n; i ++) // 但 i 较大时, i * i 可能超出int的最大表示范围,导致结果出错.
2. for(int i = 2; i <= sqrt(n); i ++) // 反复调用sqrt()函数, 运行效率比较低
建议写成：
for(int i = 2; i <= n / i; i ++) // 可以很好地规避上述情况
典型例题
2. 分解质因数
分析：假设枚举到 i, n 中一定不包含 2 ~ i - 1 之间的质因子, 又因为n % i == 0,即 n 为 i 的倍数, 所
以 i 当中也不包含 2 ~ i - 1 之间的质因子, 所以 i 一定是质数.
1.朴素做法 ---- $O(n)$
void divide(int n){
for(int i = 2; i <= n; i ++){
if(n % i == 0){
int s = 0;
while(n % i == 0){
n /= i;
s ++;
}
cout << i << ' ' << s << endl;
}
}
}
2.改进版 ---- $O(\sqrt{n})$(不一定)
void divide(int n){
for(int i = 2; i <= n / i; i ++){//n中最多包含一个大于sqrt(n)的质因子
if(n % i ==0){
int s = 0;
while(n % i == 0){
n /= i;
s ++;
}
cout << i << ' ' << s << endl;
}
}
if(n > 1) cout << n << ' ' << '1' << endl;//大于sqrt(n)的质因子
}
注意：当 n = $2 ^ k $时, 时间复杂度为logn, 因此其时间复杂度介于 logn ~ $\sqrt{n}$之间
典型例题
3. 筛质数
1.朴素做法 ----$O(n * logn)$
原理: 2 - p - 1中的数都没有把 p 删掉,说明 p 不是 2 - p - 1 当中任何一个数的倍数,因此 p 是一个质数.
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
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){//依次删掉每个i的倍数
st[j] = true;
}
}
}
2.改进版 ---- $O(n * loglogn)$ (埃氏筛法)
质数定理：1 - n 当中, 有 n / lnn 个质数.
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
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){//只删掉质数i的倍数
st[j] = true;
}
}
}
}
2.终极版 ---- $O(n)$ (线性筛法)
核心：每个 n 只会被它的最小质因子筛掉.
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
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的最小质因子
}
}
}
分析：
1.i % primes[j] == 0, 说明：primes[j]一定是i的最小质因子,primes[j]一定是primes[j] * i的最小质因子
2.i % primes[j] != 0, 说明: primes[j]一定小于i的所有质因子,primes[j]一定是primes[j] * i的最小质因子
综上：primes[j]一定是primes[j] * i的最小质因子.
我们用最小质因子筛,而每个数只有一个最小质因子,因此每个数只会被筛一次,所以是线性的.
注意：如果在1e6左右,埃氏筛法和线性筛法差不多,但在1e7左右,线性筛法要比埃氏筛法快几倍.在实际应用中线性筛法用的比较多,埃氏筛法用的较少,但埃氏筛法的思想很重要.
典型例题
4.求约数
1.试除法求约数 ---- $O(\sqrt{n})$
vector<int> get_divisors(int n){
vector<int> res;
for(int i = 1; i <= n / i; i ++){//约数成对出现,i 和 n / i, 枚举到较小的那个即可.
if(n % i == 0){
res.push_back(i);
if(i != n / i) res.push_back(n / i);
}
}
sort(res.begin(), res.end());
return res;
}
典型例题
2.约数个数
算术基本定理：任何一个正整数N都可以唯一地分解为: N = $P_1^{\alpha_1} · P_2^{\alpha_2} · P_3^{\alpha_3} ···P_k^{\alpha_k}$
如： 12 = 2^2 * 3
36 = 2^2 * 3^2
···
约数的形式：$d = P_1^{\beta_1} · P_2^{\beta_2} · P_3^{\beta_3} ···P_k^{\beta_k}$ ($ 0 <= \beta_i <= \alpha_i$)
约数个数：$(\alpha_1 + 1)*(\alpha_2 + 1) ··· (\alpha_k + 1)$
典型例题
3.约数之和
$(P_1^0 + P_1^1 + P_1^2 + P_1^{\alpha_1})···(P_k^0 + P_k^1 + P_k^2 + P_k^{\alpha_k})$
典型例题
-----
5. 欧几里得算法(辗转相除法) ---- $O(logn)$
最大公约数表示： gcd(a, b) 或 (a, b)
最小公倍数表示： lcm(a, b) 或 [a, b]
0和任何一个数的最大公约数都是那个数本身
理论基础： (a,b) = (b, a mod b) --- 理论上证明：最多转化logn次
求最大公约数
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
证明：
(a, b) >= (b, a mod b)
设(b, a mod b)公约数为d
令 a = kb + r 则 a mod b = r;
因为 d | b 且 d | r
所以 d | a
(a, b) <= (b, a mod b)
因为 d | a 且 d | b
所以 d | r
所以 (a, b) = (b, a mod b)
求最小公倍数
int lcm(int a, int b){
return a * b / gcd(a, b);
}
典型例题
6. 扩展欧几里得算法
裴蜀定理：若 a,b是整数,且 (a,b)=d, 那么对于任意的整数 x,y,ax + by 都一定是 d 的倍数，特别地，一定
存在整数 x,y,使 ax + by=d 成立.```
欧几里得算法：可以求出两个数的最大公约数d 即(a, b) = d.
用途：可以求出最大公约数d，且可以求出 ax + by = d 的系数
(a, b)
ax + by = d
a' = a / d
b' = b / d
//任意一组解
x = x0 + kb'
y = y0 + ka'
证明过程：
由
ax0 + by0 = d
ax' + by' = d
推出:
a(x' - x0) = b(y0 - y')
a'(x' - x0) = b'(y0 - y')
=> b'|a'(x' - x0)
由于a' 与 b' 互质
=> b'|(x' - x0)
=> x' - x0 = kb'
(a, b) = (b, a % b)
假设递归时求出了a 和 b
by + (a mod b)x = d
= by + (a - a/b * b)*x //因为递归的时候b与a互换了位置,同时y与x也应互换位置
= ax + (y - a/b * x)*b = d
=>x' = x
=>y' = y - a / b * x
//扩展欧几里得算法,返回最大公约数 d, 且计算出二者的系数 x 和 y
int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return a;//最大公约数为 a
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
经典例题
7. 欧拉函数
欧拉函数的常用性质：
$1. 如果 n,m 互质，则 ϕ(nm)=ϕ(n)ϕ(m)$;
$2. 小于等于 n，且与 n 互质的数的和是 ϕ(n)×n/2$;
$3. 欧拉定理：如果 n, a 互质，且均为正整数，则 a^ϕ(n)≡1(mod n)$;
欧拉函数
int phi(int 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);
return res;
}
筛法求欧拉函数
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[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)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
典型例题
8. 快速幂 ----- $O(logk)$
主要用途：计算 $m^k % p$
int qmi(int a, int k, int p){
int res = 1;
while(k){
//当前位不为0是才累积,往往容易忽略此条件导致错误
if(k & 1) res = (LL) res * a % p;//两数相乘可能会爆Int
a = (LL) a * a % p;// 计算后, a平方
k >>= 1;//移去最低位
}
return res;
}
注意：务必记得 mod p, 务必记得 mod p, 否则极易出错！
1. res = (LL) res * a % p;
2. a = (LL) a * a % p
典型例题
10. 高斯消元
一般步骤：
枚举每一列
step1: 找到当前列绝对值最大的一行.
step2: 将此行换至最上面一行(还未处理好的行中的最上面的那行).
step3: 将该列当前行的第一个数变为 1
step4: 将当前列最大行以下的左右行变为 0
step1 - step4主要目的为化行列式为上三角行列式,且各行非零首元均为1
double a[N][N]//为增广矩阵
int gauss(){
int r, c;// r 表示行 row, c 表示列 col
//枚举列
for(c = 0, r = 0; c < n; c ++){
//找到当前列以下所有行的最大值的行号, 目的：避免系数变得太大，精度较高
int t = r;
for(int i = r; i < n; i ++){
if(fabs(a[i][c]) > fabs(a[t][c])) t = i;
}
//剩余当前列最大行的元素为0,则已满足要求,直接跳过即可
if(fabs(a[t][c]) < eps) continue;//剪枝
//当最大行的元素交换到剩余行的行首
for(int i = c; i <= n; i ++){
if(t == r) continue;
swap(a[r][i], a[t][i]);
}
//处理剩余行首(最大行)的各元素,使得当前列的元素为1
for(int i = n; i >= c; i --){
a[r][i] /= a[r][c];
}
//处理当前列剩余最大行以下的所有元素,使其均为0
for(int i = r + 1; i < n; i ++){
if(fabs(a[i][c]) < eps) continue;//剪枝
for(int j = n; j >= c; j --){
a[i][j] -= a[r][j] * a[i][c];
}
}
r ++;//以保证当前行以上均为上三角行列式,且非零首元均为1, 处理下一行
}
//存在全0行(等号左边全为0)
if(r < n){
for(int i = r; i < n; i ++){
if(fabs(a[i][n]) > eps) return 0;//出现等号左侧为0,右侧不为0的情况,即无解
}
return 2;//有无穷多解
}
//由最后一行倒退至第一行求地未知数的解
for(int i = n - 1; i >= 0; i --){
for(int j = i + 1; j < n; j ++){//i + 1表示当前未知数x后的所有已知解得未知数的起始位置
a[i][n] -= a[i][j] * a[j][n];//用增广矩阵所在列元素存放未知数的值
}
}
return 1;//有唯一解
}
经典例题
11. 求组合数
case1: 10万组询问, 1 <= b <= a <= 2000 => 使用递推$O(n^2)$
case2: 1万组询问, 1 <= b <= a <= 1e5 => 预处理$n * logn$
case3: 20组询问, 1 <= b <= a <= 1e18 1 <= p <= 1e5, =>lucas定理
lucas定理： c[a][b] = c[a % p][b % p] * c[a / p][b / p] % p
递推法求组合数
for(int i = 1; i < N; i ++) c[i][0] = 1, c[0][i] = 1;//预处理
for(int i = 1; i < N; i ++){
for(int j = 1; j <= i; j ++){
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
通过预处理逆元的方式求组合数
首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
Lucas定理
若p是质数，则对于任意整数 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b) // 通过定理求组合数C(a, b)
{
int res = 1;
for (int i = 1, j = a; i <= b; i ++, j -- )
{
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2) % p;
}
return res;
}
int lucas(LL a, LL b)
{
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}
分解质因数法求组合数
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
1. 筛法求出范围内的所有质数
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
3. 用高精度乘法将所有质因子相乘
int primes[N], cnt; // 存储所有质数
int sum[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 = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p) // 求n！中的次数
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
vector<int> mul(vector<int> a, int b) // 高精度乘低精度模板
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
get_primes(a); // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘
for (int j = 0; j < sum[i]; j ++ )
res = mul(res, primes[i]);
卡特兰数
给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的
序列的数量为： Cat(n) = C(2n, n) / (n + 1)
经典例题
求组合数 I
求组合数 II
求组合数 III
满足条件的01序列
个人小建议：筛质数的改进版把除法改成乘法可能会更好一点，除法精度有损
乘法的话,两数的乘积容易溢出, 比如当 n 取将近 int 最大值时,i * i 可能会大于 int 的范围，导致乘积为负数, 从而影响结果.
可是如果i设置成长整型的话，不就可以解决了吗
顺便再提一句，筛质数的题目不至于出现那么大的数吧
看个人习惯吧，一般也不会出现什么问题.
求第n个素数，
n <= 1e18。hhh 一道板子题线性筛法预处理O(n), 然后直接查询即可O(1), 确实是模板题
$1e18$线性筛不了呀。qaq