• <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 - 74,  comments - 33,  trackbacks - 0

            Xiaoming has just come up with a new way for encryption, by calculating the key from a publicly viewable number in the following way:
            Let the public key N = AB, where 1 <= A, B <= 1000000, and a0, a1, a2, …, ak-1 be the factors of N, then the private key M is calculated by summing the cube of number of factors of all ais. For example, if A is 2 and B is 3, then N = AB = 8, a0 = 1, a1 = 2, a2 = 4, a3 = 8, so the value of M is 1 + 8 + 27 + 64 = 100.
            However, contrary to what Xiaoming believes, this encryption scheme is extremely vulnerable. Can you write a program to prove it?

            Input

            There are multiple test cases in the input file. Each test case starts with two integers A, and B. (1 <= A, B <= 1000000). Input ends with End-of-File.
            Note: There are about 50000 test cases in the input file. Please optimize your algorithm to ensure that it can finish within the given time limit.

            Output

            For each test case, output the value of M (mod 10007) in the format as indicated in the sample output.

            Sample Input

            2 2
            1 1
            4 7

            Sample Output

            Case 1: 36
            Case 2: 1
            Case 3: 4393


            Author: 2008 Asia Hangzhou Regional Contest Online
            這道題是杭州賽區的網絡預選賽的賽題,當時打死也沒過,現在也沒有當時的代碼了,不知道哪里錯了,今天一看想起了一個公式就是
            1^3+2^3+……n^3=(n)^2*(n+1)*^2/4;記得這個公式還是高二老師教會的著,具體證明我們可以數學歸納法證明一下,簡單的很自己證明吧!
            而那時自己網絡賽的時候不知道怎么推導出過10007是個循環,可以把b的取模,而現在有了這個公式就可以一步搞定為什么對b取模!
            要解題就必須求出a ^b的因子數,這不是難點
            證明如下:
            N=a1^b1*a2^b2*……*aN^bN;根據排列組合原理我們知道N的因子數可以如下解出:
            即(b1+1)*(b2+1)*.......*(bN+1);而現在是a^b只需要把(b1*b+1)*(b2*b+1)*.......*(bN*b+1);極為因子數:
            而這個時候我們知道1<=a,b<=1000000超出整形范圍:我們進一步優化得到
            因為有:m*n%x=(m%x*n%x);(m+n)%x=(m%x+n%x);
            所以我們必須在過程中優化算法!
            這樣這道題目就出來了!當然求因子時必不可少素數打表!可以優化打表1000,減少時間!當然還可以把1-10007的密碼表打出,更優時間啊
            素數打表代碼如下:
            memset(prim,0,sizeof(prim));
            ????
            for(sign=0,i=2;i<MAXN;i++)
            ????????
            if(!prim[i]){
            ????????????num[sign
            ++]=i;
            ????????????
            for(j=0;i*j<MAXN;j++)
            ????????????????prim[i
            *j]=true;????
            ????????}



            posted on 2009-03-23 19:20 KNIGHT 閱讀(524) 評論(0)  編輯 收藏 引用
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            99久久99久久精品国产片| 亚洲狠狠婷婷综合久久久久| 91视频国产91久久久| 久久99精品久久久久久齐齐 | 欧美一区二区三区久久综| 久久九九精品99国产精品| 国产精品成人精品久久久| 香蕉久久永久视频| 久久国产免费观看精品3| 久久久久国产精品嫩草影院| 久久久久亚洲AV无码专区首JN| 国产精品99久久久久久人| 久久99精品国产麻豆蜜芽| 久久精品亚洲日本波多野结衣| 久久久久无码精品| 久久精品aⅴ无码中文字字幕不卡| 国内精品久久久久久久亚洲| 精品无码久久久久久午夜| 无码任你躁久久久久久老妇 | 国产成人久久久精品二区三区| 99久久这里只精品国产免费| 精品久久久久久无码人妻蜜桃| 久久综合给久久狠狠97色| 久久这里有精品| 久久久99精品成人片中文字幕| 91精品国产高清久久久久久io| 久久婷婷午色综合夜啪| 精品久久人人做人人爽综合| 好属妞这里只有精品久久| 久久综合精品国产二区无码| 久久久久亚洲av综合波多野结衣| 久久精品女人天堂AV麻| 91久久香蕉国产熟女线看| 99久久精品日本一区二区免费 | 欧美日韩中文字幕久久久不卡| 好属妞这里只有精品久久| 中文字幕日本人妻久久久免费 | 久久青青草原综合伊人| 99国产精品久久| 国产精品综合久久第一页| 久久精品国产亚洲av瑜伽|