仄巳嘛呀

以上算法中，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)% g!= 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;
     }
    
    return 0;
}

附加：TOJ2869 http://acm.tju.edu.cn/toj/showp2869.html

大意：已知a,b,c,n,求出一组x,y,z（满足条件的任意一组）使ax+by+cz=n.

若无解则输出-1.

直接给代码：

#include<iostream>
using namespace std;
int m1,n1;
int ext_gcd(int a,int b)
{
    if(b==0)
    {
            m1 = 1;
            n1 = 0;
            return a;
    }
    else
    {
        int dab = ext_gcd(b,a%b);
        int tm = m1;
        m1 = n1;
        n1 = tm - a/b*n1;
        return dab;
    }
}
int main()
{
    int a,b,c,n;
    while(cin>>a>>b>>c>>n)
    {
       int dab = ext_gcd(a,b);
        int ma,mb,mc;
       ma = m1; 
        mb = n1;
        int dabc = ext_gcd(dab,c);
        if(n%dabc != 0){cout<<-1<<endl; continue;}
        mc = n/dabc*n1;
        ma *= (n/dabc*m1);
        mb *= (n/dabc*m1);
        int mabc = (a * b * c)/dabc;
        while(ma<0)
        {
          ma += mabc/a;
          mc -= mabc/c;
        }
        while(mb<0)
        { 
          mb += mabc/b;
          mc -= mabc/c;
        }
        while(mc>0)
        {
          mc-=mabc/c;
          ma+=mabc/a;
        }
         mc = -mc;
        cout<<ma<<' '<<mb<<' '<<mc<<endl;
    }
    return 0;
}