题目1373：整数中1出现的次数（从1到n整数中1出现的次数）

题目描述：

亲们！！我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

 

输入：

输入有多组数据,每组测试数据为一行。

每一行有两个整数a,b(0<=a,b<=1,000,000,000)。

 

输出：

对应每个测试案例,输出a和b之间1出现的次数。

 

样例输入：

0 51 1321 5531 99

样例输出：

1647

主要思路：计算数字每一位出现1的次数，并相加，得到该数字中1出现的次数。

例如：1304中，个位出现1的次数，是131次，即1304/10 + 1 = 131；十位出现1的次数 (1304/100)*10  = 130；百位出现1的次数 (1304/1000 + 1)*100 = 200 ；千位出现1的次数( 1304/10000)*1000+1+1304-int(1304/1000)*1000 = 305 总计766；

总结一下，计算数字n中1的个数，得到以下规律：从个位开始，对每一位数字进行处理，先计算对10取余的余数rem，计算除以10以后的数字tmp，如果余数为0，则该位为1的数字个数为 base*tmp ；余数为1，该位为1的数字个数为n-int(n/base)*base +1 + tmp*base；base在每计算完一位数字后，乘以10，代码如下：

#include <stdio.h>void swap(int *a, int *b){	int tmp = *b;	*b = *a ;	*a = tmp;}int getNum1(int n){	int num =0;		int tmp,rem,base;	base =1;tmp = n;		while(tmp)	{		rem = tmp%10;		tmp = tmp/10;		if(rem == 0)		{			num+=base*tmp;		}		else if(rem == 1)		{			num  = num + (n - int(n/base)*base +1 + tmp*base);		}		else			num += (tmp+1)*base;		base *= 10;	}		return num;}int main(){	int low ,high;	while(scanf("%d%d",&low,&high)!=EOF)	{		if(low <0 || high <0)			continue;		if(low > high)			swap(&low,&high);		if(low ==0)		{			printf("%d\n",getNum1(high));			continue;		}		printf("%d\n",(getNum1(high)- getNum1(low-1)));	}				return 0;}