学步园

题意：给出a, b(0<a, b<=2^31)，求X * a + Y * b = 1 的一组解x1, x2，满足x1 >= 0。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2669

——>>在找乘法逆元的题目，看到这题简单顺手A了。。

#include <cstdio>

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 -= a / b * x;
    }
}

int main()
{
    int a, b;
    LL d = 0, x = 0, y = 0;

    while (scanf("%d%d", &a, &b) == 2)
    {
        Gcd(a, b, d, x, y);
        if (d != 1)
        {
            puts("sorry");
        }
        else
        {
            if (x >= 0)
            {
                printf("%I64d %I64d\n", x, y);
            }
            else
            {
                LL t = - x / b;
                if (x % b)
                {
                    ++t;
                }
                printf("%I64d %I64d\n", x + b * t, y - a * t);
            }
        }
    }

    return 0;
}