### 题目
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;
}
```
