拓展欧几里得

2017/5/30
拓展欧几里得
求ax+by=c的值，如果c%（gcd(a,b))！=0则无解，将式子转化成求ax+by=gcd(a,b);得出特解x0,y0,则通解为
x=x0+(b/gcd(a,b))；
y=y0-(a/gcd(a,b)；
拓展欧几里得求ax+by=gcd(a,b)的最小整数解：
假如已知bx1+a%by1=gcd(a,b)的最小整数x1,y1。
b*x1+(a-a/b*b)y1=gcd(a,b)==>a*y1+b(x1-a/b*y1)=gcd(a,b)=ax+by=gcd(a,b),x=y1;
y=x1-a/b*y1;
拓展欧几里得：求ax+by=gcd(a,b)

int exGcd(int a,int b,int &x,int &y)
{
if(b==0)
    {
x=1;y=0;//b=0时a为gcd(a,b)

return a;    }

int r=exGcd(b,a%b,x,y);
int t=x;x=y,y=t-a/b*y;
return r;
}

2017/5/30
求ax+by=c:
通过求出的exGcd(a,b,x,y)，ax+by=gcd(a,b)式子两边同时乘以c/gcd(a,b)，ax+by=c成立了x,y就求出来了,但是所求的x不是最小的正整数解；
所以已知这一个特解，根据x=x0+(b/gcd(a,b))，y=y0-(a/gcd(a,b)就可以求最小正整数解了

long long kk(long long a,long long b,long long c)
{
long long k, x,y;
 t=exGcd(a,b,x,y);
if(c%k!=0)return -1;
  x*=c/t;
  b=b/t;//求x=x0+(b/gcd(a,b))里的b/gcd(a,b)
if(b<0)
    b=-b;//b值这并不是式子里的b值，只是通过它求a
  x=x%b;//相当于x=x0-(b/gcd(a,b))*k;
if(x<0)x+=b;
return x;
}

乘法逆元：
b*c≡1(modm);表示的是c是b关于模m的逆元,(modm)并不是式子的一部分，而是表示关于模m。
有逆元的条件是b与m互质,所以别忘了判断。
求法：
exGcd(b,m,x,y),求出的x就是b关于m的逆元，然而我们要求最小整数逆元，所以还得x=（m+x%m）%m.

女朋友给我讲的！！！