转载

--组合数学（POJ3286）

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=78044#problem/B

给定两个数 m,n ,让你求在【m,n】范围里，所有数的0的个数。

思路：

从个位开始列举，1233，个位是零的情况有124种，这里我们将0算在情况里；

十位是0的时候，需要考虑，当前导为0 的时候，会导致错误，比如01,02,00，等，前两个是不含零的，后面是重复计算了，这样，1233，当十位是0的时候，百位和千位分别

是1 ~ 12，而不是 0 ~ 12，是12 * 10 种情况，如果十位恰好是0，那么就需要处理，比如 1203 这个数，十位恰好是0，这时范围变成了 1~11，因为如果依然是1~12,1209

是不满足的，所以是 11 * 10 + 4。

2015 - 5 - 16 16 : 08

79ms

 1 #include<stdio.h>  2 #include<string.h>  3 #include<algorithm>  4 using namespace std;  5 __int64 pow(__int64 a,__int64 b){  6     __int64 res = 1;  7     for(__int64 i = 1;i<=b;i++)  8     res *= a;  9     return res; 10 } 11 __int64 solve(__int64 u){ 12     __int64 ans = 0; 13     __int64 a = u; 14     __int64 first = 0; 15     while(a>0){ 16         if(!first){ 17             ans += a/10 +1; 18             first  ++; 19             a/=10; 20              21         } 22         else{ 23            if(a%10 > 0)ans += a/10 * pow(10,first); 24            else ans += (a/10 - 1)*pow(10,first) + u % pow(10,first) + 1; 25            a/=10; 26            first++;  27         } 28          29          30     } 31     return u == 0?1:ans; 32 } 33  34  35 int main(){ 36     __int64 a,b; 37     while(scanf("%I64d%I64d",&a,&b),a+b>=0){ 38          39         printf("%I64d/n",solve(b) - solve(a-1)); 40     } 41      42 }