Acwing.877 扩展欧几里得算法

题目

给定n对正整数ai , bi，对于每对数，求出一组ai ,g，使其满足ai* xi+ bi * yi = gcd(ai ,bi)。

输入格式

第一行包含整数n。
接下来n行，每行包含两个整数ai , bi。

输出格式

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

数据范围

1 ≤n≤10⁵,
1≤ai,bi≤ 2* 10⁹

• 输入样例:

2
4 6
8 18

• 输出样例

-1 1
-2 1

题解

#include <iostream>
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;scanf("%d",&n);while (n -- ){int a, b, x,y;scanf("%d%d", &a，&b);exgcd(a,b,x,y);printf("%d %d\n", x, y);}	return 0;

思路

在欧几里得算法的基础上进行公式推导
具体推导如下图