• <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 SolvingPure Theory 、Memo

            FeedBack:
            # re: 【數論】擴展歐幾里德的一個妙用
            2008-03-17 21:23 | 長江三峽
            學習  回復  更多評論
              
            # re: 【數論】擴展歐幾里德的一個妙用
            2008-03-17 21:42 | sdf
            感覺ACM玩的東西都好復雜?。。?nbsp; 回復  更多評論
              
            # 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 位訪客




            <2007年10月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            常用鏈接

            留言簿(4)

            隨筆分類(54)

            隨筆檔案(52)

            文章檔案(1)

            ACM/ICPC

            技術綜合

            最新隨筆

            搜索

            •  

            積分與排名

            • 積分 - 63675
            • 排名 - 358

            最新評論

            閱讀排行榜

            評論排行榜

            久久男人Av资源网站无码软件 | 77777亚洲午夜久久多喷| 久久天天躁狠狠躁夜夜网站| AV色综合久久天堂AV色综合在| 777米奇久久最新地址| 久久无码AV中文出轨人妻| 久久精品极品盛宴观看| 久久丫精品国产亚洲av| 久久精品成人欧美大片| 少妇久久久久久被弄高潮| 精品99久久aaa一级毛片| 国产激情久久久久久熟女老人| 国产精品岛国久久久久| 久久精品国产2020| 久久国产影院| 天天综合久久久网| 久久天堂AV综合合色蜜桃网| 免费一级欧美大片久久网| 狠狠狠色丁香婷婷综合久久五月| 久久婷婷五月综合97色直播| 天天久久狠狠色综合| 久久精品国产亚洲精品2020| 久久久久久伊人高潮影院| 国内精品久久久久国产盗摄| 99久久国产综合精品麻豆| 亚洲国产另类久久久精品 | 亚洲午夜精品久久久久久app| 久久中文娱乐网| 国产精品久久久久9999| 精品国产一区二区三区久久久狼| 亚洲Av无码国产情品久久| 欧美大战日韩91综合一区婷婷久久青草| 久久精品国产精品国产精品污 | 狠狠久久综合伊人不卡| 久久久久久免费一区二区三区| 精品永久久福利一区二区| 亚洲精品美女久久久久99| 精品久久久久久国产| 亚洲AV无码久久精品成人| 囯产精品久久久久久久久蜜桃| 久久久久av无码免费网|