描述
题解
我想先建议出这道题或者翻译这道题的人去看看 《具体数学》这本书的 P91,了解了解基础的概念……
梅森数,又叫麦森数,不过我也是今天才知道还叫麦森数,不过,只要是形如 2p−1 的数都是梅森数(p 是素数),如果说 x=2p−1 中 x 和 p 都是素数,那么这个 x 则称为梅森素数……到1998年底,人们找到的梅森素数找到了37个,不是梅森数找到了37个,梅森数有无数个……截止2013年,已经发现了 48 个梅森素数,在过去的500年中,人类对最大的素数的认知一直都是梅森素数,梅森素数存在的意义十分大!
这个题中,首先让输出位数,其实这是一个公式, 2n 的位数等于 (int)(n∗log10(2))+1 ,这里不用考虑 -1 后位数是否会发生变化,因为 2n 是由 n 个质数 2 连乘的,根本不存在尾数为 0 的可能。
至于如何求具体的后五百位,其实这也不难,类似于快速幂的求法,其实就是一个二分思想。
代码
#include <stdio.h>
#include <math.h>
#include <string.h>
const int MAXBIT = 501;
int num[MAXBIT];
int tmp[MAXBIT];
int tep[MAXBIT];
void multiply(int a[], int b[])
{
memset(tep, 0, sizeof(tep));
for (int i = MAXBIT - 1; i >= 1; i--)
{
for (int j = MAXBIT - 1, k = i; j >= 1; j--)
{
tep[k--] += a[i] * b[j];
if (k == 0)
{
break;
}
}
}
for (int i = MAXBIT - 1; i >= 1; i--)
{
if (tep[i] >= 10)
{
tep[i - 1] += tep[i] / 10;
tep[i] %= 10;
}
a[i] = tep[i];
}
}
void msss(int power)
{
if (power <= 1)
{
num[MAXBIT - 1] *= 2;
return ;
}
else
{
msss(power / 2);
multiply(num, num);
if (power % 2 != 0)
{
multiply(num, tmp);
}
}
}
int main()
{
int p;
scanf("%d", &p);
num[MAXBIT - 1] = 1;
tmp[MAXBIT - 1] = 2;
msss(p);
num[MAXBIT - 1]--;
printf("%d\n", (int)(p * log10(2)) + 1);
for (int i = 1; i < MAXBIT; i++)
{
printf("%d", num[i]);
if (i % 50 == 0)
{
printf("\n");
}
}
return 0;
}