OI题解 - The Last Non-zero Digit [POJ 1150]

思维难度有一点大……

不知道如果考试的时候碰到这种题哪能想出来……


· 题目

给出正整数 $n,m$ ,求 $A_n^m$ 的最后一个非零的数字。

例如 $A_8^5=\frac{8!}{(8-5)!}=6720$ ,则最后一个非零的数字是 $2$ 。

数据规模:$0\leq m\leq n\leq 2\times10^7$


· 解析

显然不能直接算出来……

- 初步分析

因为 $A_n^m=\frac{n!}{(n-m)!}$ ,可以想到我们分开算 $n!$ 以及 $(n-m)!$ 对答案的影响。也就是算阶乘对答案的影响。

假设我们现在考虑 $t!$ 的影响:

只要 $2$ 和 $5$ 相乘就会产生 $0$ 。
那么可以想到,我们可以把 $1$ 到 $t$ 中的每个数含有的因子$2$和因子$5$提出来,并且分别计算出提取出 $2,5$ 的数量记为 $t_2,t_5$。
(举个例子,把 “$1,2,3,4,5,6,7$” 中的因子$2,5$提出来后就变成 “$1,1,3,1,1,3,7$”,其中提取出 $2,5$ 的个数分别为 $t_2=4,t_5=1$)

我们会发现提取过后剩下的数字只有 $1,3,7,9$ ,但是 $1$ 没有什么用,所以我们只需要统计 $3,7,9$ 的个数,而且这些数只会影响个位数字,所以我们只需要统计剩下的数字中末尾为 $3,7,9$ 的数的个数,并且分别记为 $t_3,t_7,t_9$。

知道 $t_2,t_5,t_3,t_7,t_9$ 后,我们就可以计算出答案,至于怎么计算后面再说。

- 提取 $2,5$

先说如何提取 $2$ ,以从数列 $1,2,3,4,5,6,7,8,9$ 中提取 $2$ 为例子:

首先 $1,2,3,4,5,6,7,8,9$ 中除去不包含$2$的因数的数,则变成 $2,4,6,8$ ;
再将每个数提取一个$2$,可以发现能够提取出 $\lfloor\frac92\rfloor$ 个 $2$,于是数列变成 $1,2,3,4$;(我们发现数列又变成了一串连续的整数)

对 $1,2,3,4$ 继续进行操作,直到数列变成 $1$。

把上面的过程普遍化一下:在数列 $1,2,3,…,(n-1),n$ 中可以一次提取出 $\lfloor\frac n2\rfloor$ ,数列就变为 $1,2,3,…,\lfloor\frac n2\rfloor$ 。

按照上面的思路,我们可以写出一个递归函数:

1
2
3
4
5
6
7
//当前数列为 1,2,3,...,n
int Get2(int n){
if(n==1) return 0;
//Get2(n/2) 即在 1,2,3,...,n/2 中继续提取 2
//n/2 即在 1,2,3,...,n 中能够找到 n/2 个包含因数2的数
return Get2(n/2)+n/2;
}

其实对于提取 $5$ 也是一样的,就直接结合代码解释了:

1
2
3
4
5
6
int Get5(int n){
if(n==1) return 0;
//除去不是5的倍数的数后数列为 5,10,...,(n/5)*5 ,共有 5/n 个数
//对每个元素提取出一个5后,数列变为 1,2,...,n/5 ,则继续在这个数列中提取5,即 Get5(n/5)
return Get5(n/5)+n/5;
}

其实两个函数可以合为一个函数。

- 查找提取完因数$2,5$后末尾为$3,7,9$的数的个数

我们以查找提取完因数$2,5$后末尾为$3$的数的个数为例。

假设我们要求 $1$ 到 $n$ 的数中末尾为 $3$ 的数的个数,相当于个位固定为$3$且小于等于$n$的数。
不妨设个位为 $3$ 且小于等于 $n$ 的数 $x=10p+3$,并且令 $n=10q+r$($p,q$ 是非负整数,$r$ 是一位数)。则分成两类:

  1. $r<3$ :

    可见 $p$ 可取的值为 $0,1,…,q-1$,共 $q$ 个,则满足条件的 $x$ 有 $q$ 个,即 $\lfloor\frac n{10}\rfloor$ 个。

  2. $r\ge 3$:

    可见 $p$ 可取的值为 $0,1,…,q$ ,共 $q+1$ 个,则满足条件的 $x$ 有 $(q+1)$ 个,即 $\lfloor\frac n{10}\rfloor+1$ 个。

$7,9$也是一样的,所以就 OK 了~

但是我们还要先除去因数$2,5$,所以我们写了两个函数,先后除去 $2,5$:

1
2
3
4
5
6
7
8
9
10
11
//参数k就是统计末尾为k的数的个数
//后除去5
int Get379_5(int num,int k){
if(!num) return 0;
return Get379_5(num/5,k)+num/10+int(num%10>=k);
}
//先除去2
int Get379_2(int num,int k){
if(!num) return 0;
return Get379_2(num/2,k)+Get379_5(num,k);
}

- 统计答案

根据上面的操作,我们知道最后一个非零的数字是哪些数字相乘的积的个位。

我们可以发现,$x^i$ 的个位是循环的:

$i=1$ $i=2$ $i=3$ $i=4$ $i=5$
$x=2$ $2$ $4$ $8$ $6$ $2$
$x=5$ $5$ $5$ $5$ $5$ $5$
$x=7$ $7$ $9$ $3$ $1$ $7$
$x=9$ $9$ $1$ $9$ $1$ $9$

虽然 $x=5$ 和 $x=9$ 分别是以 $1,2$ 为循环节的……但是也可以看成是以 $4$ 为循环节的。

那么我们就可以快速的算出 $2^i,3^i,5^i,7^i,9^i$ 的个位,从而得到它们的积的个位。


· 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Get25(int num,int k){
if(!num) return 0;
return Get25(num/k,k)+num/k;
}
int Get379_5(int num,int k){
if(!num) return 0;
return Get379_5(num/5,k)+num/10+int(num%10>=k);
}
int Get379_2(int num,int k){
if(!num) return 0;
return Get379_2(num/2,k)+Get379_5(num,k);
}
int F[10][4];
int main(){
F[2][0]=6;F[2][1]=2;F[2][2]=4;F[2][3]=8;
F[3][0]=1;F[3][1]=3;F[3][2]=9;F[3][3]=7;
F[5][0]=5;F[5][1]=5;F[5][2]=5;F[5][3]=5;
F[7][0]=1;F[7][1]=7;F[7][2]=9;F[7][3]=3;
F[9][0]=1;F[9][1]=9;F[9][2]=1;F[9][3]=9;
int n,m,A,B;
while(~scanf("%d%d",&n,&m)){
A=n;B=n-m;
int A2=Get25(A,2),A5=Get25(A,5);
int B2=Get25(B,2),B5=Get25(B,5);
int A3=Get379_2(A,3),A7=Get379_2(A,7),A9=Get379_2(A,9);
int B3=Get379_2(B,3),B7=Get379_2(B,7),B9=Get379_2(B,9);
int D2=A2-B2,D3=A3-B3,D5=A5-B5,D7=A7-B7,D9=A9-B9;
int ans=1;
if(D2>D5) D2-=D5,D5=0;
else D5-=D2,D2=0;
if(D2) ans=ans*F[2][D2%4]%10;
if(D3) ans=ans*F[3][D3%4]%10;
if(D5) ans=ans*F[5][D5%4]%10;
if(D7) ans=ans*F[7][D7%4]%10;
if(D9) ans=ans*F[9][D9%4]%10;
printf("%d\n",ans);
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%