1049. Counting Ones (30)[計算1 的個數]——PAT (Advanced Level) Practise

1049. Counting Ones (30)[計算1 的個數]——PAT (Advanced Level) Practise

題目信息

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代碼

#include 

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;
}