• <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
            這道題是杭州賽區(qū)的網(wǎng)絡預選賽的賽題,當時打死也沒過,現(xiàn)在也沒有當時的代碼了,不知道哪里錯了,今天一看想起了一個公式就是
            1^3+2^3+……n^3=(n)^2*(n+1)*^2/4;記得這個公式還是高二老師教會的著,具體證明我們可以數(shù)學歸納法證明一下,簡單的很自己證明吧!
            而那時自己網(wǎng)絡賽的時候不知道怎么推導出過10007是個循環(huán),可以把b的取模,而現(xiàn)在有了這個公式就可以一步搞定為什么對b取模!
            要解題就必須求出a ^b的因子數(shù),這不是難點
            證明如下:
            N=a1^b1*a2^b2*……*aN^bN;根據(jù)排列組合原理我們知道N的因子數(shù)可以如下解出:
            即(b1+1)*(b2+1)*.......*(bN+1);而現(xiàn)在是a^b只需要把(b1*b+1)*(b2*b+1)*.......*(bN*b+1);極為因子數(shù):
            而這個時候我們知道1<=a,b<=1000000超出整形范圍:我們進一步優(yōu)化得到
            因為有:m*n%x=(m%x*n%x);(m+n)%x=(m%x+n%x);
            所以我們必須在過程中優(yōu)化算法!
            這樣這道題目就出來了!當然求因子時必不可少素數(shù)打表!可以優(yōu)化打表1000,減少時間!當然還可以把1-10007的密碼表打出,更優(yōu)時間啊
            素數(shù)打表代碼如下:
            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)  編輯 收藏 引用
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            国产情侣久久久久aⅴ免费| 久久久久久久综合日本亚洲| 久久久无码精品午夜| 久久精品一区二区三区中文字幕| 人人狠狠综合88综合久久| 久久性精品| 精品国产乱码久久久久久人妻| 久久国产精品77777| 久久精品国产第一区二区| 日韩欧美亚洲综合久久| 久久精品九九亚洲精品天堂| 欧美成a人片免费看久久| 欧美噜噜久久久XXX| 国产精品gz久久久| 久久婷婷激情综合色综合俺也去| 久久se这里只有精品| 久久精品无码一区二区无码| 久久男人AV资源网站| 精品无码久久久久久尤物| 伊人久久成人成综合网222| 99久久精品无码一区二区毛片| 无码任你躁久久久久久老妇App| 国产精品美女久久久| 亚洲伊人久久精品影院| 欧美亚洲另类久久综合婷婷| 久久综合久久久| 99久久99久久久精品齐齐| 欧美亚洲国产精品久久高清| 国产精品日韩欧美久久综合| 久久久久人妻一区精品性色av| 久久久久无码中| 久久精品国产亚洲精品| 亚洲一区中文字幕久久| 久久国产精品-国产精品| 日日躁夜夜躁狠狠久久AV| 久久无码AV中文出轨人妻| 欧美性猛交xxxx免费看久久久| 人人狠狠综合久久亚洲| 久久一区二区三区99| 久久青青草原精品国产软件| 久久精品成人免费观看97|