扩展欧几里得算法

扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中
公式表述
gcd(a,b)=gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

例题

https://cn.vjudge.net/contest/202817#problem/O

#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long LL;

void gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        gcd(b,a%b,d,y,x);
        y -= x * (a / b);
    }
}

int main()
{
    LL x,y,m,n,l;
    while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l) == 5)
    {
        if(m < n)
        {
            swap(m,n);
            swap(x,y);
        }

        LL b = l;
        LL a = m - n;
        LL c = y - x;
        LL d,x,y;
        gcd(a,b,d,x,y);
        if(c % d) printf("Impossible\n");
        else
        {
            x = x * c / d;
            LL b1 = b / d;
            if(x > 0)
            {
                x = x % b1;
            }
            else
            {
                x = x % b1 + b1;
            }
            printf("%lld\n",x);

        }
    }
    return 0;
}