【剑指offer】【9度oj】整数中1出现的次数

时间限制：1 秒

内存限制：32 兆

特殊判题：否

题目描述：

亲们！！我们的外国友人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

例如1234这个数，1的个数之和为千位上出现的次数+百位上出现的次数+十位上出现的次数+个位上出现的次数，

                               即1出现的次数689    =    235          +           100              +                130          +         124

又例如1046这个数，1出现的次数362   =    47           +           100              +                 110         +         105

再例如1146这个数，1出现的次数362   =    147         +          147               +                 120         +         115

通过分析可知，在某位上出现1的次数与自身位相关，而且也与之前的位和之后的位相关。

由此可将一个数拆分为   前面部分+中间位+后面部分，或front+mid+back（例如1146在求百位中的1出现次数时，可看成1+1+46来处理）

我们可得如下规律：

        当mid > 1时，  1出现的次数为10^(back的位数) * (front+1) ；
        当mid == 1时，1出现的次数为10^(back的位数)* front + (back + 1) ；
        当mid == 0时，1出现的次数为10^(back的位数) * front ；

代码如下：

#include <stdio.h>long long fun(long long n){if(n < 1)return 0;long long count = 10, num = 0, front, mid, back,m;front = n;mid = 0;back = 0;while(front){front = n/count;m = n%count;mid = m/(count/10);back = m%(count/10);if(mid > 1)num = num + (count/10) * (front+1);else if(mid == 1)num = num + (count/10) * front + (back + 1);else num = num + (count/10) * front;count = count * 10;}return num;}int main(){long long n,m;while(scanf("%lld %lld",&n,&m)!=-1)if(n>m)printf("%lld\n",fun(n) - fun(m-1));elseprintf("%lld\n",fun(m) - fun(n-1));return 0;}