所谓扩展欧几里德,就是在欧几里德算法的基础上加入变量X,Y,使得aX-bY=GCD(a,b)。   此时X，Y是该不定方程式的一组解。     求a * x + b * y = n的整数解的过程:   1、先计算Gcd(a,b)，若c不能被Gcd(a,b)整除，则方程无整数；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此时Gcd(a',b')=1;   2、利用上面所说的欧几里德算法求出方程a' * x + b' * y = 1的一组整数解x0,y0，则n' * x0,n' * y0是方程a' * x + b' * y = n'的一组整数解；   3、根据数论中的相关定理，可得方程a' * x + b' * y = n'的所有整数解为：             x = n' * x0 + b' * t            y = n' * y0 - a' * t                (t为整数) 上面的解也就是a * x + b * y = n 的全部整数解。     关于1061的解法   由题意:     (x+mt)-(y+nt)=pL =>(m-n)t-(y-x)=pL =>(m-n)t-pL=(y-x) 即  (m-n)t≡(y-x)MOD(L) 令a=m-n,b=L,c=y-x,X=t,Y=p   则原等式转换为 aX-bY=c 使用扩展欧几里德 求出一组解X0,Y0=>aX0-bY0=GCD(a,b) 令d=GCD(a,b) 若c%d!=0 则无解 否则对于等式 aX0-bY0=d =>a[X0/d]-b[Y0/d]=1 =>a[c*X0/d]-b[c*Y0/d]=c 此时c*X0/d即为所求的t 可以证明其为在0附近的最小解，由于c可能小于0，则加b（X增b，Y减a,和不变）使之为正解。   实现代码如下:    #include <iostream>using namespace std;long long X,Y; long long extendGCD(long long a,long long b){    if (b==0)    {        X=1;        Y=0;        return a;    }    long long d=extendGCD(b,a%b);    long long t=X;    X=Y;    Y=t-(a/b)*X;     return d;} int main(){    long long x,y,m,n,L;    while (cin>>x>>y>>m>>n>>L)    {        long long A=m-n;            long long B=L;        long long C=y-x;         if (A<0)        {            A=-A;            C=-C;        }         long long d=extendGCD(A,B);         if (m==n||C%d!=0)        {            printf("Impossible\n");        }        else        {            B/=d;            C/=d;            long long t=C*X;            cout<<(t%B+B)%B<<endl;        }    }    return 0;}      

评论