歐式算法c語言,C語言算法

本文目錄一覽：

• 1、歐幾里得算法（輾轉相除法）
• 2、用歐幾里得算法（輾轉相除法）求最大公約數,C語言編程
• 3、用C語言編製的求模逆元的擴展歐幾里德算法，只要能基本上實現這個功能就行
• 4、使用歐幾里得算法，求給定兩個整數的最大公約數。

歐幾里得算法（輾轉相除法）

就是把上一輪有餘數的除法計算中，

除數變為下一輪計算的被除數，

餘數變為下一輪計算的除數，

一直這樣計算下去，

直到最後一次計算餘數為零，

在最後一輪計算中的被除數，即為所求的最大公約數。

舉例：

105和85的最大公約數

第一輪計算

105÷85=1…20

第二輪計算

85÷20=4…5

第三輪計算

20÷5=4

第三輪沒有餘數，

因此

105和85的最大公約數就是第三輪計算的被除數

5.

至於C語言編程，下邊是我自己寫的G函數(思想就是輾轉相除法求最大公約數)

int

G(int

x,int

y)

{

int

t;

while(y!=0)

{

t=x%y

;

x=y;

y=t;

}

return

x;

}

用歐幾里得算法（輾轉相除法）求最大公約數,C語言編程

你的程序是正確的，

瑕疵在於

scanf(“%d,%d”,m,n);

scanf函數，雙引號內光寫格式就好了，不用寫逗號什麼的，多寫什麼程序運行的時候就要輸入什麼。如你所寫，運行時就應輸入：12，24 若你在12與24之間按的是空格或其他有可能影響到第二個變量取不到值。

所以建議改為

scanf(“%d%d”,m,n); 程序運行要求輸入時兩個數之間按空格回車隨你。

用C語言編製的求模逆元的擴展歐幾里德算法，只要能基本上實現這個功能就行

擴展歐幾里德算法是用來在已知a, b求解一組x，y，使它們滿足貝祖等式： ax+by = gcd(a, b) =d（解一定存在，根據數論中的相關定理）。擴展歐幾里德常用在求解模線性方程及方程組中。

下面是一個使用C語言的實現：

intexGcd(int a,int b,int x,int y)

{

    if(b==0)    //當b==0時，得到解

    {

        x=1;y=0;

        return a;

    }

    intr=exGcd(b,a%b,x,y);//遞歸調用自身，求解

    intt=x;x=y;y=t-a/b*y;

    return r;

}

使用歐幾里得算法，求給定兩個整數的最大公約數。

歐幾里德算法

歐幾里德算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

證明：a可以表示成a = kb + r，則r = a mod b

假設d是a,b的一個公約數，則有

d|a, d|b，而r = a – kb，因此d|r

因此d是(b,a mod b)的公約數

假設d 是(b,a mod b)的公約數，則

d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公約數

因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證

歐幾里德算法就是根據這個原理來做的，其算法用C++語言描述為：

void swap(int a, int b)

{

int c = a;

a = b;

b = c;

}

int gcd(int a,int b)

{

if(0 == a )

{

return b;

}

if( 0 == b)

{

return a;

}

if(a b)

{

swap(a,b);

}

int c;

for(c = a % b ; c 0 ; c = a % b)

{

a = b;

b = c;

}

return b;

}

模P乘法逆元

對於整數a、p，如果存在整數b，滿足ab mod p =1，則說，b是a的模p乘法逆元。

定理：a存在模p的乘法逆元的充要條件是gcd(a,p) = 1

證明：

首先證明充分性

如果gcd(a,p) = 1，根據歐拉定理，aφ(p) ≡ 1 mod p，因此

顯然aφ(p)-1 mod p是a的模p乘法逆元。

再證明必要性

假設存在a模p的乘法逆元為b

ab ≡ 1 mod p

則ab = kp +1 ，所以1 = ab – kp

因為gcd(a,p) = d

所以d | 1

所以d只能為1

擴展歐幾里德算法

擴展歐幾里德算法不但能計算(a,b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用C語言描述如下：

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的乘法逆元。