专栏文章

数学章节总结

ffocalors_fontaine
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqfoem3
此快照首次捕获于
2025/12/04 04:02
3 个月前
此快照最后确认于
2025/12/04 04:02
3 个月前
查看原文

质数

质数的定义

质数(prime number)又称素数，有无限个。一个大于11的自然数，除了11和它本身外，不能被其他自然数整除;否则称为合数。根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积。

判断质数的方法

第一种：暴力筛选

思路分析

根据质数的定义，我们可以简单地想到：若要判断n是不是质数，我们可以直接写一个循环（ii从22到n\sqrt{n}，进行nn%i运算，即nn能不能被11整除，如被整除即不质数。若所有的ii都不能整除，nn即为质数）。

代码实现

CPP
bool prime(int n){
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
时间复杂度O(n)O(\sqrt{n})

第二种：埃拉托斯特尼(Eratosthenes)筛法

思路分析

创建一个比范围上限大1的数组，我们只关注下标为 1∼N1\sim N（要求的上限） 的数组元素与数组下标对应。将数组初始化为11。然后用for循环，遍历范围为：[2∼n][2\sim \sqrt{n}]。如果数组元素为11，则说明这个数组元素的下标所对应的数是质数。随后我们将这个下标（除11以外）的整数倍所对应的数组元素全部置为00，也就是判断其为非质数。这样，我们就知道了范围内(1∼(1\sim范围上限N)N)所有数是质数（下标对应的数组元素值为11）或不是质数（下标对应的数组元素值为00）

例子（N=25）

  1. 列出22以后的所有序列： 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
  2. 将序列中，划掉22的倍数，序列变成： 2 3 5 7 9 11 13 15 17 19 21 23 25
  3. 如果这个序列中最大数小于最后一个标出的质数的平方，那么剩下的序列中所有的数都是质数，否则回到第二步。
  4. 本例中，因为2525大于22的平方，我们返回第二步：
  5. 剩下的序列中第一个质数是33，将主序列中33的倍数划掉，主序列变成： 2 3 5 7 11 13 17 19 23 25
  6. 我们得到的质数有：2，3
  7. 2525仍然大于33的平方，所以我们还要返回第二步：
  8. 序列中第一个质数是55，同样将序列中55的倍数划掉，主序列成： 2 3 5 7 11 13 17 19 23
  9. 我们得到的质数有：2 3 5
  10. 因为2323小于55的平方，跳出循环。
结论：22到2525之间的质数是：2 3 5 7 11 13 17 19 23

代码实现

CPP
bool prime(int n){
	memset(v,0,sizeof v);
	for(int i=2;i<=n;i++){
		if(v[i]) continue;
		cout<<i<<endl;
		for(int j=1;j<=n/i;j++) v[i*j]=1;
	}
}
时间复杂度O(NloglogN)O(NloglogN)

第三种：线性筛选–欧拉筛法

思路分析

在埃拉托斯特尼(Eratosthenes)筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

代码实现

CPP
void prime(){
	memset(v,0,sizeof v);
	m=0;
	for(int i=2;i<=n;i++){
		if(v[i]==0){
			v[i]=i;
			prime[++m]=i;
		}
		for(int j=1;j<=m;j++){
			if(prime[j]>v[i] || prime[j]>n/i) break;
			v[i*prime[j]]=prime[j];
		}
	}
	for(int i=1;i<=m;i++) cout<<prime[i]<<endl;
}
时间复杂度O(N)O(N)

算术基本定理

任何一个大于11的正整数都能唯一分解为有限个质数的乘积，可以记作:
N=p1c1p2c2…pmcm\quad N=p_{1}^{c_{1}} p_{2}^{c_{2}} \ldots p_{m}^{c_{m}}
而其正约数集合可以记作:
{p1b1p2b2…pmbm}\quad\left\{p_{1}^{b_{1}} p_{2}^{b_{2}} \ldots p_{m}^{b_{m}}\right\} 其 中 0⩽bi⩽ci0 \leqslant b_{i} \leqslant c_{i}
其正约数个数可以记作:
(C1+1)(C2+1)(C3+1)⋯(Cm+1)=∏i=1m(Ci+1)\left(C_{1}+1\right)\left(C_{2}+1\right)\left(C_{3}+1\right) \cdots\left(C_{m}+1\right)=\prod_{i=1}^{m}\left(C_{i}+1\right)
其正约数之和可以记作:
(1+p1+p12+⋯+p1c1)⋯(1+pm1+pm2+⋯+pmcm)=∏i=1m(∑j=0ci(pi)j)\quad\left(1+p_{1}+p_{1}^{2}+\cdots+p_{1}^{c_{1}}\right) \cdots\left(1+p_{m}^{1}+p_{m}^{2}+\cdots+p_{m}^{cm}\right)=\prod_{i=1}^{m}\left(\sum_{j=0}^{c_{i}}\left(p_{i}\right)^{j}\right)

阶乘中因子出现的次数

假如现在要求 20!20!
存在 22 的有： 2 4 6 8 10 12 14 16 18 20 共有1010 个
部分数还有：4 8 12 16 20共有 55 个。 发现还有： 8 16 再记录 22 个。
最后 16 还有 11 个。
所以最后就有 10+5+2+1=18 个。
也就是说，我们如果将这样的行为用公式表示。可以总结出： 如果要求 n!n!中因子 xx 的出现次数，那 xx 就出现了
⌊nx⌋+⌊nx2⌋+⌊nx3⌋+…+⌊nxm⌋\left\lfloor\frac{n}{x}\right\rfloor+\left\lfloor\frac{n}{x^{2}}\right\rfloor+\left\lfloor\frac{n}{x^{3}}\right\rfloor+\ldots+\left\lfloor\frac{n}{x^{m}}\right\rfloor 次。

约数

约数的定义

若整数nn除以整数dd的余数为00，即dd能整除nn，则称dd是nn的约数，nn是dd的倍数，记为d∣nd|n

求正约数集合的方法

第一种:试除法

适用于单个正整数求正约数集合

思路分析

若d≥Nd≥\sqrt{N}是NN的约数，则Nd≤N\frac{N}{d} ≤\sqrt{N}也是NN的约数。所以我们可以说约束总是成对出现的(完全平方数中N\sqrt{N}会单独出现)
所以我们只需要扫描d=1∼Nd=1\sim \sqrt{N}，尝试dd是否能整除NN，若能整除，则Nd\frac{N}{d} 也是NN的约数。

代码实现

CPP
for(int i=1;i*i<=n;i++){
	if(n%i==0){
		factor[++m]=i;
		if(i!=n/i) factor[++m]=n/i;
	}
}
for(int i=1;i<=m;i++){
	cout<<factor[i]<<endl;
}

第二种:倍数法

适用于求1−N1-N每个数的正约数集合

思路分析

若再次采用上述的试除法的思路来完成的话，那么时间复杂度将会来到惊人的O(NN)O(N\sqrt{N})
所以我们可以反过来思考，对于每个数dd，1∼N1\sim N中以dd为约数的数就是dd的倍数

代码实现

CPP
vector<int> factor[500010];
for(int i=1;i<=n;i++){
	for(int j=1;j>=n/i;j++){
		factor[i*j].push_back(i);
	}
} 
for(int i=1;i<=n;i++){
	for(int j=0;j<factor[i].size();j++){
		cout<<factor[i][j]<<" "; 
	}
}

取模的性质

a%b=a−b×⌊ab⌋a \% b=a-b\times\left \lfloor \frac{a}{b} \right \rfloor

最大公约数

定义

若自然数dd同时是自然数aa和bb的约数，曾称dd是aa和bb的公约数。在所有aa和bb的公约数中最大的一个，称为aa和bb的最大公约数，记为gcd(a,b)gcd(a,b)
若自然数dd同时是自然数aa和bb的倍数，曾称dd是aa和bb的公倍数。在所有aa和bb的公倍数中最小的一个，称为aa和bb的最小公倍数，记为lcm(a,b)lcm(a,b)

性质

∀a,b∈N∀a,b\in \mathbb{N} gcd(a,b)×lcm(a,b)=a×bgcd(a,b) \times lcm(a,b)=a \times b
证明: 设d=gcd(a,b)d=gcd(a,b),a0=ada_0=\frac{a}{d} b0=bdb_0=\frac{b}{d} 根据最大公约数的定义，gcd(a0,b0)=1gcd(a_0,b_0)=1
根据最小公倍数的性质，lcm(a0,b0)=a×blcm(a_0,b_0)=a \times b
所以则有lcm(a,b)=lcm(a0×d,b0×d)=lcm(a0,b0)×d=a0×b0×d=a×bdlcm(a,b)=lcm(a_0 \times d,b_0 \times d)=lcm(a_0,b_0)\times d=a_0\times b_0\times d=\frac{a\times b}{d}
证毕

求最大公约数的方法

第一种:暴力出奇迹

从大到小暴力枚举。
最坏复杂度O(n)O(n)

第二种:辗转相除法

gcd(a,b)=gcd(a,a%b)gcd(a,b)=gcd(a,a\%b)
可以使用递归求解
时间复杂度O(log(a+b))O(log(a+b))

第三种:更相减损术

如果 a≥ba≥b，则有 gcd(a,b)=gcd(b,a−b)=gcd(a,a−b)gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)
时间复杂度通常由 aa和bb决定

第四种:二进制法

如果a,ba,b 大到需要使用高精度时，因为高精度取模不容易实现，所以考虑使用更相减损术的一个扩展方法。
我们可以先讨论a,ba,b 的奇偶性。如果是两个奇数，更相减损一次，如果是一奇一偶，偶数÷2÷2，否则均÷2÷2，结果×2×2

互质和欧拉函数

定义

∀a,b∈N\forall a, b \in \mathbb{N} ，若 gcd⁡(a,b)=1\operatorname{gcd}(a, b)=1 ，则称 a,ba, b 互质。 对于三个数或更多个数的情况，我们把 gcd⁡(a,b,c)=1 \operatorname{gcd}(a, b, c)=1 的情况称为 a,b,ca, b, c 互质。

欧拉函数

1～N1～N 中与 NN 互质的数的个数被称为欧拉函数，记为 φ(N)\varphi(N) 。
我们可以将其应用在唯一分解定理中，N=p1c1p2c2⋯pmcmN=p_{1}{ }^{c_{1}} p_{2}{ }^{c_{2}} \cdots p_{m}{ }^{c_{m}} ，则：
φ(N)=N×p1−1p1×p2−1p2×⋯×pm−1pm=N×∏质数 p∣N(1−1p)\varphi(N)=N \times \frac{p_{1}-1}{p_{1}} \times \frac{p_{2}-1}{p_{2}} \times \cdots \times \frac{p_{m}-1}{p_{m}}=N \times \prod_{\text {质数 } p \mid N}\left(1-\frac{1}{p}\right)
证明：
设 p p 是 NN 的质因子， 1∼N1 \sim N 中 p 的倍数有 p,2p,3p,⋯ ,(Np)×pp, 2 p, 3 p, \cdots,(\frac{N}{p} ) \times p ，共 Np\frac{N}{p} 个。
同理，若 qq 也是 NN 的质因子，则 1∼N1 \sim N 中 qq 的倍数有 Np\frac{N}{p} 个。
如果我们把这 Np+Np\frac{N}{p} +\frac{N}{p} 个数去掉，那么 p×qp \times q 的倍数被排除了两次，通过容斥原理，我们需要加回来一次。
因此，1∼N 1 \sim N 中不与 NN 含有共同质因子 pp 或 qq 的数的个数为：
N−Np−Nq+Npq=N×(1−1p−1q+1pq)=N(1−1p)(1−1q)N-\frac{N}{p}-\frac{N}{q}+\frac{N}{p q}=N \times \left(1-\frac{1}{p}-\frac{1}{q}+\frac{1}{p q}\right)=N\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right)
证毕。

性质1～21～2

1． ∀n>1,1∼n\forall n>1,1 \sim n 中与 n n 互质的数的和为 n×φ(n)2\frac{n \times \varphi(n)}{2} 。
2．若 a,ba, b 互质，则
φ(ab)=φ(a)φ(b)\varphi(a b)=\varphi(a) \varphi(b) 。
证明：
因为 gcd⁡(n,x)=gcd⁡(n,n−x)\operatorname{gcd}(n, x)=\operatorname{gcd}(n, n-x) ，所以与 n n 不互质的数 xx, n−xn-x 成对出现，平均值为 n2\frac{n}{2} 。因此，与n n 互质的数的平均值也是 n2\frac{n}{2} ，进而得到性质 11 。
根据欧拉函数的计算式，对 a,ba, b 分解质因数，直接可得性质22。
证毕。

积性函数

如果当 a,ba, b 互质时，有 f(ab)=f(a)×f(b) f(a b)=f(a) \times f(b) ，那么称函数 ff 为积性函数。

性质3～63～6

3．若 ff 是积性函数，且在算术基本定理中 n=∏i=1mpicin=\prod_{i=1}^{m} p_{i}^{c_{i}} ，则 f(n)=∏i=1mf(pici)f(n)=\prod_{i=1}^{m} f\left(p_{i}^{c_{i}}\right) 。
4．设 pp 为质数，若 p∣np \mid n 且 p2∣np^{2} \mid n ，则 φ(n)=φ(np)×p\varphi(n)=\varphi(\frac{n}{p} ) \times p 。
5．设 pp 为质数，若 p∣np \mid n 但 p2∤np^{2} \nmid n ，则φ(n)=φ(np)×(p−1) \varphi(n)=\varphi(\frac{n}{p} ) \times (p-1)。
6．∑d∣nφ(d)=n\sum_{d \mid n} \varphi(d)=n
证明： 把 nn 分解质因数，按照积性函数的定义，性质 33 一眼成立。
若 p∣np \mid n 且p2∣n p^{2} \mid n ，则 n,npn, \frac{n}{p} 包含相同的质因子，只是 p p 的指数不同。直接把φ(n)与φ(np) \varphi(n) 与 \varphi(\frac{n}{p} ) 。
φ(n)=n×(1−1p1)×(1−1p2)×(1−1p3)×⋯×(1−1pm)\varphi(n)=n \times (1 - \frac{1}{p_1})\times (1 - \frac{1}{p_2})\times (1 - \frac{1}{p_3}) \times \cdots\times (1 - \frac{1}{p_m})
φ(n)=np×(1−1p1)×(1−1p2)×(1−1p3)×⋯×(1−1pm)\varphi(n)=\frac{n}{p}\times (1 - \frac{1}{p_1})\times (1 - \frac{1}{p_2})\times (1 - \frac{1}{p_3}) \times \cdots\times (1 - \frac{1}{p_m})
二者相除，商为 p p ，所以性质 44 成立。
若 p∣np \mid n 但 p2∤np^{2} \nmid n ，则p p, np\frac{n}{p} 互质，由 φ\varphi 是积性函数得 φ(n)=φ(np)∗φ(p)\varphi(n)=\varphi(\frac{n}{p} ) * \varphi(p) ，而φ(p)=p−1 \varphi(p)=p-1 ，所以性质 55 成立。
设 f(n)=∑d∣nφ(d)f(n)=\sum_{d \mid n} \varphi(d) 。用乘法分配律展开比较，再利用 φ\varphi 是积性函数，得到：若 n, m 互质，则 f(nm)=∑d∣nmφ(d)=(∑d∣nφ(d))×(∑d∣mφ(d))=f(n)×f(m)f(n m)=\sum_{d \mid n m} \varphi(d)=\left(\sum_{d \mid n}\varphi(d)\right) \times \left(\sum_{d \mid m} \varphi(d)\right)=f(n) \times f(m) 。
即 ∑d∣nφ(d) \sum_{d \mid n} \varphi(d) 是积性函数。
对于单个质因子 f(pm)=∑d∣pmφ(d)=φ(1)+φ(p)+φ(p2)+⋯+φ(pm)f\left(p^{m}\right)=\sum_{d \mid p^{m}} \varphi(d)=\varphi(1)+\varphi(p)+ \varphi\left(p^{2}\right)+\cdots+\varphi\left(p^{m}\right) 是一个等比数列求和再加 11 ，结果为 pmp^{m} 。所以 f(n)=∏i=1mf(pici)=∏i=1mpici=n f(n)= \prod_{i=1}^{m} f\left(p_{i}^{c_{i}}\right)=\prod_{i=1}^{m} p_{i}^{c_{i}}=n ，性质 66 成立。
证毕。

同余

同余的定义

若整数 aa 和整数 bb 除以正整数 mm 的余数相等，则称 a,ba, b 模 mm 同余，记为 a≡b( mod m)a \equiv b(\bmod m) 。

同余类与剩余系

对于 ∀a∈[0,m−1]\forall a \in[0, m-1] ，集合 {a+km}(k∈Z)\{a+k m\}(k \in \mathbb{Z}) 的所有数模 m m 同余，余数都是 aa 。该集合称为一个模 mm 的同余类，简记为 aˉ\bar{a} 。
不难发现模 mm 的同余类一共有 mm 个，分别为 0‾,1‾,2‾,⋯ ,m−1‾\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{m-1} 。它们构成 mm 的完全剩余系。
1～m1～ m 中与 mm 互质的数代表的同余类共有 φ(m)\varphi(m) 个，它们构成 mm 的简化剩余系。例如，模 1010 的简化剩余系为 {1‾,3‾,7‾,9‾}\{\overline{1}, \overline{3}, \overline{7}, \overline{9}\} 。
简化剩余关于模 mm 乘法封闭。这是因为若 a,b(1≤a,b≤m)a, b(1 \leq a, b \leq m) 与 mm 互质，则 a×ba \times b 也不可能与 mm 含在相同的质因子，即 a×ba \times b 也与 mm 互质。再由余数的定义即可得到 a×b mod ma \times b \bmod m 也与 mm 互质，即 a×b mod ma \times b \bmod m 也属于 mm 的简化剩余系。

欧拉定理

若正整数 a,na, n 互质，则 aφ(n)≡1( mod n)a^{\varphi(n)} \equiv 1(\bmod n)
证明：
设 nn 的简化剩余系为 {a1‾,a2‾,⋯ ,aφ(n)‾} \left\{\overline{a_{1}}, \overline{a_{2}}, \cdots, \overline{a_{\varphi(n)}}\right\} 。
对 ∀ai,aj\forall a_{i}, a_j ，若 a×ai≡a×aj( mod n)a \times a_{i} \equiv a \times a_{j}(\bmod n) ，则 a×(ai−aj)≡0a \times \left(a_{i}-a_{j}\right) \equiv 0 。
因为 a,na, n 互质，所以 ai−aj≡0a_{i}-a_{j} \equiv 0 ，即 ai≡aja_{i} \equiv a_{j} 。
所以 ai≠aja_{i} \neq a_{j} 时， aai,aaja a_{i}, a a_{j} 也代表不同的同余类。
又因为简化同余系关于模 n n 乘法封闭，故 aai‾\overline{a a_{i}} 也在简化剩余系集合中。因此，集合 {a1‾,a2‾,⋯ ,aφ(n)‾}\left\{\overline{a_{1}}, \overline{a_{2}}, \cdots, \overline{a_{\varphi(n)}}\right\} 与 集合 {aa1‾,aa2‾,⋯ ,aaφ(n)‾}\left\{\overline{a a_{1}}, \overline{a a_{2}}, \cdots, \overline{a a_{\varphi(n)}}\right\} 都能表示 nn 的简化剩余系。
所以aφ(n)a1a2⋯aφ(n)≡(aa1)(aa2)⋯(aaφ(n))≡a1a2⋯aφ(n)( mod n)a^{\varphi(n)} a_{1} a_{2} \cdots a_{\varphi(n)} \equiv\left(a a_{1}\right)\left(a a_{2}\right) \cdots\left(a a_{\varphi(n)}\right) \equiv a_{1} a_{2} \cdots a_{\varphi(n)}(\bmod n)
因此aφ(n)≡1( mod n)a^{\varphi(n)} \equiv 1(\bmod n) 。
证毕。

费马小定理

若 pp 是质数，则对于任意整数 aa ，有 ap≡a( mod p)a^{p} \equiv a(\bmod p) 。
对于费马小定理我们可以直接通过欧拉定理来证明
证明过程参照裴蜀定理。

裴蜀定理

对于任意整数 a,ba, b ，存在一对整数 x,yx, y ，满足 ax+by=gcd⁡(a,b)a x+b y=\operatorname{gcd}(a, b) 。
证明：
在欧几里得算法的最后一步，即 b=0b=0 时，显然有一对整数 x=1,y=0x=1, y=0 ，使得 a×1+0×0=gcd⁡(a,0)a \times 1+0 \times 0=\operatorname{gcd}(a, 0) 。
若 b>0b>0 ，则 gcd⁡(a,b)=gcd⁡(b,a mod b)\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a \bmod b) 。
假设存在一对整数 x,yx, y ，满足 b×x+(a mod b)×y=gcd⁡(b,a mod b)b \times x+ (a \bmod b) \times y=\operatorname{gcd}(b, a \bmod b) ，
因为 bx+(a mod b)y=bx+(a−b⌊ab⌋)y=ay+b(x−⌊ab⌋y)b x+(a \bmod b) y=b x+(a-b\lfloor \frac{a}{b} \rfloor) y=a y +b(x-\lfloor \frac{a}{b} \rfloor y) ，
所以令 x′=y,y′=x−⌊ab⌋yx^{\prime}=y, y^{\prime}=x-\lfloor \frac{a}{b} \rfloor y ，
我们就得到了 ax′+by′=gcd⁡(a,b)a x^{\prime}+b y^{\prime}=\operatorname{gcd}(a, b) 。
证毕。
所以，只要 aa 不是 pp 的倍数，就有 ap−1≡1( mod p)a^{p-1} \equiv 1(\bmod p) ，两边同乘 aa 就是费马小定理。
证毕。

矩阵乘法与高斯消元

条件

  • 矩阵 AA 的列数必须等于矩阵 BB 的行数。
  • 如果 AA 是一个 n×mn \times m 的矩阵， BB 必须是一个 m×pm \times p 的矩阵。
  • 结果矩阵 CC 的维度为 n×pn \times p 。

定义

矩阵 A(n×m)A(n \times m) 和矩阵 B(m×p)B(m \times p) 的乘积 C(n×p)C(n \times p) 定义为：
Ci,j=∑k=1mAi,k×Bk,jC_{i, j}=\sum_{k=1}^{m} A_{i, k} \times B_{k, j}
其中：
  • Ci,jC_{i, j} 是结果矩阵 CC 的第 ii 行第 j j 列的元素。
  • Ai,kA_{i, k} 是矩阵 AA 的第 ii 行第 kk 列的元素。
  • Bk,jB_{k, j} 是矩阵 BB 的第 kk 行第 jj 列的元素。

意义

矩阵相乘的定义来源于实际问题的需求。例如：
  • 方程组求解：线性方程组可以表示为矩阵形式Ax=B Ax=B ，其中 AA 是系数矩阵， xx是未知数向量， BB 是常数向量。矩阵相乘用于表示方程组的线性组合，在接下来的总结中，会详细讲到。
  • 数据分析：在机器学习中，矩阵相乘用于表示特征和权重的线性组合。
矩阵相乘满足线性代数中我们所说的运算律
  • 结合律： (A×B)×C=A×(B×C)(A \times B) \times C=A \times(B \times C) 。
  • 分配律： A×(B+C)=A×B+A×CA \times(B+C)=A \times B+A \times C 。 我们实现矩阵乘法的代码如下：
CPP
struct matrix{
	int a[101][101];
	matrix(){
		memset(a,0,sizeof a);
	}
};
matrix operator * (const matrix &A,const matrix &B){
	matrix c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				c.a[i][j]=(c.a[i][j]+A.a[i][k]*B.a[k][j])%M;
			}
		}
	}
	return c;
}

矩阵快速幂

还是上面的例子，虽然 [1221]3\left[\begin{array}{ll}1 & 2 \\ 2 & 1\end{array}\right]^{3} 并不难算。但是计算 [1221]108\left[\begin{array}{ll}1 & 2 \\ 2 & 1\end{array}\right]^{10^{8}} 的时候，这就已经跑不动了。因为矩阵乘法本身就有一个 O(nmk)O(n m k) ，导致他会有一个 O(8)O(8) 的常数。
证明矩阵快速幂可行性，等价于需要证明出在矩阵中的 A×B×C=A×(B×C)A \times B \times C=A \times(B \times C) ，而这就是结合律，是显然得到的。
代码如下：
CPP
while(k){
	if(k&1) ans=ans*a;
	a=a*a;
	k>>=1;
}

高斯消元法求解方程组

在解决这个问题之前我们先引入增广矩阵和矩阵的初等行变换的概念

增广矩阵

增广矩阵就是在系数矩阵的右边添上一列，这一列是方程组的等号右边的值
例如：
[a11a12a13⋯a1nb1a21a22a23⋯a2nb2⋮⋮⋮⋮⋮an1an2an3⋯annbn]\left[\begin{array}{cccccc} a_{11} & a_{12} & a_{13} & \cdots & a_{1 n} & b_{1} \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2 n} & b_{2} \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ a_{n 1} & a_{n 2} & a_{n 3} & \cdots & a_{n n} & b_{n} \end{array}\right]

矩阵的初等行变换

  • 交换两行
  • 把某一行乘一个非 0 的数
  • 把某行的若干倍加到另一行上去 高斯消元的步骤与我们平常求解多元一次方程组的方法一样，举个例子：
我们有二元一次方程组 {2x+3y=403x+2y=45\left\{\begin{array}{llll} 2x + 3y=40 \\ 3x + 2y=45 \\ \end{array}\right.
首先我们将一式的主元xx的系数先化为11,则有x+1.5y=20x + 1.5y=20
对于电脑我们可以使用doubledouble类型进行存储
然后我们将这个化简完的一式与二式做差得到2.5y=152.5y = 15 解出来就可以得到方程组的解{x=11y=6\left\{\begin{array}{llll} x=11 \\ y=6 \\ \end{array}\right.
我们将上述的方法稍作总结可以得到：
方程组初始的形式
[x1,1x1,2…x1,n∣x1,n+1x2,1x2,2…x2,n∣x2,n+1…xn,1xn,2…xn,n∣xn,n+1]\left[\begin{array}{cccccc} x_{1,1} & x_{1,2} & \ldots & x_{1, n} \mid x_{1, n+1} \\ x_{2,1} & x_{2,2} & \ldots & x_{2, n} \mid x_{2, n+1} \\ \ldots & & & \\ x_{n, 1} & x_{n, 2} & \ldots & x_{n, n} \mid x_{n, n+1} \end{array}\right]
方程组结束的形式
[x1,1′x1,2′…x1,n′∣x1,n+1′0x2,2′…x2,n′∣x2,n+1′…00…xn,n′∣xn,n+1′]\left[\begin{array}{cccccc} x_{1,1}^{\prime} & x_{1,2}^{\prime} & \ldots & x_{1, n}^{\prime} \mid x_{1, n+1}^{\prime} \\ 0 & x_{2,2}^{\prime} & \ldots & x_{2, n}^{\prime} \mid x_{2, n+1}^{\prime} \\ \ldots & & & \\ 0 & 0 & \ldots & x_{n, n}^{\prime} \mid x_{n, n+1}^{\prime} \end{array}\right] 按照上面的推导过程，我们不难得到以下实现代码：

高斯消元法

CPP
bool guass(){
	for(int i=1;i<=n;i++){
		for(int k=i;k<=n;k++){
			if(fabs(a[k][i])>eps){
				swap(a[i],a[k]);
				break;
			}
		}
		if(fabs(a[i][i])<eps) return 0;
		for(int j=n+1;j>=1;j--) a[i][j]/=a[i][i];
		for(int k=i+1;k<=n;k++){
			for(int j=n+1;j>=i;j--) a[k][j]-=a[i][j]*a[k][i];
		}
	}
	for(int i=n-1;i>=1;i--){
		for(int j=i+1;j<=n;j++) a[i][n+1]-=a[i][j]*a[j][n+1];
	}
	return 1;
}

组合计数基础

加法原理

若完成一件事情的方法共有nn类，其中第ii个步骤有aia_i种完成方法，并且这些方法都不重合，则完成这件事情的方法一共有a1+a2+⋯+ana_1+ a_2 + \dots + a_n种，我们称这个为加法原理。

乘法原理

若完成一件事情的方法共有nn类，其中第ii个步骤有aia_i种完成方法，并且这些方法都互相之间没有干扰，则完成这件事情的方法一共有a1×a2×⋯×ana_1\times a_2 \times \dots \times a_n种，我们称这个为乘法原理。

排列数

从 nn 个不同元素中依次取出 mm 个元素排成一列，产生的不同排列的数量为：
Anm=n!(n−m)!=n×(n−1)×⋯×(n−m+1)A_{n}^{m}=\frac{n!}{(n-m)!}=n \times(n-1) \times \cdots \times(n-m+1)

组合数

从 nn 个不同元素中取出 mm 个组成一个集合，产生的不同集合数量为：
Cnm=n!m!(n−m)!=n×(n−1)×⋯×(n−m+1)m×(m−1)×⋯×2×1C_{n}^{m}=\frac{n!}{m!(n-m)!}=\frac{n \times(n-1) \times \cdots \times(n-m+1)}{ m\times(m-1) \times \cdots \times2 \times 1}
我们发现排列数和组合数只有分母上有一个m!m!的差别因为组合数是不考虑顺序的，相对于排列数来说会有m!m!个重复的方法，所以我们需要除以m!m!

性质

  1. Cnm=Cnn−mC_{n}^{m}=C_{n}^{n-m}
  2. Cnm=Cn−1m+Cn−1m−1C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}
  3. Cn0+Cn1+Cn2+⋯+Cnn=2nC_{n}^{0}+C_{n}^{1}+C_{n}^{2}+ \cdots+C_{n}^{n}=2^{n}
  4. Cn0=Cnn=1 C_{n}^{0}=C_{n}^{n} = 1
  5. Cnm=n×(n−1)×⋯×(n−m+1)m!C_{n}^{m}= \frac{n \times(n-1) \times \cdots \times(n-m+1)}{m!}
证明：
性质1:
将性质1代入公式，发现等式恒成立，两边都为n!m!(n−m)!\frac{n!}{m!(n-m)!}
性质2:
从 nn 个不同元素中取出 mm 个组成一个集合有两类方法：取 nn 号元素，不取 nn 号元素。若取 nn 号元素，则应在剩余 n−1n-1 个元素中选出 m−1m-1 个，有 Cn−1m−1C_{n-1}^{m-1} 种取法。若不取 nn 号元素，则应在剩余 n−1n-1 个元素中选出 m 个，有 Cn−1mC_{n-1}^{m} 种取法。再根据加法原理，即可证明。
性质3:
我们可以将等式左边理解为一种包含了选和不选全部方案的写法，而等式右边则是另外一种相同意义的方法。即可证得。
性质4:
在nn种方案中全部选取和全部不选取都是一种方案。
性质5:
根据组合数和排列数的关系可以知道Cnm=Anmm!C_{n}^{m}= \frac{ A_{n}^{m} }{m!}，而Anm=n×(n−1)×⋯×(n−m+1)A_{n}^{m}=n \times(n-1) \times \cdots \times(n-m+1)这是上面排列数的定义由来的，将上述的第一个等式中的AnmA_{n}^{m}替换成n×(n−1)×⋯×(n−m+1)n \times(n-1) \times \cdots \times(n-m+1)即可证明此性质。

组合数的求法

根据性质 2，用递推法可求出 0≤y≤x≤n0 \leq y \leq x \leq n 的所有组合数 CxyC_{x}^{y} ，复杂度 O(n2)O\left(n^{2}\right) 。
代码如下:
CPP
void get(){
	for(int i=0; i<N; i++) C[i][0] = 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])%P; 
		}
	}
}
组合数的结果一般较大，若题目要求出 CnmC_{n}^{m} 对一个数 pp 取模后的值，并且 1∼n1 \sim n 都存在模 p 乘法逆元，则可以先计算分子 n! mod pn!\bmod p ，再计算分母 m!(n−m)! mod pm!(n-m)!\bmod p 的逆元，乘起来得到 Cnm mod pC_{n}^{m} \bmod p ，复杂度为O(n)O\left(n\right) 。
代码如下:
CPP
f[0]=g[0]=1;//f[i]表示i的阶乘，g[i]表示i逆元的阶乘
for(int i=1;i<N;i++){
	f[i]=f[i-1]*i%P;
	g[i]=qsm(f[i],P-2)%P;
}

二项式定理

(a+b)n=∑k=0nCnkakbn−k(a+b)^{n}=\sum_{k=0}^{n} C_{n}^{k} a^{k} b^{n-k}

意义

在二项式展开中，组合数CnkC_{n}^{k}的含义是： 从 nn个因子a+ba+b中，选取 kk个bb ，其余 n−kn-k个选择aa的方式有多少种。 这正是组合数的定义。

Lucas 定理

若 pp 是质数，则对于任意整数 1≤m≤n1 \leq m \leq n ，有：
Cnm≡Cn mod pm mod p×Cn/pm/p( mod p)C_{n}^{m} \equiv C_{n \bmod p}^{m \bmod p} \times C_{n / p}^{m / p}(\bmod p)
也就是把 nn 和 mm 表示成 pp 进制数，对 pp 进制下的每一位分别计算组合数，最后再乘起来。
证明等学了生成函数以后再来补上。
Lucas 算法主要应用于mm和nn很大，但是pp很小的情况，不然相对于原来的处理方式没有变化。
代码如下：
CPP
int a[1000001];
int pow(int a,int k,int p){
	int ans=1;
    while(k){
		if(k&1) ans=(ans*a)%p;
		a=(a*a)%p;
		k>>=1;
	}
    return ans%p;
}
int C(int n,int m){
    if(m>n) return 0;
    return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
}
int Lucas(int n,int m){
    if(!m) return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}
void solve(){
	int n,m;
	cin>>n>>m>>p;
	a[0]=1;
	for(int i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;
	cout<<Lucas(n,m)<<endl;
}

容斥原理

为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把答案计算出来，然后再把重复计算的数目排斥出去，这种计数的方法称为容斥原理。——度娘
看起来确实很高端，但是，我们有一个十分简单的理解方法去理解这个这个原理。
举个例子：
求 11 到 nn 中能被 33 或 55 或 77 整除的数。
这道题我们首先需要在11到nn中先筛选能被 33 或 55 或 77 整除的数，但是如果这样就结束的话，显然像1515和2121和3535这样的数是被算了两次的，像105105甚至我们算了三次，这样肯定不是正确的。
我们需要县减去1515和2121和3535再加上105105就可以得到正确的答案。
这就是容斥原理，其实理解起来不难。
我们想要的是上面这张图里全部的信息。
但是我们发现，电脑无法一下实现，所以我们决定先给它传入 A,B,CA,B,C，把这些加起来，再减去 A⋂BA\bigcap B ,A⋂CA\bigcap C 和 B⋂CB\bigcap C 。
这个时候，我们又发现，中间的 A⋂B⋂CA\bigcap B \bigcap C 被多减去了一次，所以加回来。
这也就完成了上面我们举的例子的步骤。
在信息学中，使用容斥原理需要注意的是以下几点：
初始答案
状态设计
容斥方法
其实思路都是和数学上的差不了多少。
对于 +−+-，直接判断奇偶性即可。
奇数 −-，偶数 ++。

莫比乌斯函数

设正整数 NN 按照算术基本定理分解质因数为 N=p1c1p2c2⋯pmcmN=p_{1}^{c_{1}} p_{2}^{c_{2}} \cdots p_{m}^{c_{m}} ，定义函数
μ(N)={0∃i∈[1,m],ci>11m≡0( mod 2),∀i∈[1,m],ci=1−1m≡1( mod 2),∀i∈[1,m],ci=1\mu(N)=\left\{\begin{array}{cc} 0 & \exists i \in[1, m], c_{i}>1 \\ 1 & m \equiv 0(\bmod 2), \forall i \in[1, m], c_{i}=1 \\ -1 & m \equiv 1(\bmod 2), \forall i \in[1, m], c_{i}=1 \end{array}\right.
称 μ(N)\mu(N) 为Mo¨biusMöbius 函数（莫比乌斯函数）。
通俗地讲，当 NN 包含相等的质因子时， μ(N)=0\mu(N)=0 。
当 NN 的所有质因子各不相等时：
若 NN 有偶数个质因子， μ(N)=1\mu(N)=1 。
若 NN 有奇数个质因子， μ(N)=−1\mu(N)=-1 。
也就是说，我们可以通过莫比乌斯函数记录当前节点对结果的影响是怎样。
也就是说，如果 μ(N)=0\mu(N)=0，根本无法构造，μ(N)=1\mu(N)=1 时为正，μ(N)=−1\mu(N)=-1 时为负。
和欧拉函数一样，它们都属于积性函数，所以我们可以和欧拉函数一样使用欧拉筛把莫比乌斯函数筛出来。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
int prime[maxn],cnt;int mu[maxn];
bitset<maxn> vis;
void Init(int N){
	mu[1]=1;
	for(int i=2;i<=N;++i){
		if(!vis[i]) prime[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&i*prime[j]<=N;++j){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
			mu[i*prime[j]]=mu[i]*-1;
		}
	}
}
int t,a,b,d;
int main(){
	Init(5e4);
	for(int i=1;i<=1000;i++){
        cout<<i<<" "<<mu[i]<<endl;
    }
	return 0;
}
其实这个章节本该还有莫比乌斯反演的，但是郭总说需要和后面的知识相互配合着学习，所以莫比乌斯反演这一段先放着，等学完之后在来完工

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...