• <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>

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            poj 1061(線性同余)--青蛙的約會

            http://poj.org/problem?id=1061

            剛剛學了點數論,也好幾天沒有寫代碼了,生疏了不少,總是有錯誤,編譯個程序怎么都那么糾結啊,看來水平實在是差啊!!
            線性同余,方程還是很好就構造出來了,extended_euclid,中國剩余定理,可是后面卻不指導怎么求最小的整數了:
            看了看大牛的題解,原來這樣啊,自己數論還得多學學才行,多想想啊:

            分析:設青蛙跳了k次,那么就有(x+mk)-(y+nk)=p*L.

            即x-y+(m-n)k=p*L,即(m-n)*k≡(y-x) (mod L).

            這個線性同余方程有解當且僅當gcd(m-n,L)|(y-x).

            令a=m-n,b=L,c=y-x.用擴展歐幾里得解方程ax+by=c.

            可以求出原方程的一個解.如何求最小正整數解呢?

            假設我們已經得到一個x0,令d=gcd(m-n,L),

            那么所有解可以表示為x=x0+k*L/d.

            設L'=L/d.

            Xmin=(x0 mod L'+L') mod L'.


            WA兩次,0Ms,囧,還有一次編譯錯誤!!!

            #include<stdio.h>
            #include
            <string.h>
            #include
            <math.h>
            long long  c,d;
            long long gcd_ext(long long a,long long b)
            {
                
            long long gcd,t;
                
            if (!b)
                {
                    c
            =1;d=0;
                    
            return a;
                }
                gcd
            =gcd_ext(b,a%b);
                t
            =c;c=d;d=t-a/b*d;
                
            return gcd;
            }
            int main()
            {
                
            long long x,y,m,n,L,a,b,gcd;
                
            while (scanf("%I64d%I64d",&x,&y)==2)
                {
                    scanf(
            "%I64d%I64d%I64d",&m,&n,&L);
                    a
            =m>n?m-n:n-m;
                    b
            =m>n?y-x:x-y;
                    gcd
            =gcd_ext(a,L);
                    L
            =L/gcd;
                    
            if (b%gcd==0)
                        printf(
            "%I64d\n",((c*b/gcd)%L+L)%L);
                    
            else
                        printf(
            "Impossible\n");
                }
                
            return 0;
            }


            總結:代碼,還是得天天寫,三日不練手生。自己多想想,多思考思考才能提升能力哈。

                     不要總是去看別人的題解,要有自己的思路哈。

                     數論,還得繼續(xù)看,繼續(xù)學。要吃透才行。


            posted on 2012-04-12 00:18 wangs 閱讀(575) 評論(0)  編輯 收藏 引用 所屬分類: ACM-模擬

            新狼窝色AV性久久久久久| 久久AAAA片一区二区| 要久久爱在线免费观看| 久久夜色精品国产噜噜噜亚洲AV | 一本一道久久精品综合| 欧美久久一级内射wwwwww.| 国产成人久久AV免费| 日韩欧美亚洲综合久久| 久久www免费人成看国产片| 亚洲午夜无码久久久久小说| 亚洲人成网亚洲欧洲无码久久| 久久99精品国产麻豆蜜芽| 久久久SS麻豆欧美国产日韩| 久久亚洲精品国产精品婷婷| 久久精品国产亚洲7777| 办公室久久精品| 久久99精品国产麻豆婷婷| 久久九九久精品国产免费直播| 久久免费美女视频| 久久99国产精品久久99| 亚洲综合精品香蕉久久网97 | 91久久香蕉国产熟女线看| 一本一本久久A久久综合精品| 久久精品一区二区三区中文字幕| 婷婷久久久亚洲欧洲日产国码AV| 免费一级欧美大片久久网| 欧美麻豆久久久久久中文| www.久久热| 久久国产乱子伦精品免费午夜| 99久久婷婷国产综合亚洲| 性高湖久久久久久久久| 伊人久久精品无码二区麻豆| 中文字幕无码久久人妻| 四虎亚洲国产成人久久精品| 久久影院午夜理论片无码| 久久人妻少妇嫩草AV蜜桃| 久久精品女人天堂AV麻| 久久免费大片| 综合久久精品色| 亚洲国产精品无码久久98| 亚洲AV无码一区东京热久久|