poj 1150 The Last Non-zero Digit

 1 /**
 2 大意： 求A（n，m）的结果中从左到右第一个非零数
 3 思路： 0是由2*5的得到的，所以将n！中的2，5约掉可得（2的数目比5多，最后再考虑进去即可）
 4 那n！中2 的个数怎么求呢？ 
 5 int get2(int n){
 6     if(n==0)
 7         return 0;
 8     return n/2+get2(n/2);
 9 }
10 eg: 1*2*3*4*5*6*7*8*9*10   约去2，5可得，，1*1*3*1*1*3*7*1*9*1
11      所以最后肯定是3，7，9.。的数列，，那么在最后的数列中3，7，9，有多少个呢？
12 可以这样考虑： 1,2,3,4,5,6,7,8,9,10 可以分为奇偶数列 即 1，3，5，7，9         2，4，6，8，10===>2*(1,2,3,4,5)
13 这就出现了递归，，g(n) = g(n/2)+f(n)  {  f(n)为奇数列  }  
14 那在奇数列中怎么找3，7，9 的个数呢？
15  1，3，5，7，9，11，13，15，17，19   有可以再分  1，3，7，9，11，13，17，19  ///5，15，25 ====〉5*（1，3，5）
16 这里有出现了递归，，f(n,x) = n/10 + (n%10>=x) + f(n/5,x) 
17 **/
18 
19 #include <iostream>
20 using namespace std;
21 
22 int s[][4]={
23     {6,2,4,8},{1,3,9,7},{1,7,9,3},{1,9,1,9}
24             };
25 int get2(int n){
26     if(n==0)
27         return 0;
28     return n/2+get2(n/2);
29 }
30 
31 int get5(int n){
32     if(n==0)
33         return 0;
34     return n/5+get5(n/5);
35 }
36 
37 int get(int n,int x){
38     if(n==0)
39         return 0;
40     return n/10+(n%10>=x)+get(n/5,x);
41 }
42 
43 int getx(int n,int x){
44     if(n==0)
45         return 0;
46     int res =0;
47     res = getx(n/2,x)+get(n,x);
48     return res;
49 }
50 
51 int main()
52 {
53     int n,m;
54     while(cin>>n>>m){
55         int num2 = get2(n)-get2(n-m);
56         int num5 = get5(n)-get5(n-m);
57         int num3 = getx(n,3)-getx(n-m,3);
58         int num7 = getx(n,7)-getx(n-m,7);
59         int num9 = getx(n,9)-getx(n-m,9);
60         if(num2<num5){
61             cout<<5<<endl;
62             continue;
63         }else{
64             int res =1;
65             if(num2!=num5){
66                 num2 = num2-num5;
67                 res  = res*s[0][num2%4];
68                 res = res%10;
69             }
70             res *= s[1][num3%4];
71             res %=10;
72             res *= s[2][num7%4];
73             res %=10;
74             res *= s[3][num9%4];
75             res = res%10;
76             cout<<res<<endl;
77         }
78     }
79     return 0;
80 }