扩展欧几里得
在数论中，一般用 ( a , b ) (a,b) (a,b)表示 a , b a,b a,b的最大公约数，用 [ a , b ] [a,b] [a,b]表示 a , b a,b a,b的最小公倍数
引入
如何求两个数的最大公约数？
欧几里得算法
- 这是求两个数最大公约数的方法
- 初中我们就已经学过计算最大公约数有辗转相除法和更相减损术两种方法，其实也可以合并为一种方法，因为后者是作减法，相对于前者做除法显然速度慢很多，辗转相除法也就是欧几里德算法
- 算法核心很简单，假设有两个数 a , b ( b < a ) a,b(b\lt a) a,b(b<a)现在要求他们俩的最大公约数，那么，根据整除的性质， a = b q + r ( r < b ) a=bq+r(r\lt b) a=bq+r(r<b)，所以 ( a , b ) = ( b , r ) = ( b , a % b ) (a,b)=(b,r)=(b,a\%b) (a,b)=(b,r)=(b,a%b)，这样一直进行下去，直到出现 a % b = 0 a\%b=0 a%b=0，此时就表示找到了他们的最大公约数 b b b，程序如下
int GCD(int a, int b){
return b == 0 ? a : GCD(b, a % b);
}
扩展欧几里得算法
已知 a , b , c a,b,c a,b,c均为整数，如何求 a x + b y = c ax+by=c ax+by=c的一组整数解 ( x , y ) (x,y) (x,y)
- 首先 c c c必须是 ( a , b ) (a,b) (a,b)的倍数，否则无解。因为 a = k 1 × ( a , b ) b = k 2 × ( a , b ) a=k_1\times (a,b)\\b=k_2\times (a,b) a=k1×(a,b)b=k2×(a,b)所以 a x + b y = ( k 1 x + k 2 y ) × ( a , b ) ≡ 0 ( m o d ( a , b ) ) ax+by=(k_1x+k_2y)\times (a,b) \equiv0\pmod{(a,b)} ax+by=(k1x+k2y)×(a,b)≡0(mod(a,b))故 c = k × ( a , b ) c=k\times (a,b) c=k×(a,b)
- 接下来，由于 ( a , b ) ∣ c (a,b)|c (a,b)∣c，故只考虑 a x + b y = ( a , b ) ax+by=(a,b) ax+by=(a,b)即可，根据欧几里德算法，有 a x + b y = ( a , b ) = ( b , a % b ) = b x ′ + ( a % b ) y ′ = ( a − b ⌊ a b ⌋ ) y ′ + b x ′ = a y ′ + b ( x ′ − ⌊ a b ⌋ y ′ ) ax+by=(a,b)=(b,a\%b)=bx'+(a\%b)y'=(a-b\lfloor \frac{a}{b}\rfloor)y'+bx'=ay'+b(x'-\lfloor \frac{a}{b}\rfloor y') ax+by=(a,b)=(b,a%b)=bx′+(a%b)y′=(a−b⌊ba⌋)y′+bx′=ay′+b(x′−⌊ba⌋y′)根据恒等原理，得到 { x = y ′ y = x ′ − ⌊ a b ⌋ y ′ \begin{cases}x=y'\\y=x'-\lfloor \frac{a}{b}\rfloor y'\\\end{cases} {x=y′y=x′−⌊ba⌋y′
- 现在我们想要求 x , y x,y x,y，根据这个式子，我们可以发现，可以通过 x ′ , y ′ x',y' x′,y′求取 x , y x,y x,y，也就是从后往前推，这可以通过递归来实现，那么我们就必须要找到最后一个是谁，这样才能够实现一个完整递归，根据欧几里德定理，可以发现最后一个数应该是出现某个 a % b = 0 a\%b=0 a%b=0，也就是 ( a , b ) = ( b , a % b ) = ( b , 0 ) = b = b x ′ (a,b)=(b,a\%b)=(b,0)=b=bx' (a,b)=(b,a%b)=(b,0)=b=bx′此时 x ′ = 1 , y ′ = 0 x'=1,y'=0 x′=1,y′=0为递归出口，算法写成程序如下
void extend_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1;
y = 0;
return;
}
extend_gcd(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
}
- 扩展欧几里德程序中蕴含着欧几里德，故可直接求出最大公约数，其中 x , y x,y x,y均须传引用，因为需要传回答案
例题
两只青蛙在环形路上跳，起点分别为 x , y x,y x,y，速度分别为 m , n m,n m,n，路长为 l l l，青蛙同向一起跳，问何时最早相遇或不可相遇
- 设时间为 t t t，可列出方程 x + m t − ( y + n t ) = l k x+mt-(y+nt)=lk x+mt−(y+nt)=lk移项，得到 ( n − m ) t + l k = x − y (n-m)t+lk=x-y (n−m)t+lk=x−y
- 很明显是扩展欧几里德，如果 g c d ( ( n − m ) , l ) ∤ ( x − y ) gcd((n-m),l)\nmid (x-y) gcd((n−m),l)∤(x−y)，则无解，否则有解
- 现在要求 t t t，先求 ( n − m ) t + l k = g c d ( ( n − m ) , l ) (n-m)t+lk=gcd((n-m),l) (n−m)t+lk=gcd((n−m),l)的解，之后再把求得的 t t t乘 x − y g c d \frac{x-y}{gcd} gcdx−y即可
- 但是这个问题可能出现负数，这时候因为 t t t是正数，系数不能为负，需要化正，同时最后需要求模保证最小，问题是模谁，这里做个证明 a x 0 + b y 0 = c = a x 1 + b y 1 ax_0+by_0=c=ax_1+by_1 ax0+by0=c=ax1+by1有 a ( x 0 − x 1 ) = b ( y 1 − y 0 ) a(x_0-x_1)=b(y_1-y_0) a(x0−x1)=b(y1−y0) x 0 = x 1 + k b g c d ( a , b ) x_0=x_1+k\frac{b}{gcd(a,b)} x0=x1+kgcd(a,b)b这个题最后需要模 l g c d ( n − m , l ) \frac{l}{gcd(n-m,l)} gcd(n−m,l)l
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 100;
const double eps = 1e-6;
int Data[MAXN];
ll GCD(ll a, ll b){
return b == 0 ? a : GCD(b, a % b);
}
void extend_gcd(ll a, ll b, ll &x, ll &y){
if(b == 0){
x = 1;
y = 0;
return;
}
extend_gcd(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - a / b * y;
}
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ll x, y, m, n, l, k, t;
cin >> x >> y >> m >> n >> l;
ll mn = n - m;
ll xy = x - y;
if(mn < 0){
mn = -mn;
xy = -xy;
}
ll gcd = GCD(mn, l);
if(xy % gcd != 0){
cout << "Impossible";
}else{
ll o = xy / gcd;
extend_gcd(mn, l, t, k);
l /= gcd;
cout << (l + t * o % l) % l;
}
return 0;
}