• <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>
            posts - 25,  comments - 0,  trackbacks - 0
            /*
            */
            #include <iostream>
            using namespace std;

            /*
            注意到對(duì)于gcd(a,b) = d 我們對(duì)(a, b)用歐幾里德輾轉(zhuǎn)相除會(huì)最終得到
            (d, 0)此時(shí)對(duì)于把a(bǔ) =d, b = 0 帶入a*x + b*y = d,顯然x = 1,y可以為任意值,
            這里y可以為任意值就意味著解會(huì)有無(wú)數(shù)個(gè)。我們可以用a = d, b = 0的情況逆推出來(lái)
            任何gcd(a, b) = d 滿足a*x + b*y = d的解。如果x0, y0是b*x + (a%b)*y = d 的解,
            那么對(duì)于a*x + b*y = d的解呢?
            b*x0 + (a%b)*y0 = d => b*x0 + (a - [a/b]*b)*y0 = a*y0 + b*(x0 - [a/b]*y0),
            所以a*x + b*y = d的解x1 = y0, y1 = x0 - [a/b]*y0; 這樣我們可以程序迭帶了。
            */
            int extEuclid(int a, int b, int &x, int &y)
            {
                if (b == 0)
                {
                    x = 1;
                    y = 0;
                    return a;
                }
                int d = extEuclid(b, a % b, x, y);
                int iTemp = x;
                x = y;
                y = iTemp - (a / b)* y;
                return d;
            }
            //解同余方程ax = b(mod n) (返回最小的正數(shù)x)

            int modularLinearEquation(int a, int b, int n)
            {
                //等價(jià)于求ax + cn = b;
                
            //先求a*x1 + c1*n = gcd(a, n)
                int x, y, d;
                d = extEuclid(a, n, x, y);
                if (b % d != 0)
                   return -1;
                x = x * (b / d);
                x = (( x % n) + n) % n;
                return x;
            }

            //中國(guó)剩余定理,推導(dǎo)都是數(shù)學(xué)
            int solModularEquations(int b[], int m[], int k)
            {

                int iTemp;
                int y;
                int result;

                int M = 1;
                for (int i = 0; i < k; i++)
                  M *= m[i];

                result = 0;
                for (int i = 0; i < k; i++)
                {
                  iTemp = M / m[i];
                  y = modularLinearEquation(iTemp, 1, m[i]);
                  result = (result + b[i] * iTemp * y) % M;
                }
                return result;
            }

            int main()
            {
                int x, y , d;
                d = extEuclid(1001, 767, x, y);
                cout << x << endl;
                cout << y << endl;
                cout << d << endl;
                cout << "1001 * x + 767 * y = " << (1001 * x + 767 * y) << endl;
                cout << modularLinearEquation(3, 2, 100) << endl;
                return 0;
            }
            posted on 2012-06-02 14:31 nk_ysg 閱讀(482) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法
            <2012年7月>
            24252627282930
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿

            隨筆分類

            隨筆檔案

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            亚洲国产成人久久精品99| 亚洲午夜无码AV毛片久久| 久久精品国产福利国产琪琪| 久久精品国产亚洲欧美| 国产精品久久久久久吹潮| 久久亚洲AV成人无码国产| 久久久久亚洲av无码专区喷水| 久久久久99这里有精品10 | 2022年国产精品久久久久| 久久香蕉国产线看观看精品yw| 亚洲精品白浆高清久久久久久| 国产成人无码精品久久久性色| 久久婷婷是五月综合色狠狠| 久久成人国产精品免费软件| 97精品依人久久久大香线蕉97| 亚洲国产美女精品久久久久∴ | 一级a性色生活片久久无| 久久这里都是精品| 精品久久久久久| 伊人久久免费视频| 欧美日韩精品久久久久| 亚洲精品无码专区久久久| 久久午夜无码鲁丝片| 91精品国产91久久久久久蜜臀| 久久人人爽人人爽人人片AV东京热 | 国产成人久久精品激情| 狠狠色噜噜狠狠狠狠狠色综合久久| 国产呻吟久久久久久久92| 亚洲v国产v天堂a无码久久| 久久久久亚洲av无码专区| 亚洲综合精品香蕉久久网97| 热久久国产欧美一区二区精品| 久久只有这精品99| 久久国产精品国产自线拍免费| 亚洲国产精品成人AV无码久久综合影院 | 思思久久好好热精品国产| 久久精品九九亚洲精品| 精品久久久久国产免费| 无码人妻久久久一区二区三区| 国产精品成人久久久久久久| 亚洲女久久久噜噜噜熟女|