百练oj2706 麦森数

/*首先考虑2的p次方减1有多少位。
因为2的p次方的个位只能是2,4,6,8,所以减1后和2的p次方*的

位数相同。
这里可以使用double log10(double x)函数。分析为什么?
这个地方要学会分析*/
/*其次分析2的p次方末500位怎么求?

显然,对于任何p>0,考虑p的二进制形式,不难得到:

P = a020 + a121 + a222 + … + an-12n-1 + 2n

这里,ai要么是1,要么是0.

因而:

2p = 2a0 * 22a1 * 24a2 * 28a3 * … * 2an-12n-1 * 22n(这里给大家解释下,因为无法编辑出来,所以口头说明下:2an-12n-1是2的an-1*2n-1次方,同理22n是2的2n次方)。

这里用数组来存放大整数,数组的一个元素对应于十进制大整数的

一位。如果本题也这么做,就会超时。
为了加快计算速度,可以用一个数组元素对应于大整数的四位,
即将大整数表示为10000进制,而数组中的每一个元素就存放10000

进制数的一位。
例如:存放6373384,那么只需要2个元素就可以了,a[0] = 3384,

a[1] = 637
因为要存放500个数,而一个数组元素表示4位10进制,所以只需要

125个元素就可以了。

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 #include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <assert.h>
#include <algorithm>
using namespace std;
#define LEN 125  //每个数组元素存放十进制的4位,因此数组最
 
多只要125个元素即可
/*
Multiply函数的功能是计算高精度乘法 a * b
结果的末500位放在 a 中
*/
void Multiply(int *a, int *b)
{
	int i, j;
	int nCarry; //存放进位
	int nTmp;
	int c[LEN];   //存放结果的末500位
 
	memset(c, 0, sizeof(int)*LEN);   //现开始写成500居
 
然没结果
	for(i = 0; i < LEN; i++)
	{
		nCarry = 0;
		//考虑下面为什么是LEN-i,因为 i+j < LEN,否
 
则c会越界。
		for(j = 0; j < LEN - i; j++)  
		{
			nTmp = c[i+j] + a[j]*b[i] + 
 
nCarry;
			c[i+j] = nTmp % 10000;
			nCarry = nTmp / 10000;
		}
	}
	memcpy(a, c, LEN * sizeof(int));
}
 
int main()
{
	int i;
	int p;
	int anPow[LEN];  //存放不断增长的2的次幂
	int aResult[LEN];  //存放最终结果的末500位
	scanf("%d", &p);
	printf("%d\n", (int)(p * log10(2.0))+1);
 
	//下面将2的次幂初始化为2^(2^0)
	//最终结果为1
	anPow[0] = 2;
	aResult[0] = 1;
	for(i = 1; i < LEN; i++)
	{
		anPow[i] = 0;
		aResult[i] = 0;
	}
 
 
	//下面计算2的p次方
	while(p > 0)
	{
		if(p & 1)
			Multiply(aResult, anPow);   //如果
 
ai的值为1,则将最终结果乘以22的 i 次方
		p >>= 1;
		Multiply(anPow, anPow);   //计算2的2的
 
(i+1)次方,用22的 i 次方乘以22的 i 次方
	}
 
	aResult[0]--;//2的p次方算出后减1
 
	//输出结果
	for(i = LEN-1; i >= 0; i--)
	{
		if(i % 25 == 12)
			printf("%02d\n%02d", aResult
 
[i]/100, aResult[i] % 100);
		else
		{
			printf("%04d", aResult[i]);
			if(i % 25 == 0)
				printf("%\n");
		}
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

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