这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
/首先考虑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个元素就可以了。
*/
#include
#include
#include
#include
#include
#include
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，则将最终结果乘以2的2的 i 次方
p >>= 1;
Multiply(anPow, anPow); //计算2的2的
(i+1)次方，用2的2的 i 次方乘以2的2的 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;
}