題目：青蛙的約會
思路：首先本題可以用常規(guī)的解法求得一個擴展的歐幾里德的算法公式。為了保證能夠相遇，A 和 B 的總路程的差值一定是緯度長的整數(shù)倍。

令 跳躍 t 次后相遇， 有
(x + m * t) - (y + n * t) = l * k
轉(zhuǎn)化公式有：
x-y = (n-m) * t + l * k
令 d = x-y; a = n-m; b = l; 有
d = a * t + b * k = gcd(a, b)

在解這道題的時候，我并沒有對擴展的歐幾里德算法有所了解，所以很多的問題都沒有得到很好的解釋，也看不懂，通過這道題讓我對歐幾里德的算法應(yīng)用，有了更進一步的了解。學(xué)習(xí)算法的重要性在于使用算法解決實際的問題。

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (a < b)
        swap(a, b);

    int r = a % b;
    if (r == 0)
        return b;

    return gcd(b, r);
}

void extern_gcd(unsigned int a, unsigned int b, unsigned int c, int & x, int & y) {
    int d = b;
    int r = a % b;

    if (r == 0) {
        x = 0;
        y = 0;
        if (d == c)
            y = 1;
        return ;
    }

    int tmpx = 0;
    int tmpy = 0;
    extern_gcd(b, r, c, tmpx, tmpy);
    x = tmpy;
    y = tmpx - (a / b) * tmpy;

    return ;
}


int main() {
    int x = 0;
    int y = 4;
    int n = 4;
    int m = 2;
    int l = 8;

    int t = 0;
    int k = 0;
    int times = 0;

    cout << "Input: "  << x << "," << y << "," << n << "," << m << "," << l << endl;

    // (y - x) = (n - m) * t + l * k
    x = x % l;
    y = y % l;
    int yx = y - x;
    if (yx < 0) yx += l;

    int nm = n - m;
    if (nm < 0) {
        nm = -nm;
        yx = l - yx;
    }

    if (nm > 0) {
        int gcd_yx = yx / gcd(yx, gcd(nm, l));

        int knm = gcd_yx * nm;
        int kl = gcd_yx * l;


        extern_gcd(knm, kl, yx, t, k);

        times = gcd_yx * t;
    }
    cout << "Output: ";
    if (times > 0)
        cout << times << endl;
    else
        cout << "Impossible" << endl;

    return 0;
}

我對這道題有太多的感慨，網(wǎng)上的文章只是告訴我使用擴展的歐幾里德算法，但是并沒有告訴我如何使用這個算法。
使用擴展的歐幾里德算法有兩個基本的限制

1. 所有的輸入輸出必須全是整數(shù)，、

2. 構(gòu)造一個原組（a, b），a和b的最大公約數(shù)是d

依賴上述的條件我們能算得一個等式：

d = ax + by;

你可以從我的代碼上看到這個特點，我辛辛苦苦的就是為了湊了上述的限制，然后才能使用擴展的歐幾里德算法。
從這道題我看到了對于算法的變通和數(shù)學(xué)上使用的轉(zhuǎn)換算法是如此的相似！?。?/p>