AcWing 877：扩展欧几里得算法

【题目来源】
https://www.acwing.com/problem/content/879/

【题目描述】
给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。

【输入格式】
第一行包含整数 n。接下来 n 行，每行包含两个整数 ai,bi。

【输出格式】
输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi,yi 均可。

【数据范围】
1≤n≤10^5,
1≤ai,bi≤2×10^9

【输入样例】
2
4 6
8 18

【输出样例】
-1 1
-2 1

【算法分析】
● 扩展欧几里得算法用于求解 ax+by=gcd(a,b) 的整数解 (x,y)。算法思想如下：
当 b=0 时，ax+by=a，故 x=1，y=0。
当 b≠0 时，由裴蜀定理，得 ax+by=gcd(a,b)。
又由 gcd(a,b)=gcd(b,a%b) 及裴蜀定理，得 bx1+(a%b)y1=gcd(b, a%b)。
而 bx1+(a%b)y1=bx1+(a - b⌊a/b⌋)y1=ay1+b(x1-y1⌊a/b⌋)，故可得，x=y1，y=x1-y1⌊a/b⌋。
因此，可以利用递归，先求出下一层的x1和y1，再利用上述公式回代即可。

【算法代码一】

#include <bits/stdc++.h>
using namespace std;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;
}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;
}/*
in:
2
4 6
8 18out:
-1 1
-2 1
*/

【算法代码二】

#include <bits/stdc++.h>
using namespace std;void exgcd(int a,int b,int &x,int &y) {if(b==0) {x=1,y=0;return;}exgcd(b,a%b,x,y);int t=y;y=x-a/b*y;x=t;
}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;
}/*
in:
2
4 6
8 18out:
-1 1
-2 1
*/

【参考文献】
https://www.acwing.com/problem/content/879/
https://www.acwing.com/solution/content/278600/