扩展欧几里德: 给一个线性方程X*a+Y*b=m，给出a,b,m让求解X和Y。

首先，只有m%gcd(a,b)==0 时 该线性方程才有解。

假使a=k1 *gcd(a,b),b=k2 * gcd(a,b);

那么方程左边就等于(X*k1+Y*k2)*gcd(a,b),所以仅当m能被gcd(a,b)整除时方程才有解。

为了求上述方程的解，我们不妨先来求方程a*X+b*Y=gcd(a,b)的解,设d=m/gcd(a,b);

所以a*(d*X)+b*(d*y)=d*gcd(a,b)=m,求出这个方程的解原方程的解也就求出了。

根据欧几里德有gcd(a,b)=gcd(b,a%b)

所以a*X+b*Y=gcd(a,b)=gcd(b,a%b)=b*X1+(a%b)*Y1;

令k=a/b , r=a%b

a=b*k+r;

得出X=Y1 ,  Y=X1-Y1*(a/b);

#include "string"
#include "iostream"
#include "cstdio"
#include "cmath"
#include "set"
#include "queue"
#include "vector"
#include "cctype"
#include "sstream"
#include "cstdlib"
#include "cstring"
#include "stack"
#include "ctime"
#include "algorithm"
#define pa pair<int,int>
#define Pi M_PI
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
__int64 EXgcd(__int64 a,__int64 b,__int64& x,__int64& y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    __int64 r=EXgcd(b,a%b,x,y);
    __int64 t=x;
    x=y;
    y=t-a/b*y;
    return r;
}
int main()
{
    __int64 a,b,x,y,Gcd;
    while(cin>>a>>b)
    {
        Gcd=EXgcd(a,b,x,y);
        if(Gcd==1)//为一才有解
        {
            while(x<0)
            {
                x+=b;
                y-=a;
            }
            cout<<x<<" "<<y;
        }
        else
            cout<<"sorry";
        cout<<endl;
    }
    return 0;
}