HDU2669Romantic（欧几里得拓展）

解题思路：纯粹的欧几里得拓展运用

AC代码如下：

#include<stdio.h>

typedef long long ll;

ll extend_gcd(ll A,ll B,ll xy[])
{
    if(B==0)
    {
        xy[0]=1;
        xy[1]=0;
        return A;
    }
    ll ans=extend_gcd(B,A%B,xy);
    ll t=xy[0];
    xy[0]=xy[1];
    xy[1]=t-A/B*xy[1];
    return ans;
}

int main()
{
    ll a,b,xy[2];
    while(~scanf("%lld%lld",&a,&b))
    {
        if(extend_gcd(a,b,xy)!=1)
        {
            printf("sorry\n");
        }
        else
        {
        	while(xy[0]<0)
				xy[0]+=b,xy[1]-=a;
            printf("%lld %lld\n",xy[0],xy[1]);
        }
    }
    return 0;
}