扩展欧几里德

扩展欧几里德算法

关于不定方程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;
}