1064: 麦森数
时间限制: 1 Sec 内存限制: 128 MB
提交: 52 解决: 9
[提交][状态][讨论版]
题目描述
形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）
输入
文件中只包含一个整数P（1000<P<3100000）
输出
第一行：十进制高精度数2P-1的位数。
第2行：十进制高精度数2P-1的最后500位数字。（不足500位时高位补0）
不必验证2P-1与P是否为素数。
样例输入
1279
样例输出
386 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
#include<stdio.h>
#include<string.h>
#include<math.h>
/*
第一层难点要知道用对数求位数
第二层难点要进行大整数运算
*/
struct num { char a[500]; int size; };
void shl(num &n,int k){
int i;
i = n.size - 1;
if (i + k >= 500)i = 500 - 1 - k;
for (; i >= 0; i--)
n.a[i + k] = n.a[i];
n.size += k;
if (n.size > 500)n.size = 500;
for (i = 0; i < k; i++)n.a[i] = 0;
}
num add(num a, num b){
num c;
memset(&c, 0, sizeof(c));
int i = 0;
if (a.size > b.size)c.size = a.size;
else c.size = b.size;
for (i = 0; i < c.size; i++)
{
c.a[i] += a.a[i] + b.a[i];
c.a[i + 1] += c.a[i] / 10;
c.a[i] %= 10;
}
if (c.a[i] != 0)c.size++;
if (c.size>500)c.size = 500;
return c;
}
num multiply(num a, int b){
num c;
memset(&c, 0, sizeof(c));
if (b == 0)return c;
if (b == 1)return a;
c.size = a.size;
int i;
for (i = 0; i < a.size; i++){
c.a[i] += a.a[i] * b;
c.a[i + 1] += c.a[i] / 10;
c.a[i] %= 10;
}
if (c.a[i] != 0)c.size++;
if (c.size>500)c.size = 500;
return c;
}
num mul(num a, num b){
num c,t;
memset(&c, 0, sizeof(c));
int i;
for (i = 0; i < b.size; i++){
memcpy(&t ,& multiply(a, b.a[i]),sizeof(t));
shl(t, i);
memcpy(&c ,&add(c, t),sizeof(c));
}
return c;
}
num pow(num a, int k){
if (k == 1)return a;
num t;
memcpy(&t ,& pow(a,k / 2),sizeof(t));
if (k % 2 == 1)return mul(mul(t, t), a);
else return mul(t, t);
}
int main(){
freopen("in.txt", "r", stdin);
int p;
scanf("%d", &p);
num a;
memset(&a, 0, sizeof(a));
a.size = 1;
a.a[0] = 2;
memcpy(&a,&pow(a,p),sizeof(a));
int digit = log10((double)2)*p;
printf("%d\n", digit + 1);
int i;
for (i = 0; i < 500; i++)
if (a.a[i] == 0)a.a[i] = 9;
else break;
a.a[i]--;
for (i = 0; i < 500;i++)
printf("%d", a.a[500-1-i]);
return 0;
}