[算法]问一道ACM练习题

MurphyDog

我觉得 用到大整数还不如Java 虽然运行慢一些 可是省事
兄弟斗胆 给这个题目延伸一下
求n!最末尾的非零数
N不小于1M
也是个经典问题了

soloforce

Post by MurphyDog
我觉得 用到大整数还不如Java 虽然运行慢一些 可是省事
兄弟斗胆 给这个题目延伸一下
求n!最末尾的非零数
N不小于1M
也是个经典问题了

n>5的时候，n! 最末尾一定是0
不知您的非零数指哪些？

MurphyDog

for example 10!=3628800
那么就是8
15!=1307674368000
也是8
就是n!除了0之外的数字 最末尾的那个

Iambitious

只能解决N<10M的，用dp
大于10M暂时想不出来。
m[k + 1] = d[m[k] * d[k + 1]]
m[n]表示n!的最后一个不为0的数。
d[n]表示数n最后一个不为0的数。

Iambitious

给个想法，没有具体实现，应该可以解决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次方。

还有要注意的是，此算法实现起来琐碎，所以。。。。。我就不实现了。呵呵。

Iambitious

最开始我所说的那个dp算法是错误的。惭愧惭愧。