• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            yuanyuelang

            常用鏈接

            統計

            最新評論

            數論(2)-------擴展歐幾里得算法

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

            1.應用:
                  線性方程ax+by=c ,已知a,b,c,求解x,y.

            2.基本思路:
                
                  ax+by=c有解 => c=k*gcd(a,b)=kd(因為d=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變量,最后得到解。(可結合下面代碼源代碼進行理解)

                  接下來我們來看看ax'+by'=d和ax+by=c之間的關系
                  
                    (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為任意整數
            (注意,當要求y-qa的最小正整數min時,由y-qa>=0, q取[y/a]最小,min=y-[y/a]y,但是,[y/a]可能為0,如果y是負數,min此時也為負數,不好,此時令min+=a就可以取得最小正整數值了([y/a]=0所以|y|<a),這段可以自己找個例子好好理解下啊)

            3.源代碼模板
             1int 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//用擴展歐幾里得算法解線性方程ax+by=c;
            13bool 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;//求的只是其中一個解
            20    return true;
            21}

            四.學習心得
                擴展歐幾里得算法的妙用,值得好好體會,對整個過程自己可以找個例子好好印證一下,肯定印象深刻。去Google一下POJ上的這方面的題目好好實踐一下吧!!!

            posted on 2009-09-05 16:51 原語餓狼 閱讀(4238) 評論(4)  編輯 收藏 引用 所屬分類: 數論

            評論

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

            頂  回復  更多評論   

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

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

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

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

            min=y-[y/a]y錯了.  回復  更多評論   

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

            定理:gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不為0)  回復  更多評論   

            亚洲国产一成久久精品国产成人综合| 四虎国产精品成人免费久久| 久久综合88熟人妻| 国产成人无码久久久精品一| 69SEX久久精品国产麻豆| 2022年国产精品久久久久| 国产精品久久久久久久午夜片 | 久久夜色精品国产噜噜麻豆| 亚洲精品无码专区久久久| 2022年国产精品久久久久| 久久久精品久久久久久| 色欲久久久天天天综合网精品 | 99久久成人国产精品免费| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 久久精品国产精品亚洲毛片| 情人伊人久久综合亚洲| 久久乐国产综合亚洲精品| 女人香蕉久久**毛片精品| 亚洲中文久久精品无码| 精品久久久无码中文字幕天天| 亚洲精品美女久久777777| 日本久久中文字幕| 99久久亚洲综合精品成人| 狠狠色婷婷久久综合频道日韩| 天天综合久久久网| 国产精品久久成人影院| 精品久久久久久久国产潘金莲| 婷婷综合久久中文字幕| 久久精品中文闷骚内射| 欧美黑人激情性久久| 亚洲&#228;v永久无码精品天堂久久 | 一本一本久久A久久综合精品| 欧美日韩精品久久久久| 色综合合久久天天综合绕视看 | 久久人人爽人人人人爽AV| 人人狠狠综合久久亚洲| 国产高潮久久免费观看| 国内精品伊人久久久久AV影院| 99久久夜色精品国产网站| 香蕉久久久久久狠狠色| 久久成人小视频|