扩展欧几里德和模线性性方程

定理一：设 a, b, c 是三个不全为 0 的整数。如果 a= b* q+ c， 其中 q 是整数，则 (a,b)= (b,c).

证明：设 d1= (a,b)， d2= (b,c). 有 d1| a+ (-q)* b，所以 d1| c，因而 d1 为 b, c 的公约数，所以 d1<= d2。

同理，d2 是 a, b 的公因数，有 d2<= d1，故 d1== d2，定理成立。

 

由定理一，可得到求最大公约数的欧几里德算法：

int gcd( int a, int b ){
    return !b? a: gcd( b, a% b );
}

有一结论: 对于正整数 a, b，(a,b)= d，则 d 一定可以表示成 d= ax+ by， x, y 为整数。

故 gcd(a,b) 可以写成如下形式，gcd(a,b)= ax+ by,  x, y 为整数，用扩展欧几里德算法可以求出 x, y。

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


 以上算法中，b== 0 时，返回 a, x0= 1, y0= 0, 满足 a= a*x0+ b* y0。

b!= 0 时，算法先计算出 d= gcd( b, a% b ) 和 x, y，并且满足：

d= b* x0+ (a% b )* y0

所以， gcd(a,b)= gcd(b,a%b)= d= b* x0+ (a% b)* y0= b* x0+ ( a- [a/b]* b)* y0

          = a* y0+ b* ( x0- [a/b]* y0 )= y0* a+ (x0- [a/b]* y0)* b

因此更新 x= y0, y= (x0+ [a/b]* y0) 可以满足等式 d= ax+ by，这样就证明算法的正确性。

 

定理二：同余方程 ax=b (mod n) 对于未知数 x 有解，仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。

证明比较复杂。不难得出，由这个定理可以推出以上的那个结论 gcd(a,b)= ax+ by 这样表示。

 

特别的，如果 gcd(a,n)== 1，则方程只有唯一解。在这种情况下，如果 b== 1，同余方程就是 ax=1 (mod n ),

gcd(a,n)= 1。这时称求出的 x 为 a 的对模 n 乘法的逆元。

 

对于同余方程 ax= 1(mod n )， gcd(a,n)= 1 的求解就是求解方程

ax+ ny= 1，x, y 为整数。这个可用扩展欧几里德算法求出，原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。

 

定理三：设 d= gcd(a,n)，假如整数 x 和 y，满足 d= ax+ ny(用扩展欧几里德得出)。如果 d| b，则方程

ax= b( mod n ) 的一个解为 x0= x* (b/ d ) mod n，且方程的 d 个解分别为 xi= x0+ i* (n/ d ) {i= 0... d-1}。

 

求解方程 ax= b (mod n ) 相当于求解方程 ax+ ny= b, (x, y为整数)

a* x0+ n* y0= d， 方程两边乘以 b/ d，(因为 d|b，所以能够整除)，得到 a* x0* b/ d+ n* y0* b/ d= b。

所以 x= x0* b/ d，y= y0* b/ d 为 ax+ ny= b 的一个解，所以 x= x0* b/ d 为 ax= b (mod n ) 的解。

 

a* xi mod  n= a( x0+ i* n/ d ) mod n

                   = ( a* x0+ a* i* n/ d ) mod n

                   = a* x0 mod n   ( 因为 d| a )

                   = b。

 

pku 1061 青蛙的约会

由题意，我们设要跳 p 次才能相遇， 则有方程 (m- n)* p= y- x (mod L )，就是求解一个同余方程。

代码：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long INT;

INT x, y, m, n, l;

INT gcd( INT a, INT b ){
    return b== 0? a: gcd( b, a% b ); }

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

int main(){
    while( cin>> x>> y>> m>> n>> l ){
        INT g= gcd( m- n, l );
        if( (y- x)% 0 ){
            cout<< "Impossible" << endl;
            continue;
        }
        
        INT p, q;
        extend_gcd( m- n, l, p, q );
        INT ans= p* (y- x)/ g;
        
        cout << ( ans% l+ l )% l << endl;
    }