UVA10104 | magicat

板子题

当

最小时，那么是ax+by=gcd(a,b)

输入格式乱搞，见谅

#include<iostream>
using namespace std;

typedef long long LL;

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    LL xx,yy;
    LL d=exgcd(b,a%b,xx,yy);
    x=yy;
    y=xx-(a/b)*yy;
    return d;
}




int main()
{
    LL a,b,x,y;
    while(cin>>a>>b&&a!=1000000001&&b!=1000000001)
    {
        LL d=exgcd(a,b,x,y);
        printf("%lld %lld %lld\n",x,y,d);
        a=1000000001;
        b=1000000001;
    }
        
}