首页 > 代码库 > poj 1150 The Last Non-zero Digit

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 }