講解拓展的歐幾里德算法：
一、內容：
對于不完全為 0 的非負整數 a，b，gcd（a，b）表示 a，b 的最大公約數，必然存在整數對 x，y ，使得 gcd（a，b）=ax+by。如果gcd(a, b)＝d，那么一定存在x，y滿足ax＋by＝d；
二、推導: 如何求 x y
設 a>b。
1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
2，ab<>0 時
設 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根據樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);
則:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據恒等定理得：x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
三、算法如下：
int exGcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int r = exGcd(b, a % b, x, y);
int temp = x; // x 即 返回的x2
x = y; // x 即要求的 x1
y = temp - a / b * y;
} 理解遞歸 例：a = 48，b = 22 得到 x = 11， y = -24
posted on 2010-08-28 22:05
雪黛依夢 閱讀(316)
評論(0) 編輯 收藏 引用 所屬分類:
數論