Now tell you two nonnegative integer a and b. Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.

Input The input contains multiple test cases.
Each case two nonnegative integer a,b (0<a, b<=2^31) Output output nonnegative integer X and integer Y, if there are more answers than the X smaller one will be choosed. If no answer put "sorry" instead.   题目（HDOJ2669）就是这样，解题思路无非就是用拓展欧几里得算法 作为一个新手，写下我的过程     起初看到别人的博客我是懵的，看不懂，后来自己在草稿纸上写了几下后，才豁然开朗   对于aX+bY=1的理解：   设t = gcd(a,b) 那么a = ut, b = vt, 很容易知道u, v互质，即gcd(u, v) = 1 既然u, v互质，下面来证明一个定理：   　　　　对于线性方程 ax + by = 1, （x, y未知），若该方程有整数解，那么a, b互质 用反证法即可证明 不妨设gcd(a, b) = h(h > 1)，那么必然有互质的两个数u, v，使得a = hu, b = hv，代入原方程 　　　　hux+hvy = 1 =>　　　ux+vy = 1/h(分数) 由于u, v, x, y都是整数，那么1/h也必为整数，矛盾 原命题得证   所以　　ux + vy = 1 两边同乘以t　　utx + vty = t 变形　　　　　　ax + by = gcd(a,b) 这个式子就是我们看到的那个贝祖等式     在我不知道a%b求余之前，我都用的a-(a/b)*b来求余，没想到此时派上了用场 既然已经证明了 ax + by = gcd(a,b) 存在整数解 伟大的中国数学家和欧洲数学家告诉我们，gcd(a,b) = gcd(b,a % b) 所以得连等式　　bx0 + (a%b)y0 = gcd(b, a%b) = gcd(a, b) = ax + by 带入a%b = a-(a/b)*b 移项　　　　　　b*( x0 - (a/b)y0 ) + ay0 = ax + by 对应系数相等，所以 　　　　　　x = y0 　　　　　　y = x0 - (a/b)*y0 若要求最小正整数解 只需　　x += b 同时　　y -= a   附上此题的AC代码：

#include <iostream>
using namespace std;
int exgcd(int a, int b, int & x, int & y)
{
    if(!b) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
}
int main()
{
    int a, b;
    while(cin >> a >> b) {
        int x = 0, y = 0;
        int d = exgcd(a, b, x, y);
        if (d != 1)
            cout << "sorry" << endl;
        else {
            while(x <= 0) {
                x += b;
                y -= a;
            }
            cout << x << " " << y << endl;
        }
    }
    return 0;
}

原理讲清了，代码就不注释了