• <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 - 100,  comments - 15,  trackbacks - 0

            A+C*X=B(%2^K)
            C*X=B-A(%2^K)
            令a=c,b=B-A,n=2^K;
             利用以下結論(具體證明見《算法導論):
            推論1:方程ax=b(mod n)對于未知量x有解,當且僅當gcd(a,n) | b。
            推論2:方程ax=b(mod n)或者對模n有d個不同的解,其中d=gcd(a,n),或者無解。
            定理1:設d=gcd(a,n),假定對整數x和y滿足d=ax+by(比如用擴展Euclid算法求出的一組解)。如果d | b,則方程ax=b(mod n)有一個解x0滿足x0=x*(b/d) mod n 。特別的設e=x0+n,方程ax=b(mod n)的最小整數解x1=e mod (n/d),最大整數解x2=x1+(d-1)*(n/d)。
            定理2:假設方程ax=b(mod n)有解,且x0是方程的任意一個解,則該方程對模n恰有d個不同的解(d=gcd(a,n)),分別為:xi=x0+i*(n/d) mod n 。

            a*x=b(%n) => a*x+n*y=b
            d=ext_gcd(a,n,x0,y0)
            最小整數解x1=(x0*(b/d)%n+n)%(n/d);
              

            #include <iostream>
            using namespace std;
            __int64 exgcd(__int64 a, __int64 b, __int64 
            &x, __int64 &y)
            {
                
            if(b==0)
                
            {
                    x
            =1;y=0;return a;
                }

                __int64 r
            =exgcd(b, a%b, x, y);
                __int64 t
            =x;x=y;y=t-a/b*y;
                
            return r;
            }

            int main()
            {
                __int64 A,B,C,K;
                __int64 a,b,n,d,x,y,e;
                
            while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&K)!=EOF)
                
            {
                    
            if(A==0 && B==0 && C==0 && K==0break;
                    a
            =C;
                    n
            =((__int64)1<<K); //小心溢出
                    b=B-A;
                    d
            =exgcd(a, n, x, y);
                    
            if(b%d) {printf("FOREVER\n"); continue;}
                    e
            =x*(b/d)%n+n;
                    printf(
            "%I64d\n",e%(n/d));
                }

                
            return 0;
            }
            ;
            posted on 2010-03-31 22:48 wyiu 閱讀(400) 評論(0)  編輯 收藏 引用 所屬分類: POJ
            久久久久久精品成人免费图片 | 99久久er这里只有精品18| 久久精品免费全国观看国产| 欧美亚洲国产精品久久高清| 青青草国产精品久久久久| 亚洲国产成人精品无码久久久久久综合| 免费国产99久久久香蕉| 久久夜色精品国产亚洲| 亚洲国产精品嫩草影院久久| 97精品国产97久久久久久免费| 国内精品伊人久久久久AV影院| 人妻少妇久久中文字幕一区二区| 久久久久免费精品国产 | 久久99精品综合国产首页| 久久亚洲国产精品五月天婷| 久久久久无码精品国产不卡| 久久国产精品免费一区| 色欲久久久天天天综合网精品| 久久久久国产视频电影| 精品国产91久久久久久久| 久久久国产一区二区三区| 久久国产高潮流白浆免费观看| 久久五月精品中文字幕| a级成人毛片久久| 久久综合久久自在自线精品自| 人妻无码久久精品| 97久久精品午夜一区二区| 久久久国产精华液| 伊人热热久久原色播放www| 久久久中文字幕日本| 欧美亚洲国产精品久久蜜芽| 91精品国产91久久综合| 久久99国产精品尤物| 久久亚洲精品无码AV红樱桃| 国产成人无码精品久久久性色| 久久精品视频一| 久久久久一级精品亚洲国产成人综合AV区 | 久久综合香蕉国产蜜臀AV| 一级a性色生活片久久无少妇一级婬片免费放 | 久久久久女教师免费一区| 久久久久久久综合日本亚洲|