8: Find Last Non-Zero Digit of Factorial

uuuouou

推公式 + 找规律，可以参考一篇讲的很细致的博文：http://www.cnblogs.com/LETTers/archive/2012/04/18/2456089.html

1. // reference to http://www.cnblogs.com/LETTers/archive/2012/04/18/2456089.html
   
2. int lastDigit(int n)
   
3. {
   
4.         // kMeta【i】 = last non zero digit of i!
   
5.         static const int kMeta[10] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
   
6.         // g(i) = replace multiples of 5 by 1 in i!, we get periodical last digit
   
7.         // g(m*10+n) % 10 = kMod5[n]
   
8.         static const int kMod5[10] = {6, 6, 2, 6, 4, 4, 4, 8, 4, 6};
   
9.         // to pair those 5, we need to div 2, which is also periodical as there are much more 2 than 5
   
10.         static const int kDiv2[10] = {0, 0, 6, 0, 2, 0, 8, 0, 4, 0};
    
11. 
    
12.         if(n < 10) return kMeta[n];
    
13. 
    
14.         int res = lastDigit(n/5) * 6 * kMod5[n%10] % 10;
    
15.         int cnt = n/5 % 4;
    
16.         while(cnt--) res = kDiv2[res];
    
17.         return res;
    
18. }

复制代码