4. 基础数学初识
4.1 质数
概念
4.1.1 试除法判定质数
思想
- \(N<2\)不是质数。
- 从\(i=2\)开始枚举，直到\(\sqrt{n}\)，若\(i\)能被\(N\)整除，说明不是质数；否则为质数。
模板
C++ 模板
bool is_prime(int n) {
if (n < 2) return 0; // 若小于2直接返回false
for (int i = 2; i <= n / i; i++) { // 优化为sqrt(n)
if (n % i == 0) return 0;
}
return 1;
}例题 866. 试除法判定质数
描述
给定 n 个正整数 ai，判定每个数是否是质数。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式 共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。
数据范围 1≤n≤100, 1≤ai≤2^31−1
输入样例：
2
2
6输出样例：
Yes
No代码
#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n) {
if (n < 2) return 0;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) return 0;
}
return 1;
}
int main() {
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
if (is_prime(x)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}4.1.2 分解质因数
概念
思想
- 算术基本定理：任何一个大于 \(1\) 的自然数 \(N\)，如果 \(N\) 不为质数，
- 那么 \(N\) 可以唯一分解成有限个质数的乘积 \(N=p_1^{a_1}\times p_2^{a_2}\dots\times p_k^{a_k}\)，且最多只有一个大于 \(\sqrt{N}\) 的质因子。
- 这里 \(p_1<p_2<p_3\dots<p_k\) 均为质数，其中指数 \(a_1, a_2, \dots, a_k\) 是正整数。
模板
#include <bits/stdc++.h>
using namespace std;
map<int, int> primes; // 存储质因子底数和其指数的映射
void get_div(int n) {
primes.clear(); // 清空数据
for (int i = 2; i <= n / i; i++) { // 从2开始枚举质因子
if (n % i == 0) { // 当其为质因子时
while (n % i == 0) {
primes[i]++; // 指数增加
n /= i;
}
}
}
if (n > 1) primes[n]++; // 剩余的数大于1则为最后的质因子
}例题 867. 分解质因数
描述
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式 对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。
每个正整数的质因数全部输出完毕后，输出一个空行。
数据范围 1≤n≤100, 2≤ai≤2×10^9
输入样例：
2
6
8输出样例：
2 1
3 1
2 3代码
#include <bits/stdc++.h>
using namespace std;
map<int, int> primes;
void get_div(int n) {
primes.clear();
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
while (n % i == 0) {
primes[i]++;
n /= i;
}
}
}
if (n > 1) primes[n]++;
}
int main() {
int n;
cin >> n;
while (n--) {
int a;
cin >> a;
get_div(a);
for (auto &p : primes) {
cout << p.first << " " << p.second << endl;
}
cout << endl;
}
return 0;
}4.1.3 筛质数（线性筛）
模板
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int cnt; // 记录质数个数
int primes[N]; // 存储当前筛选出的质数
bool vis[N]; // 标记是否被筛掉
void get_primes(int n) {
for (int i = 2; i <= n; i++) { // 外层从2~n迭代
if (!vis[i]) primes[cnt++] = i; // 没被筛掉说明是质数，记录到primes[]中
for (int j = 0; primes[j] <= n / i; j++) { // 将1~n范围内质数primes[j]的i倍的合数筛掉
vis[primes[j] * i] = 1; // 用最小质因子primes[j]筛掉合数
if (i % primes[j] == 0) break;
}
}
}
// 例题 868. 筛质数
int main() {
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}4.2 约数
概念
- 约数，又称因数。整数\(a\)除以整数\(b(b≠0)\) 除得的商正好是整数而没有余数，我们就说\(a\)能被\(b\)整除，或\(b\)能整除\(a\)。\(a\)称为\(b\)的倍数，\(b\)称为\(a\)的约数。
4.2.1 试除法求约数
思想
- 从\(i=1\)开始枚举到\(\sqrt{N}\)
- \(i\)和\(\frac{N}{i}\)即为\(N\)的约数
模板
const int N=1e6+3;
int res[N]; // 存储约数
int cnt; // 记录数量
void get_div(int n){
cnt=0; // 初始化
for(int i=1;i<=n/i;i++){ // 从1开始枚举
if(n%i==0){
res[cnt++]=i; // 将i作为约数
if(i!=n/i) res[cnt++]=n/i; // 将n/i作为约数
}
}
sort(res, res+cnt); // 将约数从小到大排序
}例题 869. 试除法求约数
描述
给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。
输入格式 第一行包含整数 n。
接下来 n 行，每行包含一个整数 ai。
输出格式
输出共 n 行，其中第 i 行输出第 i 个整数 a_i 的所有约数。
数据范围
1 ≤ n ≤ 100, 2 ≤ a_i ≤ 2 × 10^9
输入样例：
2
6
8输出样例：
1 2 3 6
1 2 4 8代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 试除法求n的所有约数，存入res数组，并返回约数个数
vector<int> get_divisors(int n) {
vector<int> res;
// i*i <= n 避免开方和溢出，效率等价于 i <= n/i
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);
}
}
}
sort(res.begin(), res.end());
return res;
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
vector<int> divs = get_divisors(x);
for (int d : divs) {
cout << d << " ";
}
cout << endl;
}
return 0;
}4.2.2 约数个数
思想
- 算术基本定理：任何一个大于 1 的自然数 N，如果 N 不为质数，那么 N 可以唯一分解成有限个质数的乘积：N = p₁^{a₁} × p₂^{a₂} × ... × p_k^{a_k}。且最多只有一个大于 √N 的质因子。
- 这里 p₁ < p₂ < ... < p_k 均为质数，其中指数 a_i 是正整数。
- 设 d 为 N 的任意一个约数，则 d 可以表示为：d = p₁^{b₁} × p₂^{b₂} × ... × p_k^{b_k}，其中 0 ≤ b_i ≤ a_i。
- 由算术基本定理可知，对于 d 中的每个 p_i^{b_i} 项，指数 b_i 取值的不同组合，会得到不同的约数 d（因为每个数的质因数分解是唯一的）。
- 因此，求 N 的约数个数，等价于求指数 b_i 的选法总数。
- 对于 p₁，指数 b₁ 可以从 0 选到 a₁，共 (a₁+1) 种选法。
- 对于 p₂，指数 b₂ 可以从 0 选到 a₂，共 (a₂+1) 种选法。
- ...
- 对于 p_k，指数 b_k 可以从 0 选到 a_k，共 (a_k+1) 种选法。
- 根据乘法原理可知：N 的约数个数为 (a₁+1) × (a₂+1) × ... × (a_k+1)。
模板例题 870. 约数个数
描述
给定 n 个正整数 a_i，请你输出这些数的乘积的约数个数，答案对 1e9+7 取模。
输入格式 第一行包含整数 n。 接下来 n 行，每行包含一个整数 a_i。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10^9+7 取模。
数据范围
1 ≤ n ≤ 100, 1 ≤ a_i ≤ 2×10^9
输入样例：
3
2
6
8输出样例：
12代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
LL cnt = 1;
map<int, int> primes; // 存储质因子底数和其指数的映射
void get_div(int n) {
for (int i = 2; i <= n / i; i++) { // 枚举可能的质因子
if (n % i == 0) { // 当其为质因子时
while (n % i == 0) {
primes[i]++; // 指数增加
n /= i;
}
}
}
if (n > 1) primes[n]++; // 剩余的数大于1则为最后的质因子
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
get_div(x);
}
for (auto &p : primes) cnt = cnt * (p.second + 1) % mod; // 核心：N的约数个数为 (a1+1)*(a2+1)*(a3+1)*…*(ai+1)
cout << cnt << endl;
return 0;
}4.2.3 约数之和
思想
- 算术基本定理：任何一个大于 \(1\) 的自然数 \(N\)，如果 \(N\) 不为质数。
- 那么 \(N\) 可以唯一分解成有限个质数的乘积 \(N=p_1^{a_1}\times p_2^{a_2}\dots\times p_k^{a_k}\)，且最多只有一个大于 \(\sqrt{N}\) 的质因子。
- 这里 \(p_1 < p_2 < p_3 \dots < p_k\) 均为质数，其中指数 \(a_i\) 是正整数。
- 根据乘法原理可知：\(N\) 的约数之和 \(=(p_1^{0}+p_1^{1}+\dots+p_1^{a_1})\times(p_2^{0}+p_2^{1}+\dots+p_2^{a_2})\times\dots\times(p_k^{0}+p_k^{1}+\dots+p_k^{a_k})\)。
模板例题 871. 约数之和
描述
给定 n 个正整数 a_i，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个整数 a_i。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9+7 取模。
数据范围
1 ≤ n ≤ 100，1 ≤ a_i ≤ 2×10^9
输入样例：
3
2
6
8输出样例：
252代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
LL res = 1;
map<int, int> primes; // 存储质因子底数及其指数
void get_div(int n) {
for (int i = 2; i <= n / i; i++) { // 从2开始枚举质因子
if (n % i == 0) { // 当其为质因子时
while (n % i == 0) {
primes[i]++; // 指数增加
n /= i;
}
}
}
if (n > 1) primes[n]++; // 剩余的数大于1则为最后的质因子
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
get_div(x);
}
for (auto &p : primes) {
LL t = 1;
int a = p.first, b = p.second;
while (b--) {
t = (t * a + 1) % mod; // 核心：从 p^0 加到 p^k 的和
}
res = res * t % mod;
}
cout << res << endl;
return 0;
}4.2.4 最大公约数和最小公倍数
概念
- 最大公约数指两个或多个整数共有约数（因数）中最大的数。
- 最小公倍数指两个或多个整数的公倍数里最小的数。
思想
- 辗转相除法求最大公约数。
> 例如： 假如需要求 100 和 18 两个正整数的最大公约数，用欧几里得算法，是这样进行的：
100 / 18 = 5 (余 10)
18 / 10 = 1 (余 8)
10 / 8 = 1 (余 2)
8 / 2 = 4 (余 0)
至此，最大公约数为 2。
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数 2。
- 求 \(N\) 和 \(M\) 的最小公倍数 \(\operatorname{lcm}(N, M)\)，则先求 \(N\) 和 \(M\) 的最大公约数 \(\gcd(N, M)\)，然后 \(\frac{N \times M}{\gcd(N, M)}\) 则为最小公倍数。
模板
// 最大公约数
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
// 最小公倍数
int lcm(int a, int b){
return a / gcd(a, b) * b;
}4.3 欧拉函数
概念
- \(1 \sim N\)中与\(N\)互质的数的个数被称为欧拉函数，记为 \(\phi(N)\)。特别地，\(\phi(1)=1\)。
- 欧拉函数是一个积性函数，若\(m\)，\(n\)互质，则有\(\phi(m \times n)=\phi(m) \times \phi(n)\)。
4.3.1 公式法求欧拉函数
思想
- 算术基本定理：任何一个大于\(1\)的自然数\(N\)，如果\(N\)不为质数，那么\(N\)可以唯一分解成有限个质数的乘积\(N=p_1^{a_1}\times p_2^{a_2}\times\cdots\times p_k^{a_k}\)，且最多只有一个大于\(\sqrt{N}\)的质因子。
- 这里\(p_1<p_2<p_3<\cdots < p_k\)均为质数，其中指数\(a_i\)是正整数。
- 则\(\phi(N)=\phi(p_1^{a_1})\times\phi(p_2^{a_2})\times\cdots\times\phi(p_k^{a_k})\)。
- 对于任意一项\(\phi(p_i^{a_i})\)，与\(p_i^{a_i}\)不互质的数有\(p_i,\ 2\times p_i,\ 3\times p_i,\ \dots,\ p_i^{a_i-1}\times p_i\)，共\(p_i^{a_i-1}\)项。
- 即\(\phi(p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}\)。
模板
typedef long long LL;
LL phi(LL n){
LL res = n;
for (int i = 2; i <= n / i; i++){
if (n % i == 0){
res = res / i * (i - 1); // (1-1/i) 转换为 (i-1)/i
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1);
return res;
}例题 873. 欧拉函数
描述
给定 n 个正整数 ai，请你求出每个数的欧拉函数。
欧拉函数的定义：1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算术基本定理中，N = p₁^a₁ · p₂^a₂ · … · pₘ^aₘ，则：
ϕ(N) = N × (p₁ - 1)/p₁ × (p₂ - 1)/p₂ × … × (pₘ - 1)/pₘ
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
数据范围
1 ≤ n ≤ 100, 1 ≤ ai ≤ 2×10⁹
输入样例：
3
3
6
8输出样例：
2
2
4代码
C++ 解法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL phi(LL n) {
LL res = n;
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;
}
int main() {
int n;
cin >> n;
while (n--) {
int x;
cin >> x;
cout << phi(x) << endl;
}
return 0;
}4.3.2 筛法求欧拉函数
思想
- 利用线性筛，在筛选 1~N 中的质数时，将 1~N 的欧拉函数 ϕ(i) 求出。
- 对于质数 p，其 ϕ(p) = p - 1。
- 对于合数，其欧拉函数值通过已筛出的质因子推导而来。
以下是修复了错别字、格式问题并调整了逻辑表述后的文本：
- 在线性筛法模板中，利用最小质因子筛掉合数的过程如下：
- 当 \(i\%primes[j]=0\) 时，说明 \(primes[j]\) 是 \(i\) 的一个质因子，且是 \(primes[j]\times i\) 的最小质因子。因此 \(\phi(i)\) 的计算中已包含 \((1-\frac{1}{primes[j]})\) 项，故 \(\phi(primes[j]\times i)=primes[j]\times\phi(i)\)。
- 当 \(i\%primes[j]\ne 0\) 时，说明 \(primes[j]\) 是 \(primes[j]\times i\) 的最小质因子，且与 \(i\) 互质。因此 \(\phi(i)\) 中不包含 \((1-\frac{1}{primes[j]})\) 项，故有：
\[\begin{aligned} \phi(primes[j]\times i) &= \phi(primes[j])\times\phi(i) \\ &= (primes[j]-1)\times\phi(i) \end{aligned} \]
模板
int primes[N]; // 存储当前筛选出的质数
bool vis[N]; // 标记是否被筛掉
int phi[N]; // 记录欧拉函数的值
int cnt; // 记录质数个数
void get_phi(int n) {
phi[1] = 1; // 特别地，phi[1] = 1
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
primes[cnt++] = i; // 没有被筛掉说明是质数，记录到primes中
phi[i] = i - 1; // 质数的欧拉函数
}
for (int j = 0; primes[j] <= n / i; j++) { // 将1~n范围内质数primes[j]的i倍的合数筛掉
vis[primes[j] * i] = 1;
if (i % primes[j] == 0) { // 用最小质因子primes[j]筛掉合数
phi[primes[j] * i] = primes[j] * phi[i]; // 包含(1 - 1/primes[j])的情况
break;
} else {
phi[primes[j] * i] = (primes[j] - 1) * phi[i]; // 不包含(1 - 1/primes[j])的情况
}
}
}
}例题 874. 筛法求欧拉函数
描述
给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。
输入格式 共一行，包含一个整数 n。
输出格式 共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
数据范围 1 ≤ n ≤ 10^6
输入样例：
6输出样例：
12代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
typedef long long LL;
int primes[N];
bool vis[N];
int phi[N];
int cnt;
void get_phi(int n){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
primes[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;primes[j]<=n/i;j++){
vis[primes[j]*i]=1;
if(i%primes[j]==0){
phi[primes[j]*i]=primes[j]*phi[i];
break;
}
else phi[primes[j]*i]=(primes[j]-1)*phi[i];
}
}
}
int main(){
int n;
cin>>n;
get_phi(n);
LL res=0;
for(int i=1;i<=n;i++){
res+=phi[i];
}
cout<<res<<endl;
return 0;
}4.4 快速幂
概念
- 快速求出\(a^k\mod p\)的结果
思想
- 预处理出\(a^{2^0},a^{2^1},a^{2^2}\dots a^{2^{\log_2 k}}\)的结果
- 则使得\(k=2^{p_1}+2^{p_2}+\dots+2^{p_i}\)
- 即：\(a^k=a^{2^{p_1}}\times a^{2^{p_2}}\times\dots\times a^{2^{p_i}}\)
- 对于\(a^{2^0}\times a^{2^0}=a^{2^{1}},a^{2^{1}}\times a^{2^{1}}=a^{2^{2}}\)，即
- 综上所述，在操作时记录\(a^{2^{p_i}}\)的值，和累乘的结果
- 将\(k\)化为二进制表示，按位
>>操作，若当前位是\(1\)，则对当前累乘的结果\(\times a^{2^{p_i}} \mod p\) - 每次对\(p\)取模
a^{p_{i+1}}=a^{p_i}\times a^{p_i}\mod p
\begin{aligned} a^{p-1}\equiv 1(\mod p) \rightarrow &a \times a^{p-2}\equiv 1(\mod p)\ &a \times b\equiv 1(\mod p)\ &\text{即：} b=a^{p-2} \end
\begin{cases} b=0 \text{时：} & \begin{cases} \gcd(a,b)=a \ ax+by=\gcd(a,b) \end{cases} \Rightarrow \begin{cases} x=1 \ y=0 \end{cases} \ \ b \neq 0 \text{时：} & \begin{aligned} & \text{①设 } ax+by=\gcd(a,b)=d \ & \text{因为由欧几里得算法可知：} \gcd(a,b)=\gcd(b,a\bmod b)=d \ & \text{所以由裴蜀定理得：} b x' + (a\bmod b) y' = d \ & \text{又因为 } ax+by=d \ & \text{所以联立} \begin{cases} ax+by=d \ b x' + (a\bmod b) y' = d \ a\bmod b = a - \lfloor \frac{a}{b} \rfloor b \end{cases} \Rightarrow \begin{cases} x = y' \ y = x' - \lfloor \frac{a}{b} \rfloor y' \end{cases} \ & \text{②设 } a' = b, b' = a\bmod b \ & \text{所以 } \gcd(b,a\bmod b)=\gcd(a',b')=d \ & \text{因为 } \gcd(a',b')=\gcd(b',a'\bmod b')=d \ & \text{所以 } b' x'' + (a'\bmod b') y'' = d \ & \text{又因为 } b x' + (a\bmod b) y' = d \ & \text{所以联立} \begin{cases} b x' + (a\bmod b) y' = d \ b' x'' + (a'\bmod b') y'' = d \ a'\bmod b' = a' - \lfloor \frac{a'}{b'} \rfloor b' \end{cases} \Rightarrow \begin{cases} x' = y'' \ y' = x'' - \lfloor \frac{a'}{b'} \rfloor y'' \end{cases} \ & \text{③设 } a'' = b', b'' = a'\bmod b' \ & \dots \ & \dots \ & \text{直到 } b=0 \text{ 时，联立解得} \begin{cases} x^i = 1 \ y^i = 0 \end{cases} \ & \text{然后逐步返回每一次联立所得的结果} \begin{cases} x^{i-1} = y^i \ y^{i-1} = x^i - \lfloor \frac{a^i}{b^i} \rfloor y^i \end{cases} \text{最后返回得到 } x \text{ 和 } y \text{ 的值} \end{aligned} \end
\begin{aligned} &\textbf{判断与求解步骤：}\ &(1)\text{判断方程 } ax + by = n \text{ 是否有整数解，有解的条件为：} \gcd(a,b) \mid n\ &(2)\text{用扩展欧几里得算法求 } ax + by = \gcd(a,b) \text{，得到一个特解 } (x_0, y_0)\ &(3)\text{在 } ax_0 + by_0 = \gcd(a,b) \text{ 两边同时乘以 } \frac{n}{\gcd(a,b)} \Rightarrow \frac{ax_0 n}{\gcd(a,b)} + \frac{by_0 n}{\gcd(a,b)} = n\ &(4)\text{对照 } ax + by = n \text{ 可知该方程的一个特解为 } (x', y')，\text{ 其中 } \begin{cases} x' = \dfrac{x_0 n}{\gcd(a,b)} \ y' = \dfrac{y_0 n}{\gcd(a,b)} \end{cases} \end
\begin{aligned} &\because & ax &\equiv b \pmod{m} \ &\therefore & ax \bmod m &= k (b \bmod m), \quad (k \in \mathbb{Z}) \ &\therefore & ax - \lfloor \frac{ax}{m} \rfloor m &= k \left( b - \lfloor \frac{b}{m} \rfloor m \right) \ &\therefore & ax - k b &= \left( \lfloor \frac{ax}{m} \rfloor - k \lfloor \frac{b}{m} \rfloor \right) m \ &\because & \lfloor \frac{ax}{m} \rfloor, & \lfloor \frac{b}{m} \rfloor, k \in \mathbb{Z} \ &\therefore & \left( \lfloor \frac{ax}{m} \rfloor - k \lfloor \frac{b}{m} \rfloor \right) &\in \mathbb{Z} \ && \text{设 } \left( \lfloor \frac{ax}{m} \rfloor - k \lfloor \frac{b}{m} \rfloor \right) = y, \quad (y \in \mathbb{Z}) \ &\therefore & ax - k b &= m y \Rightarrow ax - m y = b \ \text{又} &\because & y &\text{可以为负数} \ &\therefore & ax &\equiv b \pmod{m} \leftrightarrow ax + m y = \end
(S): \begin{cases} x \equiv a_1 \pmod{m_1}\ x \equiv a_2 \pmod{m_2}\ x \equiv a_3 \pmod{m_3}\ \dots\ x \equiv a_n \pmod{m_n} \end
\begin{cases} x \equiv a_1 \pmod{m_1}\ x \equiv a_2 \pmod{m_2} \end{cases} \Rightarrow \begin{cases} x = k_1 m_1 + a_1\ x = k_2 m_2 + a_2 \end
\begin{cases} k_1 = k_1' y\ k_2 = k_2' y \end
\begin{cases} k_1 = k_1 + k \frac{m_2}{d}\ k_2 = k_2 + k \frac{m_1}{d} \end{cases} \quad (k \in \mathbb{Z})
\begin{aligned} \text{已知某线性方程组：}\ &\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \ \vdots \ a_{n1}x_1 + a_{n2}x_2 + \dots + a_{nn}x_n = b_n \end{cases} \ \text{增广矩阵为：}\ &\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} & b_1 \ a_{21} & a_{22} & \dots & a_{2n} & b_2 \ \vdots & \vdots & \vdots & \vdots & \vdots \ a_{n1} & a_{n2} & \dots & a_{nn} & b_n \end{pmatrix} \ \text{运用初等行变换：}\ &\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} & b_1 \ & a_{22} & \dots & a_{2n} & b_2 \ & & \ddots & \vdots & \vdots \ & & & a_{nn} & b_n \end{pmatrix} \ \end
\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \ \vdots \ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \ \end
C_n^m = C_{