数论与组合数学学习笔记

整理学习数论和组合数学时的所思所想。

数论入门

求最大公约数与最小公倍数

求最大公约数的最朴素的想法就是暴力枚举。

1
2
3
4
5
6
7
8
9
10

int gcd1(int a, int b) {//假定输入的a，b都是正数
	int ans = 1;
	int _max = max(a, b), _min = a + b - _max;
	for (int i = 2; i <= _min; i++) {
		if (_max % i == 0 && _min % i == 0) {
			ans = i;
		}
	}
	return ans;
}

此外，还可以使用辗转相除法，其原理为\(\text{gcd}(a, b)=\text{gcd}(b, a \mod b)\)。证明如下：

设\(a=kb+r\)，其中\(a, b, k, r\in Z，r=a \mod b\)。

另设\(d\)为\(a\)与\(b\)的一个公约数，由\(a=kb+r\)有：\(r=a-kb\)，等式两边同除\(d\)得：\(\displaystyle \frac{r}{d}=\frac{a}{r}-\frac{kb}{d}\)，显然式中任意一项都是整数，则\(r\)也是\(a\mod(b)\)的因子。

事实上还有\(\text{gcd}(a,b)=\text{gcd}(b,a)\)，这一性质可以用于算法正确性的证明。

1
2
3
4
5
6
7
8
9
10
11
12
13

int gcd2(int a, int b) {
	return a % b == 0 ? b : gcd2(b, a % b);
}

int gcd3(int a, int b) {
	int r = a;
	while (r != 0) {
		r = a % b;//取余数
		a = b;//大数更新为小数
		b = r;//小数更新为余数
	}
	return a;
}

实际上，更相减损法与辗转相除法实质是一样的，而且前者所需的计算次数通常更多。更相减损法的原理是\(\text{gcd}(a,b)=\text{gcd}(\min(a,b),\max(a,b)-\min(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

int gcd4(int a, int b) {
	if (a == b) {
		return a;
	}
	if (a > b) {
		return gcd4(b, a - b);
	}
	else{
		return gcd4(a, b - a);
	}
}

int gcd5(int a, int b) {
	if (a == b) {
		return a;
	}
	int _max = max(a, b), _min = a + b - _max;
	while(_max != _min){
		int tmp1 = _max - _min, tmp2 = _min;
		_max = max(tmp1, tmp2);
		_min = tmp1 + tmp2 - _max;
	}
	return _min;
}

int gcd6(int a, int b) {
	while(a!=b){
		if (a > b) {
			a -= b;
		}
		else {
			b -= a;
		}
	}
	return a;
}

显然，更相减损法是需要考虑两个数之间的大小的，而辗转相除法不需要。

事实上，求最小公倍数可以使用分解质因数法，也可以利用最小公倍数与最大公约数之间的关系求解。

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

bool is_prime(int n){
	if (n == 2) {
		return true;
	}
	if (n % 2 == 0 || n < 2) {
		return false;
	}
	for (int i = 3; i * i <= n; i += 2) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int lcm1(int a, int b) {
	int _max = max(a, b);
	int _lcm = 1;
	for (int i = 2; i <= _max; i++) {
		if (is_prime(i)) {
			while (a % i == 0 && b % i == 0) {
				_lcm *= i;
				a /= i;
				b /= i;
			}
			while (a % i == 0){
				_lcm *= i;
				a /= i;
			}
			while (b % i == 0) {
				_lcm *= i;
				b /= i;
			}
		}
	}
	return _lcm;
}

还可以利用最大公约数求解，具体原理详见算法分析与设计第二次题解中F题的分析。

1
2
3

int lcm2(int a, int b){
	return a * b / gcd1(a, b);
}

求一个正整数的因数个数

由算术基本定理可知：每个正整数的标准分解式都是唯一的。考虑任意一个正整数\(n\)，记\(n=\displaystyle\prod_i{p_i^{\alpha_i}}\)，那么\(n\)的因数的形式必定为\(n=\displaystyle\prod_i{p_i^{\beta_i}}\)，其中，有\(0\leq\beta_i\leq\alpha_i\)。每一个质因数\(p_i\)的次数\(\beta_i\)可取\(0\)到\(\alpha_i\)，即共有\((\alpha_i+1)\)种取法，因此总的因数个数\(d(n)\)为\(d(n)=\displaystyle\prod_i({\alpha_i + 1})\)。

求 Euler 函数的值

组合数学

组合数与排列数

从\(n\)个不同元素中取出\(m\)个元素并排序，方案数为\(\displaystyle \prod_{i=n-m+1}^{n}i =\frac{n!}{(n-m)!} = \text{A}_{n}^{m}\)，其中\(\text{A}_{n}^{m}\)被称为排列数，也被记为\(\text{P}_{n}^{m}\)。

从\(n\)个不同元素中取出\(m\)个元素，两个方案视为不同当且仅当包含的元素不同，即与元素顺序无关时，方案数为\(\displaystyle\frac{A_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}=\text{C}_{n}^{m}\)。

从\(n\)个不同元素中取\(m\)个元素并排列在圆周上，其方案数显然是\(\displaystyle \frac{\text{P}_{n}^{m}}{m} = \text{Q}_n^m\)，其中\(\text{Q}_n^m\)被称为圆排列数。

常见的组合数公式以及其组合意义上的证明

考虑从\(n\)个不同元素中取\(m\)个，其方案数显然是\(\text{C}_n^m\)；此外，不妨以是否取其中某个特定元素为标准进行分类讨论，取之的方案数的\(\text{C}_{n-1}^{m-1}\)，不取的方案数为\(\text{C}_{n-1}^{m}\)，那么可以得到下面的公式。

\[\text{C}_{n}^{m}=\text{C}_{n-1}^{m-1}+\text{C}_{n-1}^{m} \tag{1}\]

事实上，公式\((1)\)可以进行推广。考虑从\(n+m\)个不同的元素中取\(r\)个，其方案数显然是\(\text{C}_{n+m}^r\)；从另外一个思路考虑，可以从\(n\)个元素和\(m\)个元素两堆中共取\(r\)个元素，根据加法原理和乘法原理总的方案数就是\(\displaystyle \sum_{i=0}^{r}\text{C}_{n}^{r-i} \text{C}_{m}^{i}\)，即：

\[\text{C}_{n+m}^{r} = \displaystyle \sum_{i=0}^{r}\text{C}_{n}^{r-i} \text{C}_{m}^{i} \tag{2}\]

据此，公式\((1)\)还可以写作\(\text{C}_{n}^{m}=\text{C}_{1}^{0}\text{C}_{n-1}^{m}+\text{C}_{1}^{1}\text{C}_{n-1}^{m-1}\)。

允许重复的组合和不相邻的组合

允许重复的组合

不相邻的组合

组合数与排列数

从\(n\)个不同元素中取出\(m\)个元素并排序，方案数为\(\displaystyle \prod_{i=n-m+1}^{n}i =\frac{n!}{(n-m)!} = \text{A}_{n}^{m}\)，其中\(\text{A}_{n}^{m}\)被称为排列数，也被记为\(\text{P}_{n}^{m}\)。

从\(n\)个不同元素中取出\(m\)个元素，两个方案视为不同当且仅当包含的元素不同，即与元素顺序无关时，方案数为\(\displaystyle\frac{A_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}=\text{C}_{n}^{m}\)。

从\(n\)个不同元素中取\(m\)个元素并排列在圆周上，其方案数显然是\(\displaystyle \frac{\text{P}_{n}^{m}}{m} = \text{Q}_n^m\)，其中\(\text{Q}_n^m\)被称为圆排列数。

常见的组合数公式以及其组合意义上的证明

考虑从\(n\)个不同元素中取\(m\)个，其方案数显然是\(\text{C}_n^m\)；此外，不妨以是否取其中某个特定元素为标准进行分类讨论，取之的方案数的\(\text{C}_{n-1}^{m-1}\)，不取的方案数为\(\text{C}_{n-1}^{m}\)，那么可以得到下面的公式。

\[\text{C}_{n}^{m}=\text{C}_{n-1}^{m-1}+\text{C}_{n-1}^{m} \tag{1}\]

事实上，公式\((1)\)可以进行推广。考虑从\(n+m\)个不同的元素中取\(r\)个，其方案数显然是\(\text{C}_{n+m}^r\)；从另外一个思路考虑，可以从\(n\)个元素和\(m\)个元素两堆中共取\(r\)个元素，根据加法原理和乘法原理总的方案数就是\(\displaystyle \sum_{i=0}^{r}\text{C}_{n}^{r-i} \text{C}_{m}^{i}\)，即：

\[\text{C}_{n+m}^{r} = \displaystyle \sum_{i=0}^{r}\text{C}_{n}^{r-i} \text{C}_{m}^{i} \tag{2}\]

据此，公式\((1)\)还可以写作\(\text{C}_{n}^{m}=\text{C}_{1}^{0}\text{C}_{n-1}^{m}+\text{C}_{1}^{1}\text{C}_{n-1}^{m-1}\)。

允许重复的组合和不相邻的组合

允许重复的组合

不相邻的组合

参考资料

• 《组合数学》第5版，清华大学出版社，卢开澄、卢华明著；
• 组合数学-21讲-上海交通大学。