zhizhi_c @ 2023-01-08 20:16:57
本地测出来输出全是0。
#include<stdio.h>
#include<math.h>
#include<string.h>
int n,i,la=1,a[1005],ans[1005],tmp,*p;
void result(int *arr1,int *arr2){
int num[1005];
memset(num,0,sizeof num);
for(int i=1;i<=500;i++)
for(int j=1;j<=500;j++)
num[i+j]+=arr1[i]*arr2[j];
for(int i=1;i<=500;i++){
num[i+1]+=num[i]/10;
num[i]%=10;
}
memcpy(arr1,num,sizeof num);
}
int main(){
scanf("%d",&n);
printf("%d",(int)(n*log10(2)+1));
a[1]=1;
ans[1]=2;
while(n){
if(n&1) result(ans,a);
n>>=1;
result(a,a);
}
a[1]--;
for(i=500;i>=1;i--)
if(i%50) printf("%d",ans[i]);
else printf("\n%d",ans[i]);
return 0;
}
by Misophiliac @ 2023-01-08 21:01:20
1.这里所有下标需要从0开始,这样result函数里的i+j取最小值时才会是末位
2.a和ans初值应该反过来
3.快速幂完减1时,如果末位为负要借位
改完之后样例没问题
by zhizhi_c @ 2023-01-08 21:32:01
@yuanxiuan 谢谢