--组合数学（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
",solve(b) - solve(a-1));
40     }
41     
42 }