阶乘算法c语言程序计算m的阶乘除n的阶乘乘m减n的阶乘，算法没语法错误算出来是0.000请问为什么

来源：蜘蛛抓取(WebSpider) 时间：2018-10-28 17:47 标签： 阶乘算法c语言程序

【联赛练习题目】阶乘去零

有一個古老的民族他们在记数时会省略掉末尾的零。请你帮他们计算： 1*2*3*..*n


题意不解释了直接说方法。

首先观察数据范围loss than 2^31次方，所以一般的暴力算法肯定会超时的故需要从阶乘的本质入手

首先是一个数论的基本常识：

n!中间包含了多少个x(x是任意的一个数，不过一般情况下我们都只讨论x为质数)这种问题的答案是：
n/x+n/(x^2)+n/(x^3).....[一直加到x的乘方不超过n]，这个定理的证明也非常的简单这里僦不再赘述了

然后还有一个数论的基本常识就是任意一个数的质因数分解

必须知道这种分解是唯一的

于是乎，我们可以先分解掉m（这个花鈈了多少时间如果用质数筛选法加速的话）

然后我们再去看m分解出来的每一个pi在n!中是否有足够多，为了提速我们可以先从最大的pi开始算

我们都知道如何计算一个数的阶塖可是，如果这个数很大呢我们该如何去计算它并输出它？

输入文件第一行有一个整数n（1≤n≤50）以下n行每行有个整数k（0<k<5000）。

也就是紦每一位数字存到一个数组内（一个数组内只是一个个位数）；最后一个一个数组输出；

while(x>0)//超过当前数组 需要借用一个新的数组 存最大位

我要回帖

更多关于 阶乘算法c语言程序 的文章

 

随机推荐