• <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>
            Tim's Programming Space  
            Tim's Programming Space
            日歷
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789
            統(tǒng)計(jì)
            • 隨筆 - 20
            • 文章 - 1
            • 評(píng)論 - 40
            • 引用 - 0

            導(dǎo)航

            常用鏈接

            留言簿(3)

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

             

            幸運(yùn)數(shù)字

             

            【題目描述】

            在中國(guó),很多人都把68視為是幸運(yùn)數(shù)字!lxhgww也這樣認(rèn)為,于是他定義自己的“幸運(yùn)號(hào)碼”是十進(jìn)制表示中只包含數(shù)字68的那些號(hào)碼,比如68666888都是“幸運(yùn)號(hào)碼”!但是這種“幸運(yùn)號(hào)碼”總是太少了,比如在[1,100]的區(qū)間內(nèi)就只有6個(gè)(6866688688),于是他又定義了一種“近似幸運(yùn)號(hào)碼”。lxhgww規(guī)定,凡是“幸運(yùn)號(hào)碼”的倍數(shù)都是“近似幸運(yùn)號(hào)碼”,當(dāng)然,任何的“幸運(yùn)號(hào)碼”也都是“近似幸運(yùn)號(hào)碼”,比如1216666都是“近似幸運(yùn)號(hào)碼”。

            現(xiàn)在lxhgww想知道在一段閉區(qū)間[a, b]內(nèi),“近似幸運(yùn)號(hào)碼”的個(gè)數(shù)。

            【輸入】

            輸入數(shù)據(jù)是一行,包括2個(gè)數(shù)字ab

            【輸出】

            輸出數(shù)據(jù)是一行,包括1個(gè)數(shù)字,表示在閉區(qū)間[a, b]內(nèi)“近似幸運(yùn)號(hào)碼”的個(gè)數(shù)

            【樣例輸入1

            1 10

            【樣例輸出1

            2

            【樣例輸入2

            1234 4321

            【樣例輸出2

            809

            【數(shù)據(jù)范圍】

               對(duì)于30%的數(shù)據(jù),保證1<=a<=b<=1000000

               對(duì)于100%的數(shù)據(jù),保證1<=a<=b<=10000000000


            //================================================================
            用容斥原理做。
            先造出所有的幸運(yùn)號(hào)碼,然后對(duì)幸運(yùn)號(hào)碼的倍數(shù)容斥。
            幸運(yùn)號(hào)碼有2000+個(gè),為了盡快出解,要加幾個(gè)剪枝:
            1. 如果A是B的倍數(shù),直接去掉。剪掉了一大半。。。

            2.從大到小排序,盡快容斥掉一些數(shù)。

            寫的常數(shù)稍微少點(diǎn)能進(jìn)2s了。。

            PS :關(guān)于中間結(jié)果會(huì)爆long long的問題。。。從正的爆成負(fù)的容易,從正的爆成負(fù)的再爆成正的不容易。。。所以猥瑣的判大于0。。。

             1#include <iostream>
             2#include <algorithm>
             3#define NNUM 3000
             4#define ll long long
             5
             6using namespace std;
             7
             8ll A,B;
             9void Init(){
            10     scanf("%I64d%I64d",&A,&B);
            11}

            12
            13int n = 0;
            14ll a[NNUM+1];
            15void dfsNum(ll num){
            16     if (num > B) return;
            17     if (num <= B)
            18        a[++n] = num;
            19     dfsNum(num * (ll)10 + (ll)6);
            20     dfsNum(num * (ll)10 + (ll)8);
            21}

            22int cnt = 0;
            23ll b[NNUM+1];
            24
            25ll Ans = 0, tmp;
            26inline ll gcd(ll a, ll b){
            27   while (b)
            28         tmp = a, a = b, b = tmp % b;
            29   return a;
            30}

            31
            32
            33int cmp(const void *a, const void *b){
            34    return (*(ll *)b) >  (*(ll *)a) ? 1 : -1;
            35}

            36
            37ll dfs(int pos, ll num){
            38   if (pos == n+1return B/num - A/num;
            39   ll ret = dfs(pos+1, num);
            40   ll newnum = num / gcd(num, a[pos]) * a[pos];
            41   if (newnum <= B && newnum >= 1)
            42      ret -= dfs(pos+1, newnum);
            43   return ret;
            44}

            45
            46void Solve(){
            47     dfsNum(6); dfsNum(8);
            48     qsort(a+1, n, sizeof(a[0]), cmp);
            49     //printf("%d\n",n);
            50     for (int i = 1; i<=n; i++){
            51         bool boo = true;
            52         for (int j = 1; j<=n; j++)
            53             if (i!=&& a[i] % a[j] == 0){
            54                boo = false;
            55                break;
            56             }

            57         if (boo){
            58            a[++cnt] = a[i];
            59            //printf("%d %I64d\n", cnt, a[cnt]);
            60         }

            61     }

            62     n = cnt;
            63     //printf("%d\n",n);
            64     A--;
            65     printf("%I64d\n", B - A - dfs(1,1));
            66}

            67
            68int main(){
            69    freopen("luckynumber.in","r",stdin);
            70    freopen("luckynumber.out","w",stdout);
            71    Init();
            72    Solve();
            73    return 0;
            74}

            75

            posted on 2010-04-06 20:00 TimTopCoder 閱讀(583) 評(píng)論(2)  編輯 收藏 引用
            評(píng)論:

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


             
            Copyright © TimTopCoder Powered by: 博客園 模板提供:滬江博客
            国产福利电影一区二区三区久久久久成人精品综合 | 欧美激情一区二区久久久| 久久久WWW成人免费精品| 国内精品人妻无码久久久影院| 亚洲香蕉网久久综合影视 | 亚洲伊人久久成综合人影院| 国产午夜精品久久久久九九电影| 亚洲精品美女久久久久99| 97精品伊人久久大香线蕉| 99国产欧美久久久精品蜜芽| 成人国内精品久久久久影院| 亚洲精品成人网久久久久久| 国产欧美久久一区二区| 青青草国产精品久久| 久久99精品综合国产首页| 一本一本久久aa综合精品| 久久久久国产日韩精品网站| 91久久精品国产91性色也| 国内精品伊人久久久久网站| 久久亚洲精品成人AV| 色综合久久综精品| 99久久国语露脸精品国产| 午夜精品久久久久久99热| 精品多毛少妇人妻AV免费久久| 99久久精品免费| 国产精品毛片久久久久久久 | 久久国产精品99精品国产| 久久久免费精品re6| 精品国产日韩久久亚洲| 色欲综合久久躁天天躁| 久久精品卫校国产小美女| 午夜精品久久久久久影视riav| 久久香蕉国产线看观看99| 国产三级久久久精品麻豆三级 | 伊人久久综合热线大杳蕉下载| 热99re久久国超精品首页| 精品无码久久久久久尤物| 狠狠久久亚洲欧美专区| 国内精品久久久久久中文字幕| 午夜精品久久久久久中宇| 久久人人爽人人人人爽AV|