yuanyuelang

導(dǎo)航

<

2011年10月

>

日

一

二

三

四

五

六

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

隨筆 - 0
文章 - 10
評(píng)論 - 5
引用 - 0

數(shù)論(2)-------擴(kuò)展歐幾里得算法

擴(kuò)展歐幾里得算法------求解線性方程ax+by=c

1.應(yīng)用：
      線性方程ax+by=c ,已知a,b,c，求解x,y.

2.基本思路：

      ax+by=c有解 => c=k*gcd(a,b)=kd（因?yàn)閐=gcd(a,b)=>d|(ax+by))

      我們先考慮求解 ax+by=d
        由歐幾里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'
        則由上述兩式子，我們可以得出 x=y' ,y=x'-[a/b]y'
        這樣子，在歐幾里得算法添加x,y變量，最后得到解。（可結(jié)合下面代碼源代碼進(jìn)行理解）

      接下來我們來看看ax'+by'=d和ax+by=c之間的關(guān)系

        （c/d)ax'+(c/d)by'=(c/d)d 即可以得到 x=(c/d)x',y=(c/d)y'

         所以可以得到ax+by的一組解
         那么ax+by=c所有解的形式是什么呢？
             a(x+qb)+b(y-qa)=c; q為任意整數(shù)
(注意，當(dāng)要求y-qa的最小正整數(shù)min時(shí),由y-qa>=0， q取[y/a]最小，min=y-[y/a]y,但是,[y/a]可能為0，如果y是負(fù)數(shù)，min此時(shí)也為負(fù)數(shù)，不好，此時(shí)令min+=a就可以取得最小正整數(shù)值了（[y/a]=0所以|y|<a),這段可以自己找個(gè)例子好好理解下?。?br>
3.源代碼模板

1

int Extended_Euclid(int a,int b,int& x,int &y)
2

{
3

if(b==0){
4

x=1;
5

y=0;
6

return a;
7

}
8

int d=Extended_Euclid(b,a%b,x,y);
9

int temp=x;x=y;y=temp-a/b*y;
10

return d;
11

}
12

//用擴(kuò)展歐幾里得算法解線性方程ax+by=c;
13

bool linearEquation(int a,int b,int c,int& x,int &y)
14

{
15

int d=Extended_Euclid(a,b,x,y);
16

if(c%d) return false;
17

18

int k=c/d;
19

x*=k;y*=k;//求的只是其中一個(gè)解
20

return true;
21

}

四.學(xué)習(xí)心得
擴(kuò)展歐幾里得算法的妙用，值得好好體會(huì)，對(duì)整個(gè)過程自己可以找個(gè)例子好好印證一下，肯定印象深刻。去Google一下POJ上的這方面的題目好好實(shí)踐一下吧?。。?/span>

posted on 2009-09-05 16:51 原語(yǔ)餓狼閱讀(4258) 評(píng)論(4) 編輯收藏引用所屬分類: 數(shù)論

評(píng)論

# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法 2011-02-02 09:34 ding

頂回復(fù) 更多評(píng)論

# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法 2011-04-07 23:08 曉楠

由歐幾里得算法,d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b])y'

這句話應(yīng)該是
d=bx'+(a mod b)y'=bx'+(a-[a/b]b)y'=ay'+b(x'-[a/b]y')
回復(fù) 更多評(píng)論

# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法 2011-10-03 17:34 CrazyForAC

min=y-[y/a]y錯(cuò)了. 回復(fù) 更多評(píng)論

# re: 數(shù)論(2)-------擴(kuò)展歐幾里得算法 2013-12-15 20:43 s

定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不為0) 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: 數(shù)論(4)--------求解模線性方程數(shù)論(3)-------歐拉phi函數(shù) 數(shù)論(2)-------擴(kuò)展歐幾里得算法數(shù)論(1)-----歐幾里得算法

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理