扩展欧几里得【知识点】

扩展欧几里得定理：对于两个不全为0的整数a、b，必存在一组解x,y，使得ax+by == gcd(a,b);

代码实现：

 1 #include <iostream>
 2 using namespace std;
 3 int x,y;
 4 int extend_Eulid(int a,int b)
 5 {
 6     if(b==0)
 7     {
 8         x=1;
 9         y=0;   
10         return a;
11     }
12     int ans = extend_Eulid(b,a%b);
13     int temp=x;
14     x=y;
15     y=temp-(a/b)*y;  
16     return ans;
17 }
18 int main()
19 {
20     int a,b;
21     cin>>a>>b;
22     if(a < b)
23     swap(a,b);//交换a b的位置 
24     int q = extend_Eulid(a, b);
25     printf("%d=(%d)*%d+(%d)*%d
",q,x,a,y,b);
26     return 0;
27 }

y = 0; 解释：由扩展欧几里得定理：ax+by==gcd(a,b)---式1，而此时b==0，也就是说gcd(a,0)==a。原式变为ax+by==a --> x==1,y==0。应该够清楚了吧

      y=temp-(a/b)*y;  解释 ：这里先说明一下我的一些规则，x,y表示第一次递归时的值，x1,y1表示第二次递归时的值。那么gcd(a,b)==gcd(b,a%b)，同时都代入式1，有ax+by==b*x1+(a%b)*y1。将右边变形一下 b*x1+(a%b)*y1  ==  b*x1+(a-(a/b)*b)*y1  ==  a*y1+b*(x1-(a/b)*y1)，最终得到ax+by==a*y1+b*(x1-(a/b)*y1)也就是说，上一深度的x等于下一深度的y1，上一深度的y等于下一深度的x1-(a/b)*y1。   （ 需要注意，上面推导时用的除法都是整型除法）

解不定方程ax+by=c

对于不定整数方程ax+by=c ，若 c % gcd(a,b)=0,则该方程存在整数解，否则不存在整数解。

故当c % gcd(a,b)=0，先用扩展欧几里得算法求出ax+by=gcd(a,b)的一组解x1,y1。

则x2=x1*c/gcd(a,b)，y2=y1*c/gcd(a,b)为ax+by=c的一组解。

x=x2+b/gcd(a,b)*t,

y=y2-a/gcd(a,b)*t,

(t为整数)，即为ax+by=c的所有解。