• <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久久久无码| 精品久久777| 国产成人综合久久精品红| 久久99精品国产麻豆| 久久国产视屏| AV色综合久久天堂AV色综合在| 免费观看成人久久网免费观看| 久久伊人五月天论坛| 久久不见久久见免费视频7| 久久午夜综合久久| 久久婷婷国产麻豆91天堂| 久久99久国产麻精品66| 久久乐国产精品亚洲综合| 91精品国产色综合久久| 国内精品久久久久久久久电影网| 99久久免费国产精品| 久久精品国产亚洲av高清漫画| 色婷婷久久久SWAG精品| 亚洲狠狠综合久久| 久久久国产精品福利免费| 久久青青草原精品国产| 综合久久一区二区三区 | 中文精品久久久久国产网址| 伊人久久久AV老熟妇色| 人人狠狠综合88综合久久| 国产午夜精品理论片久久| 97热久久免费频精品99| 久久久精品人妻一区二区三区蜜桃 | 久久99国产精品尤物| 亚洲综合熟女久久久30p| 热综合一本伊人久久精品| 久久夜色撩人精品国产小说| 久久www免费人成精品香蕉| 久久久久一级精品亚洲国产成人综合AV区 | 亚洲国产综合久久天堂| 亚洲精品国产自在久久| 久久只有这精品99|