5.0 KiB
一、题目描述
给定 n 对正整数 a_i,b_i，对于每对数，求出一组 x_i,y_i，使其满足 a_i×x_i+b_i×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≤n≤10^5
1≤a_i,b_i≤2×10^9
输入样例
2
4 6
8 18
输出样例
-1 1
-2 1
样例理解：
2x+3y=1一组可行解：(-1,1)8x+18y=2一组可行解：(-2,1)
二、裴蜀定理
裴蜀定理
若a,b是整数,且gcd(a,b)=d，那么:
-
对于任意的整数
x,y,ax+by都一定是d的倍数 -
一定存在整数
x,y，使ax+by=d成立
裴蜀定理推论
a,b互质 \Leftrightarrow gcd(a,b)=1 \Leftrightarrow 存在整数x,y,使得ax+by=1
举栗子
2x+y=3
那么a=2,b=1,m=3,gcd(2,1)=1,3是1的倍数，所以这个方程一定有整数解。
x=1,y=1就是一个整数解，还可以有x=-2,y=7也是一组整数解。
注意：如果一个二元一次方程有正整数解，那么不只是一组解
####再举栗子
4x+2y=5
有没有整数解呢？没有，因为a=4,b=2,m=5,gcd(4,2)=2,5是除不开2的，所以没有整数解!
如何求贝祖数？
什么是贝祖数？
比如：2x+y=3，那么符合这个等式的x=1,y=1就是一组 贝祖数
可以使用 扩展欧几里得算法求贝祖数
举个栗子：
求 104x+40y=8 ，有没有合适的x,y,也就是求贝祖数
通过贝祖定理看一下，它是不是有解： gcd(104,40)=8,8是8的倍数，所以此方程一定有解，那么解是什么呢？
扩展欧几里得算法的推导过程：
在exgcd中，我们实际是求不定方程ax+by=gcd(a,b)，并且，我们所返回的值，是这组解(x，y)的最大公因数gcd(x,y)。
所以我们最后得到的解，要通过X=x∗k/gcd(a,b)，Y=(k−a∗x)/gcd(a,b)来进行一个小小的转换，得到一组解
算法实现过程证明
(1)、当 b=0时
\large ax+by=gcd(a,0)，也就是:\large ax=gcd(a,0)=a,所以\large x=1。
那么y呢？因为普遍意义上的求贝祖数，一般是指不小于零的一组解，那么不小于0的第一个可能y值就是:y=0,所以，可以将x=1,y=0做为一组特解返回，也就是返回了一组不小于零的贝祖数。
(2)、当 b≠0时
\because ax+by=gcd(a,b) 【原计算式】
gcd(b,a\%b)=gcd(a,b) 【辗转相除法】
\therefore ax+by=gcd(a,b)=gcd(b,a\%b)=b\cdot x_0+(a\%b)\cdot y_0 ① 【变量互换，最终是一致滴~】
\because a\%b=a-⌊\frac{a}{b}⌋\cdot b ②【用整除向下取整来描述扣去a中所有的b,剩下的就是余数】
将②代入①
\therefore ax+by=bx_0+(a-⌊\frac{a}{b}⌋\cdot b)\cdot y_0
\therefore ax+by=ay_0+b(x_0-⌊\frac{a}{b}⌋\cdot y_0)
\therefore x=y_0,y=x_0-⌊\frac{a}{b}⌋y_0
三、实现代码
#include <bits/stdc++.h>
using namespace std;
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);
y -= a / b * x;
return d;
}
int main() {
int n;
cin >> n;
while (n--) {
int a, b;
cin >> a >> b;
int x, y;
exgcd(a, b, x, y);
printf("%d %d\n", x, y);
}
return 0;
}
四、三者之间的关系
1. 裴蜀定理
-
对于任意一对正整数
a,b，一定存在非零整数x,y使得ax+by=gcd(a,b) -
可以用来判断方程
ax+by=c是否有解，只要看c是否是gcd(a,b)的倍数
2. 扩展欧几里得算法
如果方程ax+by=c有解，那么扩欧可以求方程ax+by=gcd(a,b)一组解(x_0,y_0)
3.线性同余方程
给定a,b,m构造出x使得ax≡b(mod\ m)成立
ax≡b(mod\ m)⟺ax=my+b(y是整数)
由此可知ax−my=b
令y'=−y则有ax+my'=b
则构造x一定使得ax+my'=b有解
根据裴蜀定理可知该方程有解的充要条件是(a,m)|b
设d=(a,m),若d∤b则x不存在
若d|b，则可以用 扩展欧几里得算法 算出ax+bm=gcd(a,m)=d的x_0,y_0
再将x_0×\frac{b}{d},y_0×\frac{b}{d}得到x与y'