质数

定义：大于1的整数中，只有1和本身两个约数的数称作质数

质数的判断

试除法，复杂度为$O(\sqrt{n})$

1
2
3
4
5
bool is_prime(int x) {
	for (int i = 2; i <= n / i; i++) // 推荐 i <= n / i表示边界
		if (x % i == 0) return false;
	return true;
}

分解质因数

试除法，复杂度为$O(\sqrt{n})$

n中最多包含一个大于sqrt(n)的质因子

1
2
3
4
5
6
7
8
9
10
11
12
13
void print_x(int x) {
	for (int i = 2; i <= x / i; i++)
		if (x % i == 0)
		{
			int cnt = 0;
			while (x % i == 0) {
				x /= i;
				cnt++
			}
			printf("%d %d", x, cnt);
		}
	if (x > 1) printf("%d 1", x);
}

质数的筛选

埃氏筛法，复杂度为$O(nloglogn)$

1
2
3
4
5
6
7
8
9
10
11
const int N = 100;
int primes[N], idx;
bool st[N];

void get_primes(int n) {
	for (int i = 2; i <= n; i++)
		if (!st[N]) {
			primes[idx++] = i;
			for (int j = i + i; j <= n; j += i) st[j] = true;
		}
}

线性筛法，复杂度为$O(n)$

线性是指确保每个合数仅被其最小质因数筛除一次，避免了重复计算

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N = 100;
int primes[N], idx;
bool st[N];

void get_primes(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[N]) primes[idx++] = i;
		for (int j = 0; primes[j] <= n / i; j++) {
			st[primes[j]*i] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

约数

求所有约数

参看质因数分解，复杂度为$O(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
 vector<int> get_divisors(int x) {
	vector<int> ans;
	for (int i = 1; i <= x/i; i++) {
		if (x % i == 0) {
			ans.push(i);
			if (i != x/i) ans.push(i);
		}
	}
	sort(ans.begin(), ans.end());
	return ans;
}

[0,n]的所有数的约数总共约有$\frac{n}{1} + \frac{n}{2} + … + \frac{n}{n} \to nlnn \lt nlogn$ ，即平均每个数都有logn个约数，所以get_divisors最后的排序复杂度约为$O(lognloglogn)$，比$O(\sqrt{n})$小

约数个数

公式：对于一个数$x = p_{1}^{d_1}p_{2}^{d_2}…p_{n}^{d_n}$ ($p_i$表示素因子)，约数个数为$\Pi_{i = 1}^{n}(d_i+1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int mod = 1e9 + 7;

int get_divisor_quantity(int n) {
    unordered_map<int, int> primes;

    for (int i = 2; i <= n / i; i++) 
        while( n % i == 0 ) {
            n /= i;
            primes[i]++;
        }
    if (n > 1) primes[n]++;

    int res = 1;
    for (auto [k, v] : primes) {
        res = (res * (v + 1)) % mod;
    }

    return res;
}

约数之和

公式：对于一个数$x = p_{1}^{d_1}p_{2}^{d_2}…p_{n}^{d_n}$ ($p_i$表示素因子)，约数总和为$\Pi_{i = 1}^{n}(\Sigma_{j=0}^{d_i}p_i^j) = (p_1^0 + p_1^1 + … + p_1^{d_1})(p_2^0 + p_2^1 + … + p_2^{d_2})…(p_n^0 + p_n^1 + … + p_n^{d_n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int mod = 10000;

int get_divisor_sum(int n) {
    unordered_map<int, int> primes;
    int total = n;

    for (int i = 2; i <= n / i; i++) 
        while (n % i == 0) {
            n /= i;
            primes[i]++;
        }
    if (n > 1) primes[n]++;

    int sum = 1;
    for (auto [p, cnt] : primes) {
        int t = 1;
        while (cnt--) {
            t = (t * p + 1) % mod;
        }
        sum = (sum * t) % mod;
    }

    return sum;
}

欧几里得算法

也称辗转相除法，用于求两个数的最大公约数

1
2
3
int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法

对于任意正整数a,b，一定存在整数x,y，使得$ax + by = gcd(a,b)$；欧几里得算法的作用就是能求出x,y的一个特解

1
2
3
4
5
6
7
8
9
10
int exgcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a%b, y, x);
	// d == yb + x(a%b) == yb + x(a - a/b*b) == xa + (y-a/b*x)b
	y -= a / b * x;
	return d;
}

例子：求解线性同余方程 (ax = b (mod m)))

1
2
3
4
5
6
7
8
9
typedef long long LL;

int main() {
	int a, b, m, x, y;
	cin >> a >> b >> m;
	int d = exgcd(a, m, x, y);
	if (b % d) cout << "no solution" << endl;
	else cout << (LL)x * (b / d) << endl;
}

扩展欧几里得算法也常用于求逆元。

欧拉函数

$\varphi(n)$表示[1, n]中与n互质的数的个数，其中$n = p_1^{d_1}p_2^{d_2}…p_n^{d_n})$，则$\varphi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_n})$ ，证明可用容斥原理

复杂度为$O(\sqrt{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
int phi(int n) {
    int res = n;
    // get primes
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }

    if (n > 1) res = res / n * (n - 1);
    return res;
}

筛法求欧拉函数

用于求解[1, n]中每个数对应的欧拉函数值，利用线性筛法，复杂度为$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N = 100;
int phi[N], primes[N], idx;
bool st[N];

void get_eulers(int n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!st[i]) {
			primes[idx++] = i;
			phi[i] = i-1;
		}
		for (int j = 0; primes[j] <= n / i; j++) {
			st[i*primes[j]] = true;
			if (i % primes[j] == 0) {
				phi[i*primes[j]] = primes[j] * phi[i];
				break;
			}
			phi[i*primes[j]] = (primes[j] - 1) * phi[i];
		}
	}
}

欧拉定理

对于a与n互质，则$a^{\varphi(n)} = 1 (mod n)$

证明原理：对于a与n互质，且b与n互质，则ab与n互质

（引理）费马小定理： 对于a与素数p互质，则$a^{p-1} = 1 (mod p)$，即a模p的逆元为$a^{p-2}$，可通过快速幂计算

快速幂

对于$a^k mod n$，复杂度为$O(logk)$

1
2
3
4
5
6
7
8
9
10
11
typedef long long LL;

LL get_exp(int a, int k, int n) {
	int res = 1, tmp = a % n;
	while (k) {
		if (k & 1) res = (LL) res * tmp % n;
		k >>= 1;
		tmp = (LL)tmp * tmp % n;
	}
	return res;
}

例子：快速幂求逆元（利用欧拉定理）略

中国剩余定理

$$
\begin{cases}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \
\vdots \
x \equiv a_k \pmod{m_k}
\end{cases}
$$
其中$m_i$两两互质
令$M = m_1m_2…m_k$，$M_i = \frac{M}{m_i}$，$M_i^{-1}$表示$M_i$模$m_i$的逆元，则有
$$
x = a_1M_1M_1^{-1} + a_2M_2M_2^{-1} + … + a_kM_kM_k^{-1}
$$

高斯消元

高斯消元是一种用于求解线性方程组的经典方法

将方程式可以转化为一个增广矩阵，并通过初等行列变换求出等价的上三角形矩阵，就能依次消元求出$x_n$到$x_1$的一个解

初等行列变换一共有三个操作：

  1. 把某一行乘一个非零的数
  2. 交换某两行
  3. 把某行的若干倍加到另一行上

上三角形矩阵的三个形态代表三种解：

  1. 完美阶梯梯形：唯一解
  2. 0 = 非零：无解
  3. 0 = 0：无穷解

求解步骤：

  1. 矩阵转化为上三角形矩阵
    1. 从当前行r开始，找出[r,n)行中第c个系数（首个非零的系数）最大的行，与第r行交换
    2. 将第r行的首个系数压缩为1
    3. 利用第r行依次将(r, n)行的第c个系数消为0
  2. 从第n-1行向第0行遍历，使当前行i利用第j行的结果，消除掉所有第j个参数（j > i)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    const double eps = 1e-6;
    const int N = 100;
    double a[N][N];

    int gaussion() {
    	int c, r;
    	for (c = 0, r = 0; c <= n; c++) {
    		// find max first-argument row
    		int t = r;
    		for (int i = r; i <= n; i++) 
    			if (fabs(a[i][c]) > fabs(a[t][c]))
    				t = i;

    		// if c-argument is all zero, skip
    		if (fabs(a[t][c]) <= eps) continue;

    		// swap row
    		for (int i = c; i <= n; i++) swap(a[t][i], a[r][i]);

    		// make c-argument to 1
    		for (int i = n; i >= c; i--) a[r][i] /= a[r][c];

    		// elimination
    		for (int i = r + 1; i <= n; i++)
    			if (fabs(a[i][c]) > eps)
    				for (int j = n; j >= c; j--) 
    					a[i][j] -= a[i][c] * a[r][j];
    		r++;
    	}

    	// if a is not a perfect top-triangle matrix 
    	if (r < n) {
    		for (int i = r; i < n; i++) 
    			if (fabs(a[i][n]) > eps) return 2; // no solution
    		return 1; // infinite solution
    	}
    	// get answer
    	for (int i = n - 1; i >= 0; i--) {
    		for (int j = i + 1; j < n; j++) 
    			a[i][n] -= a[i][j] * a[j][n];
    	return 0;
    }

组合计数

方式一：利用公式$C_a^b = C_{a-1}^b + C_{a-1}^{b-1}$，可以实现$O(n^2)$复杂度计算

1
2
3
4
5
6
7
8
9
10
const int N = 100;
const int mod = 1e9+5;
int c[N][N]; //全局遍历初始化为0，故c[i][j] = 0 (j > i)

void get_comb() {
	for (int i = 0; i < N; i++) 
		for (int j = 0; j <= i; j++)
			if (!j) c[i][j] = 1;
			else c[i][j] = (c[i-1][j] + c[i-1][j]) % mod;
}

方式二：预处理得到$fact[i] \equiv i! mod (10^9+7)$和$infact[i]=(i!)^{-1} mod (10^9+7)$，使得$C_a^b \equiv \frac{a!}{b!(a-b)!} = ((fact[a]*infact[b])%mod * infact[a-b])%mod$ ,复杂度为$O(nlogp)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef long long LL;
const int N = 1000, mod = 1e9+7;
int fact[N], infact[N];
int 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;
}

void init() {
	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) % p;
	}
}

int get_comb(int a, int b) {
	return (LL)fact[a] * infact[b] % p * infact[a-b] % p;
}

方式三：卢卡斯定理，$C_a^b \equiv C_{a mod p}^{b mod p} * C_{a/p}^{b/p}(mod p)$，复杂度为$O(nlognlog_pN)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long LL;
const int mod = 1e5+5;
int p;

int C(int a, int b) {
	int res = 1;
	for (int i = 1, j = a; i <= b; i++, j--) {
		res = (LL) res * j % p;
		res = (LL) res * qmi(i, q - 2, q) % q;
	}
	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. 获得小于等于a的所有素数
  2. 获取$C_a^b$中每个素因子的指数
  3. 通过大数乘法求得$C_a^b$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const int N = 1e5+5;
int primes[N], sum[N], idx;
bool st[N];

void get_primes(int n) {
	for (int i = 2; i <= n; i++) {
		if (!st[i]) primes[idx++] = i;
		for (int j = 0; primes[j] <= n / i; j++) {
			st[i*primes[j]] = true;
			if (i % primes[j] == 0) break;
		}
	}
}

int get(int a, int p) { // 计算a!中p的指数
	int res = 0;
	while (a) {
		res += a / p;
		a /= p;
	}
	return res;
}

vector<int> mul(vector<int> a, int p) {
	vector<int> res;
	int carry = 0;
	for (int i = 0; i < a.size(); i++) {
		carry += a[i] * p;
		res.push_back(carry % 10);
		carry /= 10;
	}
	while (carry) {
		res.push_back(carry % 10);
		carry /= 10;
	}
	return res;
}

vector<int> get_C(int a, int b) {
	get_primes(a);

	for (int i = 0; i < idx; i++) {
		sum[i] = get(a, primes[i]) - get(b, primes[i]) - get(a-b, primes[i]);
	}

	vector<int> res(1,1);
	for (int i = 0; i < idx; i++) 
		for (int j = 0; j < sum[i]; j++)
			res = mul(res, primes[i]);
	
	return res;
}

卡特兰数

$C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{C_{2n}^n}{n+1}$，可用于解决n次ab二选一，但任意前m次选a的次数不多于b的问题，如：

  • 括号匹配
  • 栈排序
  • 路径选择
  • 凸多边形的三角剖分

    可通过平面坐标系结合几何对称性质证明

容斥原理

$$
\left|\bigcup_{i = 1}^{n} A_i\right|=\sum_{k = 1}^{n}(-1)^{k - 1}\sum_{1\leq i_1<i_2<\cdots<i_k\leq n} |A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|
$$
可通过该组合恒等式$\sum_{k=0}^{r}C_r^k(-1)^{k} = 0$证明并集的每一部分总共只被计算了一次

复杂度为$O(n2^n)$

给出n和m，以及m个素数，求出[1, n]中是该m个素数的倍数的数的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int get_prime_multiple(int n, int m, vector<int> primes) {
	int res = 0;
	for (int i = 1; i < (1 << m); i++) { // 不能都不选！
		int p = 1, cnt = 0;
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) {
				p *= primes[j];
				cnt++;
			}
		}
		if (cnt & 1) res += n / p;
		else res -= n / p;
	}
	return res;
}

博弈论

Nim游戏

  1. 初始设置：游戏开始时，有一堆或多堆物品。每堆中可以有不同数量的物品。
  2. 轮流行动：两名玩家轮流行动。每次行动时，玩家可以选择任意一堆物品，并从中移除一个或多个物品，但不能从多堆中同时移除物品，也不能不拿。
  3. 游戏结束：当所有物品都被移除后，游戏结束。通常，移除最后一个物品的玩家获胜，但在某些变体中，移除最后一个物品的玩家可能会输掉游戏。

在n堆物品$a_1,\cdots,a_n$中，如果$a_1 ⊕ a_2 ⊕ \cdots ⊕ a_n = 0$ ，则先手必败，否则先手必胜

证明：

  1. $0 ⊕ 0 ⊕ \cdots ⊕ 0 = 0$, 结束局面
  2. $a_1 ⊕ a_2 ⊕ \cdots ⊕ a_n = x \neq 0$，设x二进制为$x_kx_{k-1}\cdots x_1$，$x_k$显然为1，则必然存在$a_i = a_{i,m}a_{i,m-1},\cdots ,a_{i,k}, \cdots ， a_{i, 1}$, 其中$a_{i,k}$也为1；由于$a_i \gt a_i ⊕ x$，可以从$a_i$取出$a_i - a_i ⊕ x$个物品，那么第i堆就剩下$a_i ⊕ x$个物品，使得局面变成 $a_1 ⊕ a_2 ⊕ \cdots ⊕ a_n ⊕ x = 0$
  3. $a_1 ⊕ a_2 ⊕ \cdots ⊕ a_n = 0$，则无论怎么取，下个局面肯定不等于0。

有向图游戏

是Nim游戏的一种变种，我们先定义几个操作：

  • Mex运算：S是一个非负整数集合，则Mex(S)表示不在S中的最小非负整数
  • SG函数：x是有向图中的一个节点：
    • 如果x出度为0，则SG(x) = 0
    • 否则假设x的所有后继节点为$x_1, x_2, \cdots, x_n$，$SG(x) = Mex({SG(x_1), SG(x_2), \cdots, SG(x_n})$

有向图游戏：

  1. 初始设置：游戏开始时，有若干个有向图，每个图都有一个起点。
  2. 轮流行动：两名玩家同时行动。每次行动是，玩家可以选择任意一个图，并将当前图的当前节点移动至任意一个后继节点上，但不能同时操作多个图，也不能不移动。
  3. 游戏结束：当所有图的当前节点都无法移动后，游戏结束。最后无法移动的玩家失败。

设给定的n个有向图的起点为$x_1, x_2, \cdots, x_n$，则$SG(x_1) ⊕ SG(x_1) ⊕ \cdots ⊕SG(x_n) = 0$时，先手必败，否则先手必胜。证明参考Nim游戏中的证明。