2022_haue_计算机学院暑期培训-扩展欧几里得算法
1. 预习内容
1.1 阅读资料
1.2 练习题目
例题1 两个数的最大公约数
描述
输入2个正整数a，b，求a与b的最大公约数。
输入
2个正整数a，b，中间用空格隔开。(1<=a,b <= 10^4)
输出
输出a与b的最大公约数。
样例输入
6 15样例输出
3代码 1
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
cin >> a >> b;
int flag = 1;
for(int i = 2; i <= min(a,b); i++){
if(a % i == 0 && b % i == 0) flag = max(flag,i);
}
cout << flag << "\n";
return 0;
}代码 2
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
return b ? gcd(b,a%b) : a;
}
int main(){
int a, b;
cin >> a >> b;
cout << gcd(a,b) << "\n";
return 0;
}2. 课程内容
2.1 数论简介
> 数学题在算法竞赛中经常出现，在竞赛中经常把数学模型和其他算法结合起来，出综合性的题目。
分类：
- 整除性问题：整除、最大公约数、最小公倍数；欧几里得算法、扩展欧几里得算法。
- 公式计算：高精度计算、概率和数学期望。
- 素数问题：素数判定、筛法、区间素数统计。
- 同余问题：模运算、同余方程、快速幂、中国剩余定理、逆元、整数分解、同余定理、不定方程。
- 积性函数：欧拉函数、伪随机数、莫比乌斯反演。
- 多项式与生成函数：快速傅里叶变换、普通生成函数、指数生成函数。
- 递推关系：Fibonacci 数列、Stirling 数、Catalan 数。
- 群论：Polya 定理。
- 线性规划：单纯形法。
- 线性代数：矩阵、高斯消元。
- 博弈论：公平组合游戏、非公平组合游戏。
- 排列组合：容斥原理、抽屉原理、康托展开、排列生成、组合生成。
特点
- 涉及大量数学定理、数学模型和公式计算，综合程度高。
- 需要将题目抽象出其数学模型，或根据条件推理出规律进行求解。
2.2 欧几里得算法
1. 简介与证明
概念
思想
- 辗转相除法求最大公约数。
求 100 和 18 的最大公约数？
[ \begin{aligned} &1. \ 令 a_0 = 100，b_0 = 18，\ &\lfloor \frac{a_0}{b_0} \rfloor = 5，a_0 - \lfloor \frac{a_0}{b_0} \rfloor \times b_0 = 10。 \ &2. \ 令 a_1 = b_0 = 18，b_1 = a_0 \mod b_0 = 10，\ &\lfloor \frac{a_1}{b_1} \rfloor = 1，a_1 - \lfloor \frac{a_1}{b_1} \rfloor \times b_1 = 8。 \ &3. \ 令 a_2 = b_1 = 10，b_2 = a_1 \mod b_1 = 8，\ &\lfloor \frac{a_2}{b_2} \rfloor = 1，a_2 - \lfloor \frac{a_2}{b_2} \rfloor \times b_2 = 2。 \ &4. \ 令 a_3 = b_2 = 8，b_3 = a_2 \mod b_2 = 2，\ &\lfloor \frac{a_3}{b_3} \rfloor = 0，a_3 - \lfloor \frac{a_3}{b_3} \rfloor \times b_3 = 0。 \ &即最大公约数为 b_3 = 2。 \end{aligned} ]
求 100 和 18 两个正整数的最大公约数，用欧几里得算法，是这样进行的：
100 / 18 = 5（余 10）100 % 18 = 10
18 / 10 = 1（余 8）18 % 10 = 8
10 / 8 = 1（余 2）10 % 8 = 2
8 / 2 = 4（余 0）8 % 2 = 0
至此，最大公约数为 2。以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数 2。
- 求 \(N\) 和 \(M\) 的最小公倍数 \(lcm(N,M)\)，则先求 \(N\) 和 \(M\) 的最大公约数 \(gcd(N,M)\)，然后 \(\frac{N \times M}{gcd(N,M)}\) 则为最小公倍数。
2. 算法模板
// 最大公约数
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;
}3. 最大公约数
描述
输入两个正整数 a、b，求 a、b 的最大公约数。要求采用递归函数实现。
输入
输入两个正整数 a、b。
输出
输出 a、b 的最大公约数。
样例输入
20 15样例输出
5代码
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << "\n";
return 0;
}4. 多个数的最小公倍数
题目描述
输入 n 个数，请计算它们的最小公倍数。如 5、7、15 的最小公倍数是 105。
输入
首先输入一个正整数 T，表示测试数据的组数，然后是 T 组测试数据。每组测试先输入一个整数 n（2 <= n <= 20），再输入 n 个正整数（每个数属于 [1, 100000]），这里保证最终的结果在 int 型范围内。
输出
对于每组测试，输出 n 个整数的最小公倍数。
样例输入
2
3 5 7 15
5 1 2 4 3 5样例输出
105
60分析
- 求多个数的最小公倍数，可以两两相求。
代码
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;
}
void solve() {
int n;
cin >> n;
int t;
cin >> t;
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
t = lcm(t, x);
if (i == n) cout << t << '\n';
}
}
int main() {
int _;
cin >> _;
while (_--) {
solve();
}
return 0;
}2.3 扩展欧几里得算法
简介与证明
作用
- 求形如 (ax + by = \gcd(a, b)) 的方程的解 (x, y)
思想
- 欧几里得算法：(\gcd(a, b) = \gcd(b, a % b))，特别地 (\gcd(a, 0) = a)
- 裴蜀定理：对于任意正整数 (a, b)，一定存在整数 (x, y)，使得 (ax + by = \gcd(a, b))
注意
当方程符合 \(ax+by=\gcd(a,b)\) 的形式时，才可以用扩展欧几里得算法求解 \((x_0,y_0)\)。
推论： 可以进一步求解任意方程 \(ax+by=n\)，得到一个整数解。
1. 扩展欧几里得算法求解
2. 算法模板
void exgcd(int a, int b, int &x, int &y) {
if (!b) { // 若 b=0 时
x = 1;
y = 0;
return;
} else { // b!=0 时
exgcd(b, a % b, x, y); // 递归到下一层
int t = x; // 返回时执行
x = y;
y = t - a / b * y;
}
}3. 解 ax+by=gcd(a,b) 方程
描述
给定 \(n\) 对正整数 \(a_i,b_i\)，对于每对数，求出一组 \(x_i,y_i\)，使其满足 \(a_i \times x_i + b_i \times y_i = \gcd(a_i, b_i)\)。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含两个整数 \(a_i, b_i\)。
输出格式
输出共 \(n\) 行，对于每组 \(a_i, b_i\)，求出一组满足条件的 \(x_i, y_i\)，每组结果占一行。
本题答案不唯一，输出任意满足条件的 \(x_i, y_i\) 均可。
数据范围
\(1 \leq n \leq 10^5\)，\(1 \leq a_i, b_i \leq 2 \times 10^9\)
输入样例：
2
4 6
8 18输出样例：
-1 1
-2 1代码
#include <bits/stdc++.h>
using namespace std;
void exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return;
} else {
exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
}
}
int main() {
int n;
cin >> n;
while (n--) {
int a, b, x, y;
cin >> a >> b;
exgcd(a, b, x, y);
cout << x << " " << y << endl;
}
return 0;
}4. 解一元线性同余方程
概念
- \(ax \equiv b \pmod{m}\)，即 \(\frac{ax}{m}\) 与 \(\frac{b}{m}\) 的余数相同，且 \(a, b, m\) 为整数，求 \(x\) 的值。
- 该方程即为一元线性同余方程。
思想
对 \(ax \equiv b \pmod{m}\) 做等价变形：\(ax + my = b\)。
由扩展欧几里得算法的推论可知：当且仅当 \(gcd(a, m)\) 整除 \(b\) 时，\(ax + my = b\) 存在整数解。
例题 878. 线性同余方程
描述
给定 \(n\) 组数据 \(a_i,b_i,m_i\)，对于每组数求出一个 \(x_i\)，使其满足 \(a_i \times x_i \equiv b_i \pmod{m_i}\)，如果无解则输出 impossible。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一组数据 \(a_i,b_i,m_i\)。
输出格式
输出共 \(n\) 行，每组数据输出一个整数表示一个满足条件的 \(x\)，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围 \(1 \leq n \leq 10^5\), \(1 \leq a_i, b_i, m_i \leq 2 \times 10^9\)
输入样例
2
2 3 6
4 3 5输出样例：
impossible
-3代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
// 求最大公约数
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
// 扩展欧几里得算法，求解 ax + by = gcd(a,b)
void exgcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1, y = 0;
return;
} else {
exgcd(b, a % b, x, y);
LL t = x;
x = y;
y = t - a / b * y;
}
}
int main() {
int n;
cin >> n;
while (n--) {
LL a, b, m, x, y;
cin >> a >> b >> m;
LL d = gcd(a, m); // 计算 a 和 m 的最大公约数
exgcd(a, m, x, y); // 求解 ax + my = d
// 如果 b 不能被 d 整除，则方程无整数解
if (b % d)
cout << "impossible" << endl;
else
// 计算一个特解并取模。注意 (b/d * x) 可能为负数，取模后会得到正确的非负余数或负数解。
cout << b / d * x % m << endl;
}
return 0;
}