杰哥私房题──麦森数

问题描述
形如2p-1 的素数称为麦森数，这时P 一定也是个素数。但反过来不一定，即如果P 是
个素数。2p-1 不一定也是素数。到1998 年底，人们已找到了37 个麦森数。最大的一个是
P=3021377，它有909526 位。麦森数有许多重要应用，它与完全数密切相关。
你的任务：输入P (1000<P<3100000) , 计算2p-1 的位数和最后500 位数字（用十进制高
精度数表示）
输入数据
只包含一个整数P(1000<P<3100000)
输出要求
第1 行：十进制高精度数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

 

#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
const int LEN = 125;

void multiply(int* a, int* b){
	int c[LEN];
	memset(c, 0, sizeof(c));
	int nCarry, total = 0;
	for(int i = 0; i < LEN; i++){
		nCarry = 0;
		for(int j = 0; j < LEN - i; j ++){//因为只要500位，所以算到125-i-1就够了
			total = c[i + j] + a[j] * b[i] + nCarry;
			c[i + j] = total % 10000;
			nCarry = total / 10000;
		}
	}
	memcpy(a, c, sizeof(c));
}

int main(){
	int p;
	cin >> p;
	cout << (int)(p * log10(2)) + 1 << endl;
	int anPow[LEN];
	int result[LEN];	
	anPow[0] = 2;
	result[0] = 1;
	for(int i = 1; i < LEN; i++){
		anPow[i] = 0;
		result[i] = 0;
	}
	while(p > 0){
		if(p & 1)
			multiply(result, anPow);
		p>>= 1;
		multiply(anPow, anPow);
	}
	result[0] --;
	for(int i = LEN - 1; i >= 0; i--){
		if(i % 25 == 12)
			printf("%02d\n%02d", result[i] / 100, result[i] % 100);
		else{
			printf("%04d", result[i]);
			if(i % 25 == 0)
				cout << endl;
		}
	}
	return 0;
}

 

评论

3 楼 yidao620c 2009-04-16  

嗯。最近想学算法。杰哥指导下该从何入手。

2 楼 night_stalker 2009-03-19  

比较常用的译名是梅森数吧

1 楼 yukaizhao 2009-03-18  

很强悍呀