• <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: 博客園 模板提供:滬江博客
            亚洲国产精品久久久久久| 色综合久久88色综合天天| 香蕉久久影院| 97精品依人久久久大香线蕉97| 久久亚洲中文字幕精品有坂深雪| 久久久久久亚洲精品成人| 久久亚洲国产欧洲精品一| 亚洲精品tv久久久久久久久久| 久久无码人妻一区二区三区| 亚洲狠狠综合久久| 国产激情久久久久久熟女老人| 91久久精品视频| 伊人久久精品无码二区麻豆| 久久成人影院精品777| 亚洲人成无码久久电影网站| 人妻精品久久无码区| 久久国产香蕉视频| 狠狠色噜噜狠狠狠狠狠色综合久久| 亚洲精品无码久久不卡| 777久久精品一区二区三区无码| 久久久久久综合网天天| 精品国产91久久久久久久a| 无遮挡粉嫩小泬久久久久久久| 狠狠色丁香婷婷综合久久来来去| 久久精品中文无码资源站| 久久婷婷午色综合夜啪| 国产精品久久久久久久午夜片| 久久精品黄AA片一区二区三区| 久久久亚洲裙底偷窥综合| 久久久久国产| 久久五月精品中文字幕| 久久久久久噜噜精品免费直播 | 久久精品国产99久久久| 亚洲国产小视频精品久久久三级| 欧美伊香蕉久久综合类网站| 97精品国产91久久久久久| 国内精品久久久久影院日本| 久久精品国产亚洲av麻豆图片| 久久亚洲熟女cc98cm| 色88久久久久高潮综合影院| 久久综合给久久狠狠97色|