POJ【数学】1150 The Last Non-zero Digit

POJ 1150 The Last Non-zero Digit

(这题怎么跑到组合数学里面来了？？？)

题目大意

◆题目传送门◇

求$\frac{N!}{(N?M)!}$的最后一位非零数字。

分析

我们可以将所有的因数$10$去掉，问题就转换为了求这个数的最后一位。

但直接去掉因数$10$有点麻烦，我们稍退一步，可以先去掉$2^a\times 5^b$。

这个问题等价于当$n!=a{p}^e$（$a$无法被$p$整除）时，求解$e$。

一个显然的结论是$e=n/p+n/p^2+n/p^3+\dots$。（具体可参考《挑战程序设计竞赛（第二版）》293-294页）

我们进一步可以发现，当$b>a$时，答案一定是$5$。

接下来讨论$b\le a$的情况：

我们现在只需要知道$3,7,9$的个数就可以获得答案。因为$3,7,9$的末尾都是以$4$为周期出现。

为了求解方便，我们直接讨论$n!$。

我们将$1,2,3,\dots ,N$分为两个序列：$2,4,6\dots$和$1,3,5,\dots$，即偶数序列和奇数序列。

对于偶数序列，我们只需将它除$2$即可递归转化为奇数序列。对于奇数序列，我们可以发现，每$10$个数字中就有$3,7,9$各一，但又因为其中有$5$的倍数，所以继续除$5$递归。

至此我们得到了所有的因数$2,5,3,7,9$的个数。其中$2,5$可以对消为$2^{a?b}$，我们就可以利用这些数的$N$次方尾数是$4$个一循环即可。

参考代码

#include<cstdio>
#include<algorithm>
using namespace std;const int T[][4]={
    {
    6,2,4,8},//2^4,2^1,2^2,2^3{
    1,3,9,7},//3^4,3^1,3^2,3^3{
    1,7,9,3},//7^4,7^1,7^2,7^3{
    1,9,1,9},//9^4,9^1,9^2,9^3
};int N,M;int Calc(int num,int t) {
    return num==0?0:(num/t+Calc(num/t,t));
}int g(int num,int t) {
    return (num==0)?0:(num/10+(num%10>=t)+g(num/5,t));
}
int cal(int num,int t) {
    return num==0?0:(cal(num/2,t)+g(num,t));
}int main() {
    #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifwhile(scanf("%d %d",&N,&M)!=EOF) {
    int num2=Calc(N,2)-Calc(N-M,2);int num5=Calc(N,5)-Calc(N-M,5);if(num5>num2) {
    puts("5");continue;} else {
    int ans=1;int num3=cal(N,3)-cal(N-M,3);int num7=cal(N,7)-cal(N-M,7);int num9=cal(N,9)-cal(N-M,9);if(num2>num5)ans*=T[0][(num2-num5)%4],ans%=10;ans*=T[1][num3%4],ans%=10;ans*=T[2][num7%4],ans%=10;ans*=T[3][num9%4],ans%=10;printf("%d\n",ans);}}return 0;
}