工学1号馆

home

« | 返回首页 | »

求阶乘最后非0位算法

By Wu Yudong on July 20, 2016

算法设计思路:

我们设F(N)表示N!的尾数。

先考虑简单的。考虑某一个N!(N < 10),我们先将所有5的倍数提出来,用1代替原来5的倍数的位置。由于5的倍数全被提走了,所以这样就不会出现尾数0了。我们先把0..9的阶乘的尾数列出来(注意,5的倍数的位置上是1),可以得到table[0..9] =(1, 1, 2, 6, 4, 4, 4, 8, 4, 6)。对于N < 5,直接输出table[N]即可;对于N >= 5,由于提出了一个5,因此需要一个2与之配成10,即将尾数除以2。注意到除了0!和1!,阶乘的最后一个非零数字必为偶数,所以有一个很特别的除法规律:2 / 2= 6,4 / 2 = 2,6 / 2 = 8,8 / 2 = 4。比较特殊的就是2 / 2 = 12 / 2 = 6,6 / 2 = 16 / 2 = 8。这样我们就可以得到如下式子:

             table[N]
F(N) = ------------ (0 <= N < 10)
             2^([N/5])

再考虑复杂的。考虑某一个N!(N >= 10),我们先将所有5的倍数提出来,用1代替原来5的倍数的位置。由于5的倍数全被提走了,所以这样就不会出现尾数0了。我们观察一下剩下的数的乘积的尾数,通过table表,我们发现这10个数的乘积的尾数是6,6 * 6的尾数还是6,因此我们将剩下的数每10个分成一组,则剩下的数的乘积的尾数只与最后一组的情况有关,即与N的最后一位数字有关。由于我们把5的倍数提出来了,N!中一次可以提出[N/5]个5的倍数,有多少个5,就需要有多少个2与之配成10,所以有多少个5,最后就要除以多少个2。注意到除2的结果变化是4个一循环,因此如果有A个5,只需要除(A MOD 4)次2就可以了。A MOD 4只与A的最后两位数有关,很好求算。剩下的5的倍数,由于5已经全部处理掉了,就变成[N/5]!。于是,我们可以得到一个递归关系:
              F([N/5]) * table[N的尾数] * 6
F(N) = ----------------------------------- (N > 10)
              2^([N/5] MOD 4)

这样我们就得到了一个O(log5(N))的算法,整除5可以用高精度加法做,乘2再除10即可。整个算法相当巧妙,写起来也比较轻松。

因为 2^N 是以4为循环节的而且table[N]是以10为循环节的,所以从10开始

                F([N/5]) * table[N的尾数] * 6
F(N) = ----------------------------------- (N > 10)
               2^([N/5] MOD 4)

右边的式子除了F[n/5]外 是以20为循环节的

写出循环的末尾数字mod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}

代码如下:

#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define MAXN 10000

int lastdigit(char *buf)
{
	const int mod[20] = { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8, 4, 
				4, 8, 4, 6, 8, 8, 6, 8, 2 };
	int len = strlen(buf), a[MAXN], i, c, ret = 1;
	if (len == 1)
		return mod[buf[0] - '0'];
	for (i = 0; i < len; i++)
		a[i] = buf[len - 1 - i] - '0';
	for (; len; len -= !a[len - 1]) {
		ret = ret * mod[a[1] % 2 * 10 + a[0]] % 10;
		for (c = 0, i = len - 1; i >= 0; i--)
			c = c * 10 + a[i], a[i] = c / 5, c %= 5;
	}
	return ret + ret % 2 * 5;
}

int main()
{
	char buf[MAXN];
	while (scanf("%s", buf) != EOF) {
		printf("%d\n", lastdigit(buf));
	}

	return 0;
}

附:杭电题目地址

http://acm.hdu.edu.cn/showproblem.php?pid=1066

如果文章对您有帮助,欢迎点击下方按钮打赏作者

Comments

No comments yet.
To verify that you are human, please fill in "七"(required)