Time Limit:1000MS Memory Limit:65536K
Total Submit:141 Accepted:26
Description
形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从标准设备输入P（1000＜P＜3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）
Input
输入包含多个测试用例，每个测试用例为一个整数P（1000＜P＜3100000）。
Output
对应每个测试用例，输出分为两部分
第1行：十进制高精度数2P-1的位数。
第2-11行：十进制高精度数2P的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
Sample Input
1279
Sample Output
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
Hint
不必验证2P-1与P是否为素数。
Source
----------------解决方案--------------------------------------------------------
是2的幂次方吧.
----------------解决方案--------------------------------------------------------
不太懂啊...
----------------解决方案--------------------------------------------------------
是求2的幂次方
----------------解决方案--------------------------------------------------------
有没有测试的地方??
我感觉直接一个高精度都是log(p)*500*500感觉没有把握过..
----------------解决方案--------------------------------------------------------
#include<stdio.h>
#include<math.h>
typedef __int64 int64;
#define mod 100000
void f(int64 b[],int64 a[])
{
int i,j,k;
int64 temp[101]={0};
for(i=0;i<100;i++)
{
for(k=i,j=0;k<100;k++,j++)
{
temp[k]+=a[i]*b[j];
}
for(k=i;k<100;k++)
{
temp[k+1]+=temp[k]/mod;
temp[k]%=mod;
}
}
for(i=0;i<100;i++)
{
b[i]=temp[i];
}
for(i=0;i<100;i++)
{
b[i+1]+=b[i]/mod;
b[i]%=mod;
}
}
int64 a[102];
int64 b[102];
void g(int p)
{
int i;
for(i=0;i<100;i++) a[i]=b[i]=0;
a[0]=1;
b[0]=2;
while(p)
{
if(p%2)
{
f(a,b);
}
f(b,b);
p/=2;
}
}
int main()
{
int p;
double x;
while(scanf("%d",&p)!=EOF)
{
x=p*log10(2);
printf("%d\n",(int)x+1);
g(p);
for(p=99;p>=0;p--) printf("%05I64d",a[p]);
printf("\n");
}
return 0;
}
还有个减法不想写了...
这几天写的太多了
----------------解决方案--------------------------------------------------------
找个能提交的地点
http://web.zjdyzx.com/doj/showproblem.asp?problem_id=1033#
那里的p最大才到１００万
[此贴子已经被作者于2007-10-12 20:25:38编辑过]
----------------解决方案--------------------------------------------------------
真诚的希望各位大哥大姐能帮一下忙
----------------解决方案--------------------------------------------------------