关于1000的阶乘的问题

lulijie

关于1000的阶乘：
1.    末尾有几个0？
2.    去掉末尾所有的0后最后一位是什么数字？
3.    写成质因数的幂的乘积的形式又是什么？               比如  360=2^3 * 3^2 * 5^1


------------------------------
由于1000以内的素数太多，第3题计算起来比较繁琐。
第3题就改为
    求100!的质因数的幂的乘积的形式。

[ 本帖最后由 lulijie 于 2009-8-31 00:10 编辑 ]

网罟双星

汗...出现个用穷举法的...不过这是我的最爱！哈哈

zxl0714

楼上太搞笑了。。。。这题给的数据是小了点，如果再大一点，比如１００００００，朴素算法就不好用了，复杂度要O( n^2 )（普通高精度乘法），再往上就要用快速傅里叶变换了，但是复杂度也只能到O( nlogn )。这题只需计算最后有多少０，不用计算具体数，所以我们可以用人脑列出一个递推公式，使得算法复杂度降到O( n )，所以不能依赖CPU。
还有为什么要用python，python在效率上比起c要差的远，虽然比较好编。

ukyo502

用强大的计算机CPU把结果算出来就是了~~推荐用python语言，嘿嘿

lulijie

很好！
不错！
不过可以把公式写的规范一些，像2/2=6，6/2=8之类的毕竟不太正规。

zxl0714

郁闷。。。我写错了，现在改好了。。

lulijie

f(49)=f(9)*f(9)*6/2^1=6*6*6/2=6/2=8
而49!=608281864034267560872252163321295376887552831379210240000000000

zxl0714

对，就是这样.....

lulijie

是这样么：
2/2=6
6/2=8
8/2=4
4/2=2

zxl0714

12也是取尾数的，就是2，2 / 2 = 6，6 / 2 = 8