麦森数（19/9/17）

Bertha 。 2024-04-19 11:18 53阅读 0赞

问题  
形容2^P -1的素数称为麦森数，这时P也一定是个素数。但反过来不一定，即如果P是个素数，2^P-1不一定是素数。到1998年底，人民已经找到37格麦森数。最大的一个是P= 3 021 377，它有909 526位。  
你的任务是输入P（1000<P<3100000）, 并且计算2^P-1的位数和最后500位数字（用十进制高精度表示）。

输入数据  
只包含一个整数P（1000<P<3100000）.

输出要求  
第一行输出十进制数高精度数2^P - 1的位数，第2~11行输出十进制高精度数2^P - 1的最后500位数字（每行输出50位，共输出10行，不足500位时高位补0）。不必验证2^P-1 和P是否为素数。

样例输入  
1279

样例输出  
386  
00000000000000000000000000000000000000000000000000  
00000000000000000000000000000000000000000000000000  
00000000000000104079321946643990819252403273640855  
38615262247266704805319112350403608059673360298012  
23944173232418484242161395428100779138356624832346  
49081399066056773207629241295093892203457731833496  
61583550472959420547689811211693677147548478866962  
50138443826029173234888531116082853841658502825560  
46662248318909188018470682222031405210266984354887  
32958028878050869736186900714720710555703168729087

解题思路：  
首先考虑输出2^P - 1有多少位。由于 2^P 的个位数只可能是2，4，6，8，所以2^P-1 和 2^P的位数相同。使用C/C++标准库中在math.h里声明的，以10为底的对数的函数，即double log10（double x）函数，就能轻松求得2^P 的位数。2^P 的值需要用一种高效的办法来算。  
显然，对于任何P>0，考虑P的二进制形式，则不难得到：P = a0 *（2^0 ） + a1 \* （2^1）+ a2 \* （2^2） + ……+ a(n-1) \* （2 ^ (n-1) ）+ 2^n  
(a后面的数字表示ai，这个我不会打出脚标，我太难了~)  
这里ai要么是0， 要么是1.  
因而：2 ^ P = (2 ^ a0) \* (2 ^ 2a1) \* (2 ^ 4a2) \* (2 ^ 8a3) \* ……*(2 ^(an-1 \* 2^(n-1))) \* 2^(2 ^ n)  
(倒数第二个是2的（a（n-1）\*2的n-1次方）的次方，我太难了~)  
计算2^P 的办法就是：先将结果的值设为1，计算2^1 。如果a0的值为1，则将结果乘以2^1 ;计算2^2 ,如果a1为1，则将结果乘以2^2；……；总之，第i步（i从0~ n，an是1）就计算2^ (2^i) , 如果ai为1， 则将结果乘以 2^ (2^i)。每次 由 2^ (2^i) \* 2^ (2^i) 就能算出 2^ (2^(i+1))。

实现代码：

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    int a[1001],b[501];
    
    void solve(int x)
    {
    	if(x==0) return;
    	else solve(x/2);
    	for(int i=1;i<=500;i++)
    	{
    		for(int j=1;j<=500;j++)
    		{
    			if(x%2==0) 
    				a[i+j-1]+=b[i]*b[j];
    			else 
    				a[i+j-1]+=b[i]*b[j]*2;
    			
    		}
    	}
    	for(int i=1;i<=500;i++)
    	{
    		b[i]=a[i]%10;
    		a[i+1]+=a[i]/10;
    	}
    
    	memset(a, 0, sizeof(a));
    }
    
    int main()
    {
    	int p;
    	scanf("%d", &p);
    	b[1]=1;
    	solve(p);
    	printf("%d\n", (int)(p*log10(2))+1);
    	for(int i=500;i>=2;i--){
    		printf("%d", b[i]);
    		if(i%50==1)
    		printf("\n");
    
    	}
    		printf("%d", b[1]-1);
    		return 0；
    			
    	}

（此代码是由我参考他人代码后所写，若原博主有意见可联系更改或删除，谢谢）