QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks

问你N阶乘的最低非零位上是什么数字。(0 <= N <= 4220)

从1一直乘到N,如果能整除10,就除以10,可以吗?不行,因为即使去掉低位的0,高位的非0位仍然很大,无法保存下来。

可以将N!这样表示:
N! = 2^K * 5^L * V(N)
= 2^(K-L) * V(N) * 10^L ( K >= L 如何证明呢?)

10^L不影响N!最低非零位,这个数由(K-L)以及V(N)的个位数所决定。K和L容易得到,V(N)的个位数也好得到,只要枚举i(从1到N),去除因子2和5(因子个数加到K和L),将其个位数乘以中间结果就可以了。

关键代码如下:

const int f2 [] = {6, 2, 4, 8};

int i, tmp, n2, n5;
int ans = 1;
n2 = n5 = 0;
for ( i = 1; i <= n; i ++)
{
	tmp = i;
	while ( tmp % 2 == 0 )
	{
		n2 ++;
		tmp /= 2;
	}
	while ( tmp % 5 == 0 )
	{
		n5 ++;
		tmp /= 5;
	}
	ans = (( tmp % 10) * ans) % 10;
}
ans = ( ans * f2[( n2- n5)%4] ) % 10;
printf( "%d\n", ans);
posted on 2011-02-14 15:30 quxiao 阅读(132) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理