題目大意：計算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 閱讀(2804)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數學/數論