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

            求連續(xù)n個(gè)數(shù)每個(gè)數(shù)的因數(shù)個(gè)數(shù)之和

            今天個(gè)人賽的一個(gè)題
            We define the function f(x) = the number of divisors of x. Given two integers a and b (a ≤ b), please
            calculate f(a) + f(a+1) + ... + f(b).
            Input
            Two integers a and b for each test case, 1 ≤ a ≤ b ≤ 231 1.
            The input is terminated by a line with a = b
            = 0.
            Output
            The value of f(a) + f(a+1) + ... + f(b).
            Sample Input
            9 12
            1 2147483647
            0 0
            Sample Output
            15
            46475828386
            Hint
            For the first test case:
            9 has 3 divisors: 1, 3, 9.
            10 has 4 divisors: 1, 2, 5, 10.
            11 has 2 divisors: 1, 11.
            12 has 6 divisors: 1, 2, 3, 4, 6, 12.
            So the answer is 3 + 4 + 2 + 6 = 15.

            O(n)的算法很好想

            1到m中可以被i整除的數(shù)的個(gè)數(shù)為 m/i

            ?所以用for(sum =0,i=0;i<=m;i++)

            sum += m/i;

            ?sum即是f(1)+f(2)+f(m)的值.

            這樣的算法復(fù)雜度是O(N);

            但諸位大哥也看到了 數(shù)據(jù)范圍很大 所以我們按照慣例---要優(yōu)化···

            其實(shí)我們可以只算從1到sqrt(m)? 具體說來每次不但要加m/i 還要加(m/i-m/(i+1))*i;

            后面加的那個(gè)對應(yīng)的是跟i對應(yīng)的另一半···

            形象一點(diǎn)吧

            拿12來說

            就是 12 6 4 3 2 2 1 1 1 1 1 1

            我們算的從1到3 后面對應(yīng)的就是
            (12/1-12/2)*1
            (12/2-12/3)*2
            (12/3-12/4)*3

            這個(gè)也算規(guī)律吧

            這樣一來規(guī)模就是O(sqrt(N))

            還是貼CODE:
            #include<iostream>
            #include <cmath>

            using namespace std;
            int a[10]={0,1,3,5,8,10};
            long long int f(long long int m)
            {
            ??????? if(m<=5) return a[m];
            ??????? long long int sum=0;
            ??????? long long int t=sqrt(m*1.0);
            ??????? for(long long int i=1;i<=t;i++)
            ??????? {
            ??????????????? sum+=m/i;
            ??????????????? sum+=(m/i-m/(i+1))*i;
            ??????? }
            ??????? return sum;
            }
            int main()
            {
            ??????? long long int m,n;
            ??????? while(cin>>m>>n&&(m||n))
            ??????????????? cout<<f(n)-f(m-1)<<endl;

            }



            posted on 2008-05-24 23:59 Victordu 閱讀(554) 評(píng)論(0)  編輯 收藏 引用


            只有注冊用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            導(dǎo)航

            <2008年5月>
            27282930123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            統(tǒng)計(jì)

            常用鏈接

            留言簿(5)

            隨筆檔案(46)

            搜索

            積分與排名

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久久久久波多野结衣高潮 | 久久国产精品无码HDAV| 久久亚洲国产精品成人AV秋霞| 亚洲精品高清一二区久久| 久久亚洲国产成人影院| 7777久久亚洲中文字幕| 青青草原综合久久| 久久久久久综合网天天| 热久久国产精品| 久久国产劲爆AV内射—百度| 狠狠色丁香久久婷婷综| 久久久久久国产a免费观看黄色大片 | 久久人人爽人人精品视频| 色8久久人人97超碰香蕉987| 91久久福利国产成人精品| 色8久久人人97超碰香蕉987| 亚洲伊人久久成综合人影院 | 久久精品国产亚洲AV久| 久久99精品国产99久久6| 97精品国产91久久久久久| 99久久综合国产精品免费 | 国产69精品久久久久9999APGF| 99蜜桃臀久久久欧美精品网站| 国产精品99久久久久久董美香| 伊人久久综合精品无码AV专区| 青青草国产97免久久费观看| 久久久久综合网久久| 国产∨亚洲V天堂无码久久久| 亚洲午夜久久久久妓女影院| 思思久久99热只有频精品66| 色偷偷91久久综合噜噜噜噜| 久久国产免费| 久久国产三级无码一区二区| 久久久久久毛片免费播放| 亚洲中文字幕无码久久综合网 | 亚洲欧洲精品成人久久奇米网| 国产精品成人久久久久久久| 日本久久久久久中文字幕| 国内精品久久久久影院日本| 精品久久久久久无码专区不卡| 国产成人久久AV免费|