### 题目
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:**
```cpp
12
```
**Sample Output:**
```cpp
5
```
### 解析
**题意:**
给定一个正整数`N`,求从`1-N`的所有正整数中,`1`总共出现了几次。
**思路:**
这道题是《编程之美》上面的一道题(第2.4节),需要通过分析来总结规律,然后总结出公式,如果暴力去“数”1的个数,显然会超时。但如果通过公式来算的话,时间复杂度就直接降到O(1)。具体分析过程比较复杂,详情参见《编程之美》2.4节“1的数目”,这里只给出结论——从右往左拆解当前数字,逐位分析每个位置出现1的次数,然后统计其规律与当前位置左右部分数字的关系,最后累加,即为结果。

以数字`N=345、N=305、N=315`为例,**寻找`十位`上是`1`的数字个数**。将数字分成`3`部分:`百位、十位、个位`。
- 当`N=345`时,从`1-345`这`345`个数中,`百位`数字可以出现`0、1、2、3`四种,每种`百位`数字都可以跟一个数字为`1`的`十位`,而每种`十位`数字可以跟`0-9`这十种数字,所以从`1~345`这`345`个数中,`十位`数字为`1`的数共有`(3+1)×10=40`个,故`十位`上的`1`共出现`40`次。
- 当`N=305`时,`百位`上数字依然可以出现`0、1、2、3`四种,但要注意,`百位`数字为`3`时,后面不能再跟数字为`1`的`十位`,因为这样的数字已经大于`305`了,所以从`1~305`这`305`个数中,`十位`数字为`1`的数共有`3×10=30`个,故`十位`上的`1`共出现`30`次。
- 当`N=315`时,`百位`上数字依然可以出现`0、1、2、3`四种,此时要注意,`百位`数字为`3`时,后面可以再跟数字为`1`的`十位`,但这样的数字`个位`上只能出现`0-5`这`6`个数,即`310、311、312、313、314、315`,其他数字都会大于`315`,所以从`1~315`这`315`个数中,`十位`数字为`1`的数共有`3×10+(5+1)=36`个,故`十位`上的`1`共出现`36`次。
综上,对于任意一个数字`N`,当要判断`从右向左`数第`i`位上`1`出现的次数`num`时,可以将这个数字分成三部分,分别用`left、current、right`表示,即`left=数字N在i位左侧的数字、current=数字N在第i位的数字、right=数字N在i位右侧的数字`。例如数字`N=123456`,判断`从右向左第3位`也就是`百位`上,即数字`4`所在位置`1`出现的次数时,`left=123、current=4、right=56`。此时分三种情况进行计算:
- current=0:num = left × 10^i^
- current=1:num = left × 10^i^+ (right + 1)
- current>1:num = (left + 1) × 10^i^
- 其中`10^i^`就表示的是当前处理的是个位、十位、还是百位、千位.......
所以如果使用`result`存储最后的答案,用`a`表示当前是个、十、百、千位……使用`left`表示左边部分表示的数字,`right`表示右边部分表示的数字。
则`从右往左`(从个位往高位)开始遍历,判断当前位置的字符:
- 若是`0`:则在当前位置可以出现1的次数为`left * a`次。
- 若是`1`:则在当前位置可以出现1的次数为`left * a + right + 1`次
- `其他`(2-9):则在当前位置出现1 的次数为`(left+1)*a`
### 代码
```cpp
#include
using namespace std;
int main() {
int n, ans = 0, radix = 1, left, right, curr;
cin >> n;
while (n / radix) {
left = n / (radix * 10); curr = n / radix % 10; right = n % radix;
if (curr == 0) ans += left * radix;
else if (curr == 1) ans += left * radix + right + 1;
else ans += (left + 1) * radix;
radix *= 10;
}
cout << ans;
return 0;
}
```

PAT 1049 Counting Ones (30分) 编程之美--1的个数