題目信息

    1049. Counting Ones (30)

    時間限制10 ms

    內存限制65536 kB

    代碼長度限制16000 B

    The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form. of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

    Input Specification:

    Each input file contains one test case which gives the positive N (<=2^30).

    Output Specification:

    For each test case, print the number of 1’s in one line.

    Sample Input:

    12

    Sample Output:

    5

解題思路

    《編程之美》中計算0到N包含數字1的個數問題

AC代碼

<code class="language-c++ hljs cpp">#include<cstdio>int get(long long n){    long long cur = 0, before = 0, after = 0, i = 1, cnt = 0;    while ((n / i) != 0){        cur = n / i % 10;        before = n / i / 10;        after = n - (n / i) * i;        if (cur == 0){            cnt += before * i;        }else if (cur == 1){            cnt += before * i + after + 1;        }else {            cnt += (before + 1) * i;        }        i *= 10;    }    return cnt;}int main(){    long long a;    scanf("%lld", &a);    printf("%d\n", get(a));    return 0;}</cstdio></code>