扩展欧几里得算法------求解线性方程ax+by=c
1.应用：
线性方程ax+by=c ,已知a,b,c，求解x,y.
2.基本思路：
ax+by=c有解 => c=k*gcd(a,b)=kd（因为d=gcd(a,b)=>d|(ax+by))
我们先考虑求解 ax+by=d
由欧几里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'
则由上述两式子，我们可以得出 x=y' ,y=x'-[a/b]y'
这样子，在欧几里得算法添加x,y变量，最后得到解。（可结合下面代码源代码进行理解）
接下来我们来看看ax'+by'=d和ax+by=c之间的关系
（c/d)ax'+(c/d)by'=(c/d)d 即 可以得到 x=(c/d)x',y=(c/d)y'
所以可以得到ax+by的一组解
那么ax+by=c所有解的形式是什么呢？
a(x+qb)+b(y-qa)=c; q为任意整数
(注意，当要求y-qa的最小正整数min时,由y-qa>=0， q取[y/a]最小，min=y-[y/a]y,但是,[y/a]可能为0，如果y是负数，min此时也为负数，不好，此时令min+=a就可以取得最小正整数值了（[y/a]=0所以|y|<a),这段可以自己找个例子好好理解下啊）
3.源代码模板
1int Extended_Euclid(int a,int b,int& x,int &y)
2{
3 if(b==0){
4 x=1;
5 y=0;
6 return a;
7 }
8 int d=Extended_Euclid(b,a%b,x,y);
9 int temp=x;x=y;y=temp-a/b*y;
10 return d;
11}
12//用扩展欧几里得算法解线性方程ax+by=c;
13bool linearEquation(int a,int b,int c,int& x,int &y)
14{
15 int d=Extended_Euclid(a,b,x,y);
16 if(c%d) return false;
17
18 int k=c/d;
19 x*=k;y*=k;//求的只是其中一个解
20 return true;
21}
int gcd(int a， int b ， int& ar，int & br)
{
int x1，x2，x3；
int y1，y2，y3；
int t1，t2，t3；
if(0 == a)
{ //有一个数为0，就不存在乘法逆元
ar = 0；br = 0 ；
return b；
}
if(0 == b)
{
ar = 0；br = 0 ；
return a；
}
x1 = 1；x2 = 0；x3 = a；
y1 = 0；y2 = 1；y3 = b；
int k；
for( t3 = x3 % y3 ； t3 ！= 0 ； t3 = x3 % y3)
{
k = x3 / y3；
t2 = x2 - k * y2；
t1 = x1 - k * y1；
x1 = y1；x1 = y2；x3 = y3；
y1 = t1；y2 = t2；y3 = t3；
}
if( y3 == 1)
{
//有乘法逆元
ar = y2；br = x1；
return 1；
}else{
//公约数不为1，无乘法逆元
ar = 0；br = 0；
return y3；
}
}
如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数(t1，t2，t3)，用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假设前k行都成立，考察第k+1行
对于k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分别满足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根据扩展欧几里德算法，假设t3(k-1) = j t3(k) + r
则：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
则
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得证
因此，当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
35x=1 (mod 3) x=2
35x+3y=1=gcd(35,3)=gcd(3,2)=gcd(2,1)=gcd(1,0);
ax+by=1=gcd(a,b)=gcd(b,a%b)=bX+a%bY=bX+(a-(a/b)b)Y=bX+aY-(a/b)bY=aY+b(X-(a/b)Y);
35x+3y=35y1+3(x1-11y1) x=y1 y=x1-11y1
3x1+2y1=3y2+2(x2-y2) x1=y2 y1=x2-y2
2x2+y2=2y3+(x3-2y3) x2=y3 y2=x3-2y3
triple Extended_Euclid(int a,int b)
{triple result;
if(b == 0){
result.d = a;
result.x = 1;
result.y = 0;
}else{
triple ee = Extended_Euclid(b,a%b);
result.d = ee.d;
result.x = ee.y;
result.y = ee.x - (a/b)*ee.y;
}
return result;
}
struct triple{
int d,x,y
};
int MLES(int a,int b,int n)
{ triple ee = Extended_Euclid(a,n);
if(mod(b,ee.d) == 0)
return mod((ee.x * (b / ee.d)),n / ee.d);
else
return -1;
}//返回-1为无解，否则返回的是方程的最小解说明：
ax≡b(mod n)解的个数：
如果ee.d 整除 b 则有ee.d个解；
如果ee.d 不能整除 b 则无解。
