poj 1061 （扩展欧几里德算法）

首先先抛出一个例题：

青蛙的约会

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 89761		Accepted: 16131

Description

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

Output

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

Sample Input

1 2 3 4 5

Sample Output

涉及知识点：ext_gcd

代码如下：

#include<stdio.h>
#include<math.h>
#define LL long long

LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL d = extend_gcd(b, a%b, x, y);
    LL t = x;
    x = y;
    y = t-a/b*y;
    return d;
}

int main()
{
    LL x, y, n, m, L;
    LL a,b,c,d;

    while(~scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L))
    {
        LL p,q;
        a=n-m, b=L, c = x-y;
        d = extend_gcd(a, b, p, q);

        if(c%d!=0) printf("Impossible
");
        else
        {
            p = p*(c/d);
            p = (p%b + b)%b;
            printf("%lld
", p);
        }
    }
    return 0;

注意：

ext_gcd模板求得的只是当 ax + by = gcd（a，b）时，x 和 y 的值。但是当ax ' + b y' = c 如果有解，则应满足以下情况：,c能够整除gcd（a， b)，也就是c = k *（gcd（a, b））其中k为整数。那么此时的 x' 就等于kx， y' 就等于 ky，即 x' = kx, y = ky'，对应文中代码部分为： p = p*(c/d);。如果想求最小正整数解的话，就要加上 p = (p%b + b)%b 了。

—————————————————————————————————————————————————————————————————————————————

今天看了一下gcd算法，本来学的教材上有这个，但不知道还叫欧几里德算法，于是又重新看了一边，搜的时候没想到还有新的收获，又看到了拓展欧几里德算法。

先说一下gcd吧，也叫辗转相除法。给定两个数 a，b , 求两个数中的最大公约数。

int gcd(int n, int m) // n>m
{
if(n%m == 0)
return m;
else
return (m, n%m);

}

思路比较简单，两个数（a， b，其中a>b）的最大公约数就等于其中较小数（b）和（a%b）这两个数的最大公约数。

最小公倍数等于两个数的乘积除以两个数的最大公约数。

再说一下extend_gcd（拓展欧几里得算法），ext_gcd 算法由裴蜀定理中得出：

知识点： 在数论中，裴蜀等式或裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 $a$ 、 $b$ 和它们的最大公约数 $d$ ，关于未知数 $x$ 和 $y$ 的线性丢番图方程（称为裴蜀等式）：

ax+by=m

有整数解时当且仅当m是d 的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 $x$ 、 $y$ 都称为裴蜀数，可用扩展欧几里得算法求得。

例如，12和42的最大公约数是6，则方程 $12x+42y=6$ 有解。事实上有(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。

特别来说，方程 $ax+by=1$ 有整数解当且仅当整数a和b互素。

裴蜀等式也可以用来给最大公约数定义： $d$ 其实就是最小的可以写成 $ax+by$ 形式的正整数。这个定义的本质是整环中“理想”的概念。因此对于多项式整环也有相应的裴蜀定理。

历史：历史上首先证明关于整数的裴蜀定理的并不是裴蜀，而是17世纪初的法国数学家克劳德-加斯帕·巴歇·德·梅齐里亚克（Claude-Gaspard Bachet de Méziriac）。他在于1624年发表的著作《有关整数的令人快乐与惬意的问题集》（Problèmes plaisans et délectables qui se font par les nombres）第二版中给出了问题的描述和证明^[1]。

然而，裴蜀推广了梅齐里亚克的结论，特别是探讨了多项式中的裴蜀等式，并给出了相应的定理和证明^[2]。

证明过程如下：

整数中的裴蜀定理

对任意两个整数

a

、

b

，设

d

是它们的最大公约数。那么关于未知数

x

和

y

的线性丢番图方程（称为裴蜀等式）：

displaystyle ax+by=m

有整数解(x,y) 当且仅当m 是d 的倍数。裴蜀等式有解时必然有无穷多个解。

证明：

如果 $a$ 和 $b$ 中有一个是0，比如 $a=0$ ，那么它们两个的最大公约数是 $b$ 。这时裴蜀等式变成 $displaystyle by=m$ ，它有整数解(x,y) 当且仅当m 是d 的倍数，而且有解时必然有无穷多个解，因为 $x$ 可以是任何整数。定理成立。

以下设 $a$ 和 $b$ 都不为0。

设 $A = {xa+yb; (x;y) in ^2}$ ，下面证明 $A$ 中的最小正元素是 $a$ 与 $b$ 的最大公约数。

首先， $A cap N^*$ 不是空集（至少包含 $|a|$ 和 $|b|$ ），因此由于自然数集合是良序的， $A$ 中存在最小正元素 $d_0 = x_0a + y_0b$ 。考虑A中任意一个正元素p（ $=x_1a + y_1b$ ）对 $d_0$ 的带余除法：设 $p=qd_0+r$ ，其中q 为正整数， $0 le r < d_0$ 。但是