题目大意：计算2^P-1的位数和它的最后500位并输出。
1、计算位数：2^P-1的位数为[log10(2^P)]+1==[Plog10(2)]+1
2、计算最后500位：高精度预处理2^i，计算时将P分解成二进制形式，然后相乘，只保留500位
3、网站上的似乎和原题不太一样，原题要求每输出50位换行
以下是我的代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 570
typedef struct
{
long a[maxn];
}bign;
void mul(bign &c,bign &a,bign &b)
{
memset(c.a,0,sizeof(c.a));
for(long i=0;i<=499;i++)
for(long j=0;j<=499-i;j++)
c.a[i+j]+=a.a[i]*b.a[j];
for(long i=0;i<=499;i++)
if(c.a[i]>=10)
{
c.a[i+1]+=c.a[i]/10;
c.a[i]%=10;
}
c.a[500]=0;
}
int main()
{
long n,m,count;
bign _2[maxn]={{1},{2}},ans={{1}},t;
scanf("%ld",&n);
// Input
printf("%ld\n",(long)(n*log10(2))+1);
m=(long)(log(n)/log(2))+3;
for(long i=2;i<=m;i++)
mul(_2[i],_2[i-1],_2[i-1]);
count=0;
while(n>0)
{
if(n%2==1)
{
t=ans;
mul(ans,t,_2[count+1]);
}
count++;n/=2;
}
ans.a[0]--;
for(long i=499;i>=0;i--)
printf("%ld",ans.a[i]);
putchar('\n');
return 0;
}
posted on 2010-03-21 18:53
lee1r 阅读(2768)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论