關於擴充套件歐幾里德演算法的c語言程式

1樓:匿名使用者

- -? 什麼歐幾里德的?

哈哈~~忘了。你說下~~

用c語言編寫擴充套件歐幾里德演算法用來求乘法逆元ab=1 mod(n) 要求我輸入b,n,求出a。請編譯執行通過,謝謝啦

2樓:有錢買不起房子

#include

int extendedeuclid( int f,int d ,int *result);

int main()

int extendedeuclid( int f,int d ,int *result)

if ( y3 == 1 )

q = x3/y3;

t1 = x1 - q*y1;

t2 = x2 - q*y2;

t3 = x3 - q*y3;

x1 = y1;

x2 = y2;

x3 = y3;

y1 = t1;

y2 = t2;

y3 = t3;}}

/*輸入兩個數:

5 14

5和14互素,乘法的逆元是:3*/

3樓:匿名使用者

這是一個錯誤的演算法啊

用c語言編制的求模逆元的擴充套件歐幾里德演算法,只要能基本上實現這個功能就行

4樓:匿名使用者

//舉例 3x+4y=1 ax+by=1

//得到一組解x0=-1,y0=1 通解為x=-1+4k,y=1-3k

返回a,b的***,同時求的一組滿足題目的最小正整數解

ans=extend_***(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;

return ans;

}//(a/b)%mod=c 逆元為p,(p*b)%mod=1

//(a/b)*(p*b)%mod=c*1%mod=c

// (p*b)%mod=1 等價於 p*b-(p*b)/mod*mod=1其中要求p,b已知 等價於 ax+by=1

//其中x=p(x就是逆元),y=p/mod,a=b,b=b*mod 那麼呼叫extend_***(b,b*mod,x,y)即可求(a/b)%mod的逆元等價於a*p%mod

int main()

cout<<"x="<

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

所以建議改為

scanf("%d%d",&m,&n); 程式執行要求輸入時兩個數之間按空格回車隨你。

7樓:匿名使用者

if(m

r=m;

m=n;

n=r;

這裡缺了點什麼

改if(m

認同求採納,求經驗,求懸賞

不認同可以問,有求必應

8樓:匿名使用者

刪掉if(m

r=m;

m=n;

n=r;就好了

c語言用歐幾里得演算法定義的求最大公約數的函式沒看懂,哪位大神能解釋一下?具體到每一步驟。

9樓:id雞蛋炒韭菜

if(x換,使得x是兩數中最大值,y是最小值

while(y!=0) //演算法核心,首先用x模y,取得餘數,然後每次用除數模餘數,直到整除為止

擴充套件歐幾里得演算法

10樓:諾諾愛熊貓

//歐幾米德演算法 //演算法描述:給定兩個正整數m和n,求他們的最大公因子。 //1.

[求餘數]用m除以n並令r為所得餘數 //2.[餘數為0]若r=0,則演算法結束,n即為所求答案 //3.[互換]置m←n,n←r,並返回步驟1。

#include #include using namespace std; int main(int argc, char *argv) cout << m<< endl; system("pause"); return exit_success; }

麻煩採納,謝謝!

擴充套件的歐幾里得演算法求逆元

11樓:匿名使用者

數對 x,y ,使得 ***(a,b)=ax+by。

c++語言實現

#include

#include

using namespace std;

int x,y,q;

void extend_eulid(int a,int b)else

}int main()

你給的題目實際上就是: 給定 a 和b。

a 要有逆元 , 那麼***( a , b ) = 1假設a的逆元 為x , 那麼就有 a * x mod b = 1

也就是 a * x + b * y = 1上面的程式中輸入a和b就可以求出對應的x和y。

其中 x 就是 a的逆元

擴充套件歐幾里德演算法是什麼歐幾里德演算法是什麼啊

擴充套件歐幾里德演算法是用來在已知a,b求解一組x，y，使它們滿足貝祖等式 ax by a,b d 解一定存在，根據數論中的相關定理 擴充套件歐幾里德常用在求解模線性方程及方程組中。下面是一個使用c 的實現 intr ex b,a b,x,y intt x x y y t a b y return ...

歐幾里德演算法的簡單解釋

編輯本段 歐幾里得演算法的概述 歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a，b的最大公約數。其計算原理依賴於下面的定理 定理 a,b 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是...

關於spend in doing句型的擴充套件

bas much as i can是修飾 i spent的。spend money time in doing sth.in可以省略。b與as much as i can中的can無關 選擇bspend doint 通常是spend some time money in doing sth,如 i ...