首页 > 其他 > 详细

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

时间:2014-12-10 02:13:31      阅读:236      评论:0      收藏:0      [点我收藏+]

题意:

????? 求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;
}

?

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

原文:http://bbezxcy.iteye.com/blog/2164453

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!