扩展欧几里德。

扩展欧几里德: 给一个线性方程X*a+Y*b=m，给出a,b,m让求解X和Y。

首先，只有m%gcd(a,b)==0 时 该线性方程才有解。

假使a=k1 *gcd(a,b),b=k2 * gcd(a,b);

那么方程左边就等于(X*k1+Y*k2)*gcd(a,b),所以仅当m能被gcd(a,b)整除时方程才有解。

为了求上述方程的解，我们不妨先来求方程a*X+b*Y=gcd(a,b)的解,设d=m/gcd(a,b);

所以a*(d*X)+b*(d*y)=d*gcd(a,b)=m,求出这个方程的解原方程的解也就求出了。

根据欧几里德有gcd(a,b)=gcd(b,a%b)

所以a*X+b*Y=gcd(a,b)=gcd(b,a%b)=b*X1+(a%b)*Y1;

令k=a/b , r=a%b

a=b*k+r;

得出X=Y1 ,  Y=X1-Y1*(a/b);

__int64 X，Y; //全局变量

void extend_GCD(__int64 a,__int64 b)

{

    __int64 X1,Y1;

    if(b==0)

    {

        X=1;

        Y=0;

        return;

    }

    extend_GCD(b,a%b);

    X1=Y;

    Y1=X-Y*(a/b);

    X=X1;

    Y=Y1;

}

这样X*d,Y*d就是原方程的一组解。

满足方程的解有无数多个，a*(X + n*b) + b*(Y - n*a)=m; n=(...-2,-1,0,1,2...);

一般是让求最小的X并且X>=0，我们只需找X,每一个X都对应唯一的一个Y.

X所以最后的解为X%b,如果为负数就再加b

1 # include
      
        2 # include
       
         3 # include
        
          4 __int64 X,Y; 5 __int64 gcd(__int64 a,__int64 b) 6 { 7     __int64 tmp; 8     while(a%b) 9     {10         tmp=a%b;11         a=b;12         b=tmp;13     }14     return b;15 }16 void extend_GCD(__int64 a,__int64 b)17 {18     __int64 X1,Y1;19     if(b==0)20     {21         X=1;22         Y=0;23         return;24     }25     extend_GCD(b,a%b);26     X1=Y;27     Y1=X-Y*(a/b);28     X=X1;29     Y=Y1;30 }31 int main()32 {33     __int64 d,a,b;34     while(scanf("%I64d%I64d",&a,&b)!=EOF)35     {36         d=gcd(a,b);37         if(d!=1) {printf("sorry\n");continue;}38         extend_GCD(a,b);39         X=X%b;40         if(X<0) X+=b;41         Y=(1-X*a)/b;42         printf("%I64d %I64d\n",X,Y);43     }44     return 0;45 }