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

    在從1到n的正數中1出現的次數
    題目：輸入一個整數n，求從1到n這n個整數的十進制表示中1出現的次數。

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

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

using namespace std;


int len;
int *perDigit; // 每位上的數字 
long long* fullOne; // 位數是n位的數，含1的總個數為fullOne[n]
long long* addTopOne; // 位數為n的數，首位為1時有多少個這樣的數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) {  // 把數字n分成十進制串對應的數字數組
        perDigit[len] = n % 10;
        n = n / 10;
        len++;
    }
    cnt = 0;
    fixBit1 = 0; // 數字n中1所在的位被小于此位的數字重復的次數
    ocuur1Cnt = 0; // 數字n有幾位是1
    for (int i = len - 1; i >= 0; i--) { // 從十進制數高位到低位
        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; // 記錄計算開始結束時間
    start = clock();

    len = 20; // 最長20位十進制數
    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]; // 存儲數據段, [from, to]及計算方向，每次分別存入from,to,dir
    long long lRel[1000]; // 符合f(i)==i表達式的i的數組
    int pStack = 0, pRel = 0; // stack與lRel當前長度或下一次存儲位置或棧頂
    long long from, to, dir; // 當前要驗證的一段數據的始終與驗證方向，驗證方向為0x01(向上) 0x10(向下) 0x11(向上向下均可以)
    long long fn, dist; // fn當前一個數字n對應的1到n所有數字的十進制中的1的總個數；dist臨時變量（from與to的差）


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

        if ((dir & 0x01) != 0) { // UP 從from開始向to的方向計算 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的方向計算 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) { // 這一段己經很小，直接計算完
            for (;from<=to;from++) {
                if (from == getOneCnt(from)) {
                    lRel[pRel++] = fn;
                }
            }
        } else { // 當前段向上向下己計算完，二分后入棧，再計算
            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