题目描述
给定n对正整数ai,bi，对于每对数，求出一组xi,yi，使其满足aixi+biyi=gcd(ai,bi)。
输入格式
第一行包含整数n。
接下来n行，每行包含两个整数ai,bi。
输出格式
输出共n行，对于每组ai,bi，求出一组满足条件的xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的xi,yi均可。
数据范围
1≤n≤105,
1≤ai,bi≤2∗109
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
1. 扩展欧几里得
用于求解方程 ax+by=gcd(a,b) 的解
当 b=0 时 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−⌊a/b⌋∗b)y′=gcd(b,a%b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
故而
x=y′,y=x′−⌊a/b⌋∗y′
因此可以采取递归算法 先求出下一层的x′和y′ 再利用上述公式回代即可
2. 对于求解更一般的方程 ax+by=c
设 d=gcd(a,b) 则其有解当且仅当 d|c
求解方法如下:
用扩展欧几里得求出 ax0+by0=d 的解
则a(x0\*c/d)+b(y0∗c/d)=c
故而特解为 x′=x0\*c/d,y′=y0\*c/d
而通解 = 特解 + 齐次解
而齐次解即为方程 ax+by=0的解
故而通解为 x=x′+k\*b/d,y=y′−k\*a/dk∈z
若令 t=b/d, 则对于 x 的最小非负整数解为 (x′%t+t)%t
3.应用: 求解一次同余方程 ax≡b(modm)
则等价于求
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
写得太牛了
我悟了
gcd=exgcd(b,a%b,x1,y1); x=y1,y=x1-a/b*y1;想问一下，这两行代码，为什么不可以交换顺序？
x1,y1没有进行初始化，为什么可以直接调用呢
你现在知道了吗，我也不理解
不知道
x1，y1没有初始化也是因为他们不需要初始化，因为是到最底层的时候被赋值x=1，y=0带值回去，一层一层往上带回
NB谢谢
赞
如果我要求x y都是尽可能小的正整数解要怎么做
直接求出非负整数解再加一个通解不就完事了
真的太清楚了，%%%
写的真不错！