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


            May the force be with you!
            posts - 52,  comments - 33,  trackbacks - 0

            問題來源:
            HUST07校賽

            原題見:http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1338

            提交方式:WOJ1338

            問題描述:
                對于N(1<=N<=80)個數A[1...N](1<=A[i]<=500),他們的和為sum,求sum!/(A[1]!*A[2]!*...*A[N]!)%40009。

            解題過程:
                對于這個題目,我當時就推出了上面的公式,然后就卡了,不知道后面怎么辦——這些數可是非常大。

                其實這個問題的重點就在于運用擴展歐幾里德(感謝Felicia的指導):

            對于 a/b%m = ans, 求 ans。

            a = a%m, b = b%m
            ans = (a % m)*(x % m) % m  (x為b的逆元)

            求逆元則利用擴展歐幾里德:
            對于 b*x = 1(mod m)
            可以求b*x + m*y = 1的解( 用extennd_Euclid(b, m, x, y) )!
            然后把 x 映射到 [0,m)區間,帶入上式, 即得解。


            附代碼:

             1 
             2 int extend_Euclid(int a, int b, int &x, int &y)
             3 {
             4     if (b == 0)
             5     {
             6         x = 1;
             7         y = 0;
             8          return a;
             9     }
            10     else
            11     {
            12         int ans = extend_Euclid(b, a % b, x, y); /////
            13         int t = x;
            14         x = y;
            15         y = t - (a / b) * y;
            16         return ans;
            17     }
            18 }
            19 
            20 





            posted on 2008-03-14 16:46 R2 閱讀(2552) 評論(5)  編輯 收藏 引用 所屬分類: Problem Solving 、Pure Theory 、Memo

            FeedBack:
            # re: 【數論】擴展歐幾里德的一個妙用
            2008-03-17 21:23 | 長江三峽
            學習  回復  更多評論
              
            # re: 【數論】擴展歐幾里德的一個妙用
            2008-03-17 21:42 | sdf
            感覺ACM玩的東西都好復雜?。?!  回復  更多評論
              
            # re: 【數論】擴展歐幾里德的一個妙用
            2008-04-07 21:48 | IceDragon
            樓主你好,我也是用擴展歐幾里得做的,但是我一直WA
            可否借你的代碼看下--不勝感激
            這題目還有什么陷阱么??????
            我郵箱--wangzhaoren@gmail.com
              回復  更多評論
              
            # re: 【數論】擴展歐幾里德的一個妙用
            2008-04-09 12:53 | littlekid
            @IceDragon
            估計OJ出現不明錯誤,或者后來加強數據了(最近交的都沒過,我貼了別人AC的代碼都沒過=,=?。?br>
            不過你可以考慮一下越界問題——用long long試試  回復  更多評論
              
            # re: 【數論】擴展歐幾里德的一個妙用
            2009-10-29 17:59 | 5
            還是不懂啊  回復  更多評論
              
            你是第 free hit counter 位訪客




            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 63689
            • 排名 - 358

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲欧美成人久久综合中文网| 色偷偷久久一区二区三区| 91秦先生久久久久久久| 久久高潮一级毛片免费| 久久福利资源国产精品999| 九九精品99久久久香蕉| 国产成人久久久精品二区三区| 伊人久久无码精品中文字幕| 久久人人爽人人爽人人AV| 88久久精品无码一区二区毛片 | 亚洲中文字幕无码一久久区| 91久久婷婷国产综合精品青草| 久久精品成人免费国产片小草| 天堂久久天堂AV色综合| 久久综合九色综合久99| 久久精品国产福利国产秒| 久久久久久国产精品美女| 激情五月综合综合久久69| 99999久久久久久亚洲| 亚洲精品乱码久久久久久自慰| 久久久久久av无码免费看大片| 久久精品国产亚洲AV高清热| 久久亚洲sm情趣捆绑调教| 久久99精品国产麻豆不卡| 久久久精品午夜免费不卡| 久久亚洲精品人成综合网| 伊人久久精品无码av一区| 一级女性全黄久久生活片免费 | 香蕉久久夜色精品国产小说| 色婷婷久久综合中文久久蜜桃av | 热re99久久精品国99热| 久久99精品久久久大学生| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 一本色道久久99一综合| 99久久国产综合精品女同图片| 99久久免费国产精品特黄| 欧美亚洲国产精品久久高清| 思思久久精品在热线热| 久久亚洲日韩看片无码| 奇米综合四色77777久久| 国内精品久久久久久99|