poj 1150 The Last Non-zero Digit

点击打开链接poj 1150

思路：组合数学+排列组合
分析：

1 求排列数A(n , m)的末尾第一个非0数。

2 总结一下，求n!最后一个非0位的步骤如下：
step1：首先将n!中所有2，5因子去掉；
step2：然后求出剩下的一串数字相乘后末尾的那个数。
step3：由于去掉的2比5多，最后还要考虑多余的那部分2对结果的影响。
step4：output your answer!

详见 点击打开链接

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int a , b;
/*找到2 3 7 9的n次方后的最后一位的循环节*/
int hash[4][4] ={
    {6 , 2 , 4 , 8},/*2 4 8 16，16的时候是6但是下标只到3所以把6放在第一个位置，以下类似*/
    {1 , 3 , 9 , 7},
    {1 , 7 , 9 , 3},
    {1 , 9 , 1 , 9}
};

/*求出含有因子x的个数*/
int getFactor(int n , int m){
   if(m == 0)
     return 0;
   return m/n+getFactor(n , m/n);
}

/*求奇数系列*/
int getOdd(int n , int m){
   if(m == 0)
     return 0;
   return m/10+(m%10 >= n)+getOdd(n , m/5);
}

/*对序列求3 7 9的个数*/
int getAll(int n , int m){
   if(m == 0)
     return 0;
   return getAll(n , m/2)+getOdd(n , m);
}

int main(){
   int two , three , five , seven , nine;
   while(scanf("%d%d" , &a , &b) != EOF){
      if(!a || !b){
         printf("1\n");
         continue;
      }
      two = getFactor(2 , a)-getFactor(2 , a-b);
      five = getFactor(5 , a)-getFactor(5 , a-b);
      
      three = getAll(3 , a)-getAll(3 , a-b);
      seven = getAll(7 , a)-getAll(7 , a-b);
      nine = getAll(9 , a)-getAll(9 , a-b);
      
      two -= five;
      int ans = 1;
      /*当含有2和含有5的数相同时候对结果是没有影响的*/
      if(two) 
         ans *= hash[0][two%4];
      ans *= hash[1][three%4];
      ans *= hash[2][seven%4];
      ans *= hash[3][nine%4];
      printf("%d\n" , ans%10);
   } 
   return 0;
}