[NOIP2003普及组]麦森数

不得不纪念一下这道题,因为我今天一整天的时间都花到这道题上了。因为这道题,我学会了快速幂,学会了高精度乘高精度,学会了静态查错,学会了一个小小的变量的使用可能会导致整个程序挂掉。。

 

Description

形如2^P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2^P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000 < P < 3100000),计算2^P-1的位数和最后500位数字(用十进制高精度数表示)

Input

只包含一个整数P(1000 < P < 3100000)

Output

第一行:十进制高精度数2^P-1的位数。
第2-11行:十进制高精度数2^P-1的最后500位数字。(每行输出50位,共输出10行,不足500位时高位补0)
不必验证2^P-1与P是否为素数。

Sample Input

Sample Output

看到这题第一感觉是简单,很容易就看懂了。然后,就没有然后了。不知道怎么做了,直接不断乘2肯定不仅超时而且超出范围。。明显用高精度。然后不知道用高精度乘这么多次会不会超时,于是想到快速幂。

想归想,这俩算法我都不会。于是问百度,看题解,看了好久,终于在上午似懂非懂地编出了快速幂(求a^b%m)。下午继续研究,终于又编出了高精度乘高精度的程序。这可完全是我自己蒙出来的,我没找到高精度乘高精度的例程。所以毫无悬念地在2^p,p上万时挂掉了。
就是因为自己想的高*高用了t、tt以及计算时处理进位,程序在次数较高的时候才挂掉了。这三个全部改掉才可以,只改掉任何一个仍然会挂。

本题分两问,第一问求位数,可以证明:当x有n位时,必有10^(n-1)<=x<10^n(如x有3位时必有100=10^2<=x<1000=10^3),取常用对数,n-1<=lgx<n,即lgx的整数部分是n-1,也就是说数x的位数是lg(x)的整数部分+1。故欲求x的位数只需求floor(log10(x)+1+0.5)(floor(x+0.5)是计算x的整数部分,这样可以避免浮点误差)。

然后第二问是去掉了取模运算、用上高精度的快速幂:

话说我看了很多题解,都发现里面有一句“末位不要忘了减1”,一直百思不得其解。直到最后我才明白,原来是因为题目让算2^p-1。。还有,写这个程序的时候除了很多小错,比如递减的for循环写成了i++,x[i]*y[j]写成了x[i]*y[i]……这些都是编译器查不出来的,只有静态查错,也就是传说中的用眼睛自己看,才可以查到。从此以后我再也不敢完全依靠编译器了。

废话不多说,直接贴AC程序:

吐槽一下,这道题的测试数据真变态,第一组数据就把我的程序干掉了。。再吐槽一下,C++看起来真是比C好多了,我真想换C++。。

代码下载:

mason

奉上本题测试数据:点此下载

发表评论

电子邮件地址不会被公开。 必填项已用*标注