扩展欧几里得(acwing877)

给a,b求使ax+by=gcd(a,b)，成立的x,y;

思路：

整个过程可以分为两部分，一部分是求gcd(a,b)，当函数递归回来时，求x,y;

递归回来时： b*y+(a-(a/b)*b)*x=d(d为gcd(a,b));

求当前a*x+b*y=d,的x,y;

a*x+b(y-a/b*x)=d;

x=x;

y=y-a/b*x;

代码：

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

}
int main()
{
    int a, b, x, y;
    scanf("%lld", &n);
    while (n--)
    {
        scanf("%d%d", &a, &b);
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }
    return 0;
}