扩展欧几里德算法

关于不定方程ax+by=c

扩展欧几里德算法其实就是用来求出一组关于ax+by=c的解，复杂度比较稳定，是建立在欧几里德算法上面进行计算的。

首先需要考虑一下这个不定方程是否有解判断的方法就是：对于一个方程ax+by=c来说，如果 c%GCD(a,b)!=0 那么这个方程就是无解的。其实扩展欧几里德算法解出来的就是丢番图方程的解（好像是丢番图方程）。

首先我们需要看一下这个不定方程是否有解，如果有解的话，就进行计算，很显然的，如果b=0的时候，那么ax=c，那么x一定等于c/a。此时x=c/a,y=0;

然后，然后我们可以列出来两个方程：

  1. a*x1+b*y1=GCD(a,b);
  2. b*x2+(a%b)*y2=GCD(b,a%b);

然后根据欧几里德算法：GCD(a,b)=GCD(b,a%b);

所以就可以得到：a*x1+b*y1=b*x2+a%b*y2;

然后解得: x1=y2 y1=x2-a/b*y2;

然后我们就可以利用GCD的迭代解出来不定方程ax+by=c的一组解！

注意这里是一组解！！！！！！

但是你需要求出来其他解（比如大于零的最小解）

你就需要明白一个定理，也就是如果(x,y)是不定方程的一组解，那么(x+b/a,y-a/b)
也同样是一组解，然后我们就可以愉快的寻找其他解了……

比如大于零的最小x的解：(x%(LCM/a)+LCM/a)%LCM/a;原理和上面的(x+b/a,y-a/b)是一样的。但是(LCM/a)是满足x为整数的最小值。

  • 最后我们来看一道神奇的题目：

青蛙的约会

题目描述：

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳n米，青蛙B一次能跳m米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入：

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

输出：

在单独一行里输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行“Impossible”。

题解：

  • 这个一看就是扩展欧几里德啊……我们可以这样变幻一下。
  • 首先，我们可以轻松的设出来方程：设x为两只青蛙需要跳的次数，a为A青蛙的初始位置，b为B青蛙的初始位置，然后解方程：
  1. (n*x+a)%L=(m*x+b)%L
  2. nx%L+a%L=mx%L+b%L
  3. nx%L-mx%L=b%L-a%L
  4. (n-m)x%L=(b-a)%L
  5. 设c=(b-a)%L,d=n-m，则c,d为可计算常数；
  6. dx%L=c
  7. dx+Ly=c

  • 这个式子里面的x就是要输出的k！！！
    数论超级有意思的！

  • 然后就是在开始扩展欧几里德之前先判断一下是否有解，就是if(c%GCD)是否为零，如果是则有解，否则无解。也就是判断一下c是不是x和y的最大公约数的倍数。

  • 最后输出的时候用上面的方法找出来要求的最小正整数解就行了！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cctype>
using namespace std;
long long s1,s2,m,n,l,a,b,c,This,All,x,y;
long long GCD(long long x,long long y)
{
    long long Now=x%y;
    while(Now)
    {
        x=y;
        y=Now;
        Now=x%y;
    }
    return y;
}
void EXGCD(long long a,long long b)
{
    if(!b){x=c/This;y=0;return;}
    EXGCD(b,a%b);
    All=x; x=y; y=All-a/b*y;
}
long long LCM(long long x,long long y)
{ return abs(x*y/This/a); }
int main()
{
    cin>>s1>>s2>>m>>n>>l;
    a=m-n; b=l; c=s2-s1;
    This=GCD(a,b);
    if(c%This) cout<<"Impossible"<<endl;
    else
    {
        EXGCD(a,b);
        cout<<(x%LCM(a,b)+LCM(a,b))%LCM(a,b)<<endl;
    }
    return 0;
}