# PAT A1049题解

1049 Counting Ones （30 分）
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

``````//部分超时代码
#includecstdio
#includeiostream
using namespace std;
int change(int n,int a[]){
int count=0;
while(n!=0){
a[count++]=n%10;
n=n/10;
}
}
int main(){
int n,m,sum=0;
cinn;
for(int i=1;i=n;i++){
int a[10]={0};
change(i,a);
for(int j=0;j10;j++){
if(a[j]==1){
sum++;
}
}
}
coutsum;
return 0;
}
``````

``````//AC 代码
#include iostream
using namespace std;
int main() {
int n, left = 0, right = 0, a = 1, now = 1, ans = 0;
scanf("%d", n);
while(n / a) {
left = n / (a * 10), now = n / a % 10, right = n % a;
if(now == 0) ans += left * a;
else if(now == 1) ans += left * a + right + 1;
else ans += (left + 1) * a;
a = a * 10;
}
printf("%d", ans);
return 0;
}
``````