/********************************************************************
    
    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