LinuxSir.cn,穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
12
返回列表 发新帖
楼主: soloforce

[算法]问一道ACM练习题

[复制链接]
发表于 2006-7-17 09:34:52 | 显示全部楼层
我觉得 用到大整数还不如Java 虽然运行慢一些 可是省事
兄弟斗胆 给这个题目延伸一下
求n!最末尾的非零数
N不小于1M
也是个经典问题了
回复 支持 反对

使用道具 举报

 楼主| 发表于 2006-7-17 11:24:20 | 显示全部楼层
Post by MurphyDog
我觉得 用到大整数还不如Java 虽然运行慢一些 可是省事
兄弟斗胆 给这个题目延伸一下
求n!最末尾的非零数
N不小于1M
也是个经典问题了


n>5的时候,n! 最末尾一定是0
不知您的非零数指哪些?
回复 支持 反对

使用道具 举报

发表于 2006-7-17 11:39:39 | 显示全部楼层
for example 10!=3628800
那么就是8
15!=1307674368000
也是8
就是n!除了0之外的数字 最末尾的那个
回复 支持 反对

使用道具 举报

发表于 2006-7-20 14:05:09 | 显示全部楼层
只能解决N<10M的,用dp
大于10M暂时想不出来。
m[k + 1] = d[m[k] * d[k + 1]]
m[n]表示n!的最后一个不为0的数。
d[n]表示数n最后一个不为0的数。
回复 支持 反对

使用道具 举报

发表于 2006-7-24 14:40:50 | 显示全部楼层
给个想法,没有具体实现,应该可以解决1M位以内的阶乘的最后非零数字问题。
当然如果超出long long的话需要用大整数的运算。

大体思想:
从n的最低位到最高位依此计算出最后一个非零数字在第k位的所有在1。。n范围内的数字所提供的2,3,7,9的个数,然后计算出总的2,3,7,9的个数,利用单个数字相乘最后一位数字的循还性,计算出n!的最后一位非零数字。

具体想法如下:

1.对于n!,考虑每个数最后一位非零的数子,然后统计从1到n提供了多少个2。。9(0,5先都不考虑,1不用考虑),从最后一位开始考虑.
对于提供了m个数字d(从1到9)有规律如下,假设对于2,2 * 2 = 4, 2 * 4 = 8 ,2 * 8 = 16,2 * 6 = 12 如此循环,所以对于2来说它的周期为4,也就是对于m个2它所提供的最后一位数字为m % 4所对应的6,2,4,8,对于为偶数的数字,都把其拆分成2和非偶数的乘积,例如对于m个6,则添加m个2和m个3,而m个8则只添加3m个2。

2.下面讨论5的问题,对于5来说,它必然会与一个2相乘而得到0,所以先要求出从1。。n提供了多少个5,注意对于5^x提供了x个5,然后减去相应个数的2(2一定比5多,由第一步保证)。

3.下面在考虑包含5的数提供的最后非零数字是什么,举例如下对于末两位为05,15,35,45,55,65,75,85,95并且非5的幂的数,分别提供的非零数字为1,3,7,9,1,3,7,9..........(与2相乘后)。

4,再考虑5的幂,注意凡是5的幂,最后必然与2相乘而提供一个1,所以可以不用考虑。

5.那么下一个问题就是有多少个05,15...这样的数呢?答案很简单就是所有5的倍数减去25的倍数再减去10的倍数再加上50的倍数(容斥原理)。

6.可以看到以上算法对于最后一位为0的情况没有处理,这是为什么呢?其实是因为递归的原因,考虑所有后k位为0的数,其实相当于处理(n / (10^k))!,所以此算法是递归的,因为任意的阶乘最后非零数字不会是5,所以只要考虑最后一个非零数字在第k(从1。。(n的位数))位提供了多少个2,3,7,9然后再利用1提到的方法就可以算出最后一位非0的数字。

此算法的复杂度,是与位数有关,但是需要用到大量的除法操作,所以对于10的8次方位数以下的n的阶乘,应该在10秒内得出结果,但是考虑到需要用到大整数相除,要想在10秒内得出结果,尽量不要让n的位数超过10的6次方。

还有要注意的是,此算法实现起来琐碎,所以。。。。。我就不实现了。呵呵。
回复 支持 反对

使用道具 举报

发表于 2006-7-25 13:52:54 | 显示全部楼层
最开始我所说的那个dp算法是错误的。惭愧惭愧。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表