思维难度有一点大……
不知道如果考试的时候碰到这种题哪能想出来……
· 题目
给出正整数 $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 | //当前数列为 1,2,3,...,n |
其实对于提取 $5$ 也是一样的,就直接结合代码解释了:
1 | int Get5(int n){ |
其实两个函数可以合为一个函数。
- 查找提取完因数$2,5$后末尾为$3,7,9$的数的个数
我们以查找提取完因数$2,5$后末尾为$3$的数的个数为例。
假设我们要求 $1$ 到 $n$ 的数中末尾为 $3$ 的数的个数,相当于个位固定为$3$且小于等于$n$的数。
不妨设个位为 $3$ 且小于等于 $n$ 的数 $x=10p+3$,并且令 $n=10q+r$($p,q$ 是非负整数,$r$ 是一位数)。则分成两类:
$r<3$ :
可见 $p$ 可取的值为 $0,1,…,q-1$,共 $q$ 个,则满足条件的 $x$ 有 $q$ 个,即 $\lfloor\frac n{10}\rfloor$ 个。
$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 | //参数k就是统计末尾为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 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~