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,...,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$ 也是一样的，就直接结合代码解释了：

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$ ：

   $$\begin{align} x&\leq n\\ 10p+3&\leq 10q+r\\ 10p&\leq 10(q-1)+(r+7)\\ p&\leq q-1+\lfloor\frac {r+7}{10}\rfloor\\ p&\leq q-1 \end{align}$$

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

2. $r\ge 3$：

   $$\begin{align} x&\leq n\\ 10p+3&\leq 10q+r\\ 10p&\leq 10q+(r-3)\\ p&\leq q+\lfloor\frac{r-3}{10}\rfloor\\ p&\leq q \end{align}$$

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

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

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

//参数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$ 的个位，从而得到它们的积的个位。

---

· 源代码

/*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 ，欢迎提问~