基础数学的应用--POJ1423
方法1：
POJ1423题目的意思是给出一个N，问N!的数字有多少位。对于这种题目，我们首先想到的是使用高精度乘法的方法模拟，最后在看看有多少位，但是这道题目的数据庞大，达10^7，高精度模拟显然不行。因此我们必须另外想方法。
要知道一个数字的位数是多少，我们可以用log10函数求得。例如，对于一个数，N=10，10!=3628800，而log10(3628800)=6.559763033，那么只要将这个数向上取整，就是7，就是10!的位数。当然，直接算log10(10!)是不可能的，但是根据对数的加法的性质，我们有log10(10!) = log10(1*2*3.....*9*10)=log10(1) + log10(2) + log10(3) + ... + log10(9) +log10(10)，这样的话，即使是10^7，我们也可以对其直接进行log10的函数计算。至于向上取整，我们有另外一个函数，其原形double ceil(double)。有这个函数我们可以很方便的对一个浮点数向上取整。
问题又来了，这道题目给出的限时是1000ms。假如对于给出的每一个数据，我们都慢慢地将它从log10(1) 慢慢加到log10(N)，绝对会超时。因为里面有大量重复的运算，例如log10(1)，如果有100组数据，那么它的值就会被计算100次。于是，我们想到，能否把所有计算过的log10值保存起来，然后若遇到重复的，就从这个结果数组里面提取就可以了，不用再计算。这个方法很好，但是题目给出的数据规模比较大，开一个10^7大的double数组，绝对会Memory Excceed Limit。那么，既然如此，我们应该用什么方法来计算呢？
假设问题给出的C组数据，是从小往大排列的，例如，给出三个数据，10，20，30，那么我们可以想到，计算log10(20!)的时候，我们是可以利用long10(10!)的结果。因为：
log10(10!) = log10(1) + log10(2) + log10(3) + ... + log10(9) +log10(10)
log10(20!) = log10(1) + log10(2) + log10(3) + ... + log10(9) +log10(10) + log10(11) + log10(12) +... +log10(19) + log10(20)
容易看出：
log10(20!) = log10(10!) + log10(11) + log10(12) +... +log10(19) + log10(20) ;
同理：
log10(30!) = log10(10!) + log10(21) + log10(22) +... +log10(29) + log10(30) ;
位数=CEIL(log10(n!))
方法2：
直接利用《计算机程序设计艺术》所给出的公式
CEIL(log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e))
评论
发表评论