[n!最后一位非零数]poj 1150

题意：

      求P（n,m）的最后一位非零数。

 

思路：

      讨论1-----n中2,5,3,7,9因子的个数，具体移步

http://duanple.blog.163.com/blog/static/7097176720081016113033592/

 

按照我的理解，求n！最后非零为，先把1----n中‘2’和‘5’的因子的数量求出来，因为只有2和5可以构成0，接下来就要分别求出1---n中最后一位为3,7,9的数字的数量，然后相乘就可以得到n！的最后一位的数

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n, m;
ll get25(ll n ,ll x){
    ll res = 0;
    while(n){
        res+=n/x;
        n/=x;
    }
    return res;
}

ll getodd(int n ,int x){
    if(n == 0)return 0;
    return n/10 + (n%10 >= x) + getodd(n/5 ,x);
}
ll gao(int n ,int x){
    if(n == 0)return 0;
    return gao(n/2,x)+getodd(n ,x);
}

int table[4][4] ={
    6,2,4,8,//last digit of 2^4 2 2^2 2^3
    1,3,9,7,//...3
    1,7,9,3,//...7
    1,9,1,9,//...9
};
int main(){
    while(cin>>n>>m){
        m = n - m;
        ll two = get25(n ,2) - get25(m ,2);
        ll five = get25(n ,5) - get25(m ,5);
        ll three = gao(n ,3) - gao(m ,3);
        ll seven = gao(n ,7) - gao(m ,7);
        ll nig = gao(n ,9) - gao(m ,9);
//        cout<<two<<" "<<five;
        if(two<five){
            puts("5");
            continue;
        }
        ll res = 1;
        if(two != five)res *= table[0][(two - five)%4];
        res *= table[1][(three)%4];
        res *= table[2][(seven)%4];
        res *= table[3][(nig)%4];
        res %= 10;
        printf("%I64d\n",res);
    }
    return 0;
}