• <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
            日歷
            <2010年4月>
            28293031123
            45678910
            11121314151617
            18192021222324
            2526272829301
            2345678
            統計
            • 隨筆 - 20
            • 文章 - 1
            • 評論 - 40
            • 引用 - 0

            導航

            常用鏈接

            留言簿(3)

            隨筆檔案

            文章檔案

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

             

            幸運數字

             

            【題目描述】

            在中國,很多人都把68視為是幸運數字!lxhgww也這樣認為,于是他定義自己的“幸運號碼”是十進制表示中只包含數字68的那些號碼,比如68,666,888都是“幸運號碼”!但是這種“幸運號碼”總是太少了,比如在[1,100]的區間內就只有6個(6,8,66,68,86,88),于是他又定義了一種“近似幸運號碼”。lxhgww規定,凡是“幸運號碼”的倍數都是“近似幸運號碼”,當然,任何的“幸運號碼”也都是“近似幸運號碼”,比如12,16,666都是“近似幸運號碼”。

            現在lxhgww想知道在一段閉區間[a, b]內,“近似幸運號碼”的個數。

            【輸入】

            輸入數據是一行,包括2個數字ab

            【輸出】

            輸出數據是一行,包括1個數字,表示在閉區間[a, b]“近似幸運號碼”的個數

            【樣例輸入1

            1 10

            【樣例輸出1

            2

            【樣例輸入2

            1234 4321

            【樣例輸出2

            809

            【數據范圍】

               對于30%的數據,保證1<=a<=b<=1000000

               對于100%的數據,保證1<=a<=b<=10000000000


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

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

            寫的常數稍微少點能進2s了。。

            PS :關于中間結果會爆long long的問題。。。從正的爆成負的容易,從正的爆成負的再爆成正的不容易。。。所以猥瑣的判大于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) 評論(2)  編輯 收藏 引用
            評論:
            • # re: SCTSC2010-幸運數字  rgt Posted @ 2010-04-12 20:50
              話說這道題可以分段打表。  回復  更多評論   

            • # re: SCTSC2010-幸運數字[未登錄]  TimTopCoder Posted @ 2010-04-13 10:08
              @rgt
              orz。。。莫非sqrt一下?。。。  回復  更多評論   

             
            Copyright © TimTopCoder Powered by: 博客園 模板提供:滬江博客
            国产激情久久久久影院| 亚洲精品WWW久久久久久| 久久婷婷五月综合色奶水99啪| 热99RE久久精品这里都是精品免费 | 日韩久久无码免费毛片软件 | 久久久久亚洲AV无码专区首JN| 7777久久久国产精品消防器材| 国产精品久久久久久久久| 久久伊人中文无码| 精品无码久久久久久尤物| 久久久久亚洲AV成人网| 亚洲香蕉网久久综合影视| 国产精品成人精品久久久| 久久精品国产亚洲AV影院| 久久久青草久久久青草| 国产美女亚洲精品久久久综合| 久久91亚洲人成电影网站| 久久久久精品国产亚洲AV无码| 久久精品免费观看| 亚洲国产精品无码久久| 久久强奷乱码老熟女| 久久久久久久综合日本亚洲| 伊人久久大香线蕉亚洲| 看全色黄大色大片免费久久久| 久久99精品国产| 久久久久亚洲精品无码蜜桃| 99久久香蕉国产线看观香| 久久99精品久久久久久9蜜桃| 久久久久久夜精品精品免费啦| 99精品国产免费久久久久久下载| 久久黄视频| 精品久久人人做人人爽综合| av无码久久久久久不卡网站| 亚洲精品乱码久久久久66| 蜜桃麻豆WWW久久囤产精品| 手机看片久久高清国产日韩| 久久久久国产| 久久亚洲精品国产亚洲老地址| 久久久久亚洲av毛片大| 麻豆国内精品久久久久久| 欧洲国产伦久久久久久久|