对数是数学史上一个重要的发明,有着划时代的意义,对数函数在信息学竞赛中也同样有着非常重要的应用,很多时候,合理使用对数函数会简化我们的程序,降低时间复杂度和编程复杂度。
注:为了使描述方便,以下均用log(a)N的形式表示一个普通对数(非常用对数和自然对数),其中a为底数,N为真数;用logn表示log(2)n。
例1:求一个十进制数的位数。
解析:我们以这道很简单的题目作为一个小小的引子。这一题当然有很朴素的O(lgn)的算法,应当说这已经很好了,但是我们应该考虑一下,是否有更简单的方法。注意看朴素算法的时间复杂度,lgn,我们知道朴素算法的实现是不停的div10,分离出它的每一位,所以我们是否可以猜想n的位数是lgn。结论是显然的,所以这一题的答案就是Trunc(lgn+1),因为pascal中没有常用对数,只有自然对数,利用换底公式我们得到Trunc(ln(n)/ln(10))+1。
对数的应用远远不止于此,利用对数,我们可以将乘除运算化为加减运算,将幂运算化为乘除运算,从而提高我们程序的效率。下面我们再看一个例子。
例2:求a^b。
解析:这样的题目我们有O(n)的朴素算法,也有O(logn)的快速幂算法,但是由上一题的启示我们是否可以利用对数在O(1)的时间内算出a^b。2^k显然是可以的,因为有shl和shr的位运算(2^k=shl(1,k))。那么一般的呢?答案是仍然可以在O(1)的时间内算出。我们知道a^(log(a)N)=N,所以a^(log(a)(N^M))=N^M,由对数的性质我们可以知道a^(M*log(a)N)=a^(log(a)(N^M))=N^M(注意,幂运算已经化为乘法运算了),换句话说,e^(b*ln(a))=a^b,而pascal中是提供e的指数函数(exp)和对数函数(ln)的,于是我们得到:
a^b=Trunc(exp(ln(a)*b))
需要注意的事,由对数定义可知,这里a不能为0。
应用:麦森数(Noip2003普及组复赛第4题)
【问题描述】形如2P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000<P<3100000),计算2P-1的位数和最后500位数字(用十进制高精度数表示)
【输入格式】
文件中只包含一个整数P(1000<P<3100000)
【输出格式】
第一行:十进制高精度数2P-1的位数。
第2-11行:十进制高精度数2P-1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证2P-1与P是否为素数。
【输入样例】
1279
【输出样例】
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
解析:
我们撇开高精度运算,这不是本文的重点,在这里,我们关注的是第一问,也就是十进制高精度数2P-1的位数,这一问是可以在高精度运算结束后统计出的,但是例1与例2可以帮助我们在做高精度之前算出这个值的。
首先我们要明确一点,不可能先算出2P-1,再求它的位数,所以需要对例1例2的公式加以组合变形。又因为2P不可能为10的整数次幂,也就是说2P-1和2P位数必然相等,于是问题转化为求2P的位数。
将2和p代入例2的公式则有2P=trunc(exp(ln(2)*p)),将右边整体代入到例1的公式中,则有2P的位数=
Trunc(ln(2)*p/ln(10))+1
至此问题圆满解决。
笔者以上列出的只是对数函数在信息学竞赛中几点小小的应用,但是我们可以由此看到,合理使用对数函数对我们的程序是有很大帮助的,随着我们不断探索,对数函数的应用也会越来越广泛。