/********************************************************************
    
    purpose:    

    在從1到n的正數(shù)中1出現(xiàn)的次數(shù)
    題目：輸入一個(gè)整數(shù)n，求從1到n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。

    例如輸入12，從1到12這些整數(shù)中包含1 的數(shù)字有1，10，11和12，1一共出現(xiàn)了5次。

    求滿足f(i)=i(i<=911111111099999009)這樣的數(shù)總計(jì)有多少個(gè)
*********************************************************************/
#include <iostream>
#include <string>
#include <time.h>

using namespace std;


int len;
int *perDigit; // 每位上的數(shù)字 
long long* fullOne; // 位數(shù)是n位的數(shù)，含1的總個(gè)數(shù)為fullOne[n]
long long* addTopOne; // 位數(shù)為n的數(shù)，首位為1時(shí)有多少個(gè)這樣的數(shù)addTopOne[n] 即10^(n-1) 


int curDigit;
long long cnt = 0;
long long fixBit1 = 0;
int ocuur1Cnt = 0;
long long getOneCnt(long long n)
{
    len = 0;
    while (n > 0) {  // 把數(shù)字n分成十進(jìn)制串對應(yīng)的數(shù)字?jǐn)?shù)組
        perDigit[len] = n % 10;
        n = n / 10;
        len++;
    }
    cnt = 0;
    fixBit1 = 0; // 數(shù)字n中1所在的位被小于此位的數(shù)字重復(fù)的次數(shù)
    ocuur1Cnt = 0; // 數(shù)字n有幾位是1
    for (int i = len - 1; i >= 0; i--) { // 從十進(jìn)制數(shù)高位到低位
        curDigit = perDigit[i];
        if (ocuur1Cnt > 0) {
            fixBit1 = fixBit1 * 10 + ocuur1Cnt * curDigit;
        }
        if (curDigit > 0) {
            if (curDigit == 1) {
                cnt += curDigit * fullOne[i];
                ocuur1Cnt++;
            } else {
                cnt += curDigit * fullOne[i] + addTopOne[i];
            }
        }
    }
    return cnt + fixBit1 + ocuur1Cnt;
}

void HowManyOne(long long topNum)
{
    clock_t start, finish; // 記錄計(jì)算開始結(jié)束時(shí)間
    start = clock();

    len = 20; // 最長20位十進(jìn)制數(shù)
    perDigit = new int[len];
    fullOne = new long long[len];
    addTopOne = new long long[len];
    fullOne[0] = 0;
    addTopOne[0] = 1;
    cnt = 1;
    for (int i = 1; i < len; i++) { // 初始化信息
        fullOne[i] = fullOne[i-1]*10 + cnt;
        cnt *= 10;
        addTopOne[i] = cnt;
    }


    long long stack[1000]; // 存儲數(shù)據(jù)段, [from, to]及計(jì)算方向，每次分別存入from,to,dir
    long long lRel[1000]; // 符合f(i)==i表達(dá)式的i的數(shù)組
    int pStack = 0, pRel = 0; // stack與lRel當(dāng)前長度或下一次存儲位置或棧頂
    long long from, to, dir; // 當(dāng)前要驗(yàn)證的一段數(shù)據(jù)的始終與驗(yàn)證方向，驗(yàn)證方向?yàn)?x01(向上) 0x10(向下) 0x11(向上向下均可以)
    long long fn, dist; // fn當(dāng)前一個(gè)數(shù)字n對應(yīng)的1到n所有數(shù)字的十進(jìn)制中的1的總個(gè)數(shù)；dist臨時(shí)變量（from與to的差）


    stack[0] = 1;
    stack[1] = topNum;
    stack[2] = 3; // 0x11
    pStack = 3;
    int maxP = 0;
    while (pStack > 0) { // 從stack中取出一段數(shù)據(jù)，驗(yàn)證其中的i是否滿足f(i)==i
        dir = stack[--pStack];
        to = stack[--pStack];
        from = stack[--pStack];

        if ((dir & 0x01) != 0) { // UP 從from開始向to的方向計(jì)算 f(i)==i
            while (from <= to) {
                fn = getOneCnt(from);
                if (fn > from) {
                    from = fn;
                } else if (fn < from) {
                    from++;
                    break;
                } else {
                    lRel[pRel++] = fn;
                    from++;
                }
            }
        }
        if ((dir & 0x10) != 0) { // down 從to開始向from的方向計(jì)算 f(i)==i
            while(from <= to) {
                fn = getOneCnt(to);
                if (fn < to) {
                    to = fn;
                } else if (fn > to) {
                    to--;
                    break;
                } else {
                    lRel[pRel++] = fn;
                    to--;
                }
            }
        }
        if (to-from<2) { // 這一段己經(jīng)很小，直接計(jì)算完
            for (;from<=to;from++) {
                if (from == getOneCnt(from)) {
                    lRel[pRel++] = fn;
                }
            }
        } else { // 當(dāng)前段向上向下己計(jì)算完，二分后入棧，再計(jì)算
            dist = (to - from) >> 1;
            dist = from + dist;
            stack[pStack++] = from;
            stack[pStack++] = dist;
            stack[pStack++] = 0x10;
            stack[pStack++] = dist+1;
            stack[pStack++] = to;
            stack[pStack++] = 0x01;
        }

    }

    finish = clock();
    int i = pRel;
    while(i > 0) // 輸出符合f(i)==i的所有i
        cout<<lRel[--i] <<endl;
    cout<<"time: " << ((double)(finish-start))<<"ms" << endl;
    cout<<"total: " <<pRel<<endl;
}

void Test_HowManyOne()
{
    HowManyOne(911111111099999009LL);
}


輸出為：
199981
199982
199983
199984
199985
199986
199987
199990
199989
199988
200000
200001
1599981
1599982
1599983
1599984
1599985
1599986
1599987
1599988
1599990
1599989
2600000
2600001
13199998
35199981
35199982
35199983
35199984
35199985
35199986
35199987
35199990
35199989
35199988
35000001
35000000
35200000
35200001
117463825
500199981
500199982
500199983
500199984
500199985
500199986
500199987
500199990
500199989
500199988
500200000
500200001
501599981
501599982
501599983
501599984
501599985
501599986
501599987
501599988
501599990
501599989
502600000
502600001
513199998
535199981
535199982
535199983
535199984
535199985
535199986
535199987
535199990
535199989
535199988
535000001
535000000
500000001
500000000
535200000
535200001
1111111110
1
time: 0ms
total: 83