扩展欧几里得

求解线性方程，首先要判断线性方程有没有解

如果，说明方程有解

我们可以先用扩展欧几里得求解方程

因为

即

根据多项式恒等定理，最后化简得到

　所以，当求出最大公约数时，，我们让x=1，y=0,求出一组解，然后递归返回时，根据上面的递推，不断递推出解，从而最终求的

　　的解

　　从而的解也可以求的。

LL extendGcd(LL a, LL b, LL &x, LL &y)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL g = extendGcd(b,a%b,x,y);
    //不断递推出新方程的解
    LL t = x;
    x = y;
    y = t - a / b * y;
    return g;
}

但是这样只能够求出一组解(x2,y2)，如果要求出另一组解怎么办呢？我们设另外一组解为（x1,y1)

可以a"与b"是互为质数的，所以(x1-x2)是b“的倍数(设为kb")，那么x1=x2+kb". 同理，(y2-y1)也是a"的倍数(设为ka"),那么y1=y2-ka"

即另一个组解为(x2+kb",y2-ka")

下面是模线性方程的一个应用

poj1061 http://poj.org/problem?id=1061

根据题目我们设跳k次之后相遇，可以得到方程 x+km = y+kn(mod L) 两只青蛙相遇，即mod L时余数相等

那么得到 x+km-y-kn = SL --> k(m-n) - SL = y - x

用扩展欧几里得就可以求出解来，但是要注意的一点是负数的情况，当初做的时候wa了好久，现在完全理解了定理之后，讨论一下是负数的情况就A了

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 
 5 typedef __int64 LL;
 6 
 7 LL exGcd(LL a, LL b, LL&x, LL&y)
 8 {
 9     if(b==0)
10     {
11         x = 1;
12         y = 0;
13         return a;
14     }
15     LL g = exGcd(b,a%b,x,y);
16     LL t = x;
17     x = y;
18     y = t - a / b * y;
19     return g;
20 }
21 int main()
22 {
23     LL x,y,n,m,L,a,b,c,g;
24     while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L)!=EOF)
25     {
26         a = m - n;
27         b = L;
28         c = y - x;
29         if(a<0)//如果a是负数，那么让a变成正数，然后只要求出x之后 改成-x就是原方程的解
30             g = exGcd(-a,b,x,y);
31         else
32             g = exGcd(a,b,x,y);
33         if(c%g==0)//是g的倍数才有解
34         {
35             x = x * (c/g);
36             if(a<0)
37                 x = -x;
38             x %= b/g;
39             if(x<0)
40                 x += b/g;
41             printf("%I64d
",x);
42         }
43         else
44             puts("Impossible");
45     }
46     return 0;
47 }

View Code