題目信息
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>