gcd就是求a和b最大公约数&＃xff0c;一般方法就是递推。不多说&＃xff0c;上代码。
一.迭代法
int gcd(int m, int n)
{ while(m>0) { int c &＃61; n % m; n &＃61; m; m &＃61; c; } return n;
}
二.递归法
int Gcd(int a, int b)
{if(b &＃61;&＃61; 0)return a;return Gcd(b, a % b);
}
但exgcd是个什么玩意&＃xff1f;&＃xff1f;&＃xff1f;
百度了一下&＃xff0c;百科这么讲的&＃xff1a;
存在整数对 x&＃xff0c;y &＃xff0c;使得 gcd&＃xff08;a&＃xff0c;b&＃xff09;&＃61;ax&＃43;by。
好像很好理解的样子&＃xff0c;百度还给了个代码
int gcd(int a,int b,int &x,int &y){if (b&＃61;&＃61;0){x&＃61;1,y&＃61;0;return a;}int q&＃61;gcd(b,a%b,y,x);y-&＃61;a/b*x;return q;
}
&＃xff1f;&＃xff1f;&＃xff1f;什么玩意&＃xff1f;&＃xff1f;&＃xff1f;
于是我又找了一段证明&＃xff1a;
证明&＃xff1a;当 b&＃61;0 时&＃xff0c;gcd(a,b)&＃61;a&＃xff0c;此时 x&＃61;1 , y&＃61;0当 b!&＃61;0 时&＃xff0c;设 ax1&＃43;by1&＃61;gcd(a,b)&＃61;gcd(b,a%b)&＃61;bx2&＃43;(a%b)y2又因 a%b&＃61;a-a/b*b则 ax1&＃43;by1&＃61;bx2&＃43;(a-a/b*b)y2ax1&＃43;by1&＃61;bx2&＃43;ay2-a/b*by2ax1&＃43;by1&＃61;ay2&＃43;bx2-b*a/b*y2ax1&＃43;by1&＃61;ay2&＃43;b(x2-a/b*y2)解得 x1&＃61;y2 , y1&＃61;x2-a/b*y2因为当 b&＃61;0 时存在 x , y 为最后一组解而每一组的解可根据后一组得到所以第一组的解 x , y 必然存在得证
于是刚才那段代码返回的是a和b的gcd
void exgcd(int a,int b)
{if (b){exgcd(b,a%b);int k&＃61;x;x&＃61;y;y&＃61;k-a/b*y; //k就是上一组的x-- y1 &＃61; x2 - a/b*y2;}else y&＃61;(x&＃61;1)-1;
}
还有一个斐蜀定理。。。
若a,b是整数,且&＃xff08;a,b)&＃61;d&＃xff0c;那么对于任意的整数x,y,ax&＃43;by都一定是d的倍数&＃xff0c;特别地&＃xff0c;一定存在整数x,y&＃xff0c;使ax&＃43;by&＃61;d成立。
京公网安备 11010802041100号