NBUTOJ1475： Bachelor

問題描述  炎熱的暑期集訓就要結束了，在這短短的20天，大家都很努力，因為很多都是光棍嘛。balabala 所以 Marknoon 先森一直耿耿於懷，畢竟他也是單身嘛。 有一天，Marknoon 先森看著一串數字，發現了那個跟他同命相連的數字1，所以他就開始無聊起來，想知道從數字1到數字N，一共出現了幾個1。 例如N=12，則1的個數為5，出現1的數字分別為1,10,11,12。  輸入  輸入一個數N(1 <= N <= 2147483647)。  輸出  輸出從1到N中所有數字裡出現 1 的個數。  樣例輸入  3 13 123樣例輸出  1 6 57 

#include <stdio.h>
#include <math.h>

__int64 CountOne(__int64 n)//數1的個數
{
    __int64 count =0;
    if (n ==0)
        count =0;
    else if (n >1&& n <10)
    count =1;
    else
    {
        __int64 highest = n;
        __int64 bit =0;
        while (highest >=10)
        {
            highest = highest /10;
            bit++;
        }

        __int64 weight = (__int64)pow(10, bit);
        if (highest ==1)
        {
            count = CountOne(weight -1)+ CountOne(n - weight)+ n - weight +1;
        }
        else
        {
            count = highest * CountOne(weight -1)+ CountOne(n - highest * weight) + weight;
        }
    }
    return count;
}

int main()
{
    __int64 n;
    while(~scanf("%I64d",&n))
    {
        printf("%I64d\n",CountOne(n));
    }

    return 0;
}