拓展欧几里得_牛客博客

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;
}

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