题目描述
给定$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≤ai,bi≤2∗10^{9}$
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
1. 扩展欧几里得
用于求解方程 $ax+by = gcd(a,b)$ 的解
当 $b = 0$ 时 $\quad ax + by = a$ 故而 $x = 1, y = 0$
当 $b ≠ 0$ 时
因为
$$ gcd(a, b) = gcd(b, a\%b) $$
而$$ bx’ + (a \% b)y’ = gcd(b, a\%b)$$
$$bx’ + (a-\lfloor a/b \rfloor*b)y’ = gcd(b, a\%b)$$
$$ay’ + b(x’-\lfloor a/b \rfloor*y’) = gcd(b, a\%b) = gcd(a, b)$$
故而
$$x = y’ , \quad y = x’ - \lfloor a/b \rfloor*y’$$
因此可以采取递归算法 先求出下一层的$x’$和$y’$ 再利用上述公式回代即可
2. 对于求解更一般的方程 $ax + by = c$
设 $d = gcd(a, b)$ 则其有解当且仅当 $d | c$
求解方法如下:
用扩展欧几里得求出 $ax_{0} + by_{0} = d$ 的解
则$a(x_{0}\*c/d)+b(y_{0}*c/d) = c$
故而特解为 $ x’ = x_{0}\*c/d , \quad y’ = y_{0}\*c/d$
而通解 = 特解 + 齐次解
而齐次解即为方程 $ax + by = 0$的解
故而通解为 $ x = x’ + k\*b/d,\quad y = y’ - k\*a/d\quad k \in \mathbb{z}$
若令 $t=b/d$, 则对于 $x$ 的最小非负整数解为 $(x’\%t+t)\%t$
3.应用: 求解一次同余方程 $ax ≡ b (mod m)$
则等价于求
$$ax = m\*(-y) + b$$
$$ax + my = b$$
有解条件为 $gcd(a,m) | b$,然后用扩展欧几里得求解即可
特别的 当 $b = 1$ 且 $a$与$m$互质时 则所求的$x$即为$a$的逆元
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
if(b==0){
x = 1, y = 0;
return a;
}
int x1,y1,gcd;
gcd = exgcd(b, a%b, x1, y1);
x = y1, y = x1 - a/b*y1;
return gcd;
}
int main(){
int n,a,b,x,y;
cin>>n;
while(n--){
cin>>a>>b;
exgcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
}
return 0;
}
齐次解为啥是b/d 和 a/d呀
ax + by = 0
ax = -by
x = -b/a * y
设 d = (a, b), a = a1 * d, b = b1 * d, 故 （a1, b1) = 1
x = -(b1 * d) / (a1 * d) * y
x = -b1/a1 * y, 因为 a1, b1 互质， 则x有整数解 => a1 | y => y = k * a1 (k 为任意整数）=> y = k * a/d
代入得 x = - k * b/d
我TM直接NB
直接NB
我TM直接NB
很清晰
还是不理解昂..
dl
orz
我操 写的太他妈牛逼了！
好蟀的头像啊 我都说雀氏蟀了
小丑一个一个小丑
小丑
丁真珍珠（
想问一下 ，对于x最小非负整数解为 (x′%t+t)%t 这里是怎么冒出来的
为什么要 用 x 去 模 b/d . b/d 求出来的是什么东西
x’有可能是负的，(x′%t+t)%t 这句话可以保证求出来一个正的余数
看着忍不住woc
过了一年，再回来看，感觉比上次收获更多了，只能说，这题解是写的真好
请教一下大佬！a(x0∗c/d)+b(y0∗c/d)=c 这里x为什么突然变成了x0c/d y为啥突然变成了 y0c/d
我好像明白了，两边同时扩大 c/d倍
是的
b=0的时候推不出y = 0, y = 0只是一个特解而已。
是的，b=0的时候y可以是任意值，需要的只是一个特解，（输出一种可能的情况即可）
大佬nb
d|c读作 : d整除c，或c被d整除
竖线前面的是约数，是比较小的数字，后面的数字是被整除的数字，是比较大的数字
这里的k又是代表什么呢
LaTeX 炸了
终于理解这个含义了，1
int exgcd(int a,int b,int &x,int &y)
{
if(b == 0)
{
x = 1,y = 0;
return a;
}
int d = exgcd(b,a%b,y,x);
y -= a / b * x;
return d;
}
清晰明了orz
写得太牛了
我悟了
想问一下，这两行代码，为什么不可以交换顺序？
x1,y1没有进行初始化，为什么可以直接调用呢
你现在知道了吗，我也不理解
不知道
x1，y1没有初始化也是因为他们不需要初始化，因为是到最底层的时候被赋值x=1，y=0带值回去，一层一层往上带回
NB谢谢
赞
如果我要求x y都是尽可能小的正整数解要怎么做
直接求出非负整数解再加一个通解不就完事了
真的太清楚了，%%%
写的真不错！