傳送門
這裡隻做筆記,詳細解答明年再補。
數學推導:位數=[log10(2)*p+1]
手寫高精度快速幂
代碼如下:
如上所述,我回來補解答了。(雖然已經一年半過去了)
這一題還是比較簡單的,主要是一個高精度,或者說不完全高精度。
當然了,你采用正常的高精度當然可以,但是考場上畢竟時間有限,是以隻需要打我們需要的部分即可。至于高精度,就沒什麼好說的了。以後如果有時間寫一下高精度,會在這裡補連結的(雖然我覺得高精度真的沒什麼說的必要)。
接下來本質上就是倍增做快速幂即可。
那麼我們要解釋的重頭戲就是這個位數的推導。
雖說是重頭戲,但實際上卻出奇的好了解。
我們假設我們要求的位數是a,由常識我們有:10a>2p-1>=10a-1
這就不用解釋了。接下來我們對這個不等式進行操作:
10a+1>2p>=10a-1+1(同時加一)
log10(10a+1)>log10(2p)>=log10(10a-1+1) (同時對10取對數)
a>[p*log10(2)]>=a-1 (取整)
是以也就是:
[p*log10(2)]+1>=a>[p*log10(2)]
是以a=[p*log10(2)]+1
這樣就得到了我們需要的結果。
代碼如下:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int p;
int num[505];
int res[505];
int len;
int ans;
void mult(){
int tmp[505];
memset(tmp,0,sizeof(tmp));
for(int i=0;i<500;i++){
for(int j=0;j<500&&(i+j)<500;j++){
tmp[i+j]+=num[i]*res[j];
}
}
for(int i=0;i<500;i++){
tmp[i+1]+=tmp[i]/10;
tmp[i]=tmp[i]%10;
num[i]=tmp[i];
}
}
void self(){
int tmp[505];
memset(tmp,0,sizeof(tmp));
for(int i=0;i<500;i++){
for(int j=0;j<500&&(i+j)<500;j++){
tmp[i+j]+=res[i]*res[j];
}
}
for(int i=0;i<500;i++){
tmp[i+1]+=tmp[i]/10;
tmp[i]=tmp[i]%10;
res[i]=tmp[i];
}
}
void fpow(){
while(p){
if(p%2==1){
mult();
}
self();
p>>=1;
}
}
int main(){
scanf("%d",&p);
memset(num,0,sizeof(num));
num[0]=1;
res[0]=2;
ans=(int)(p*log10(2)+1);
fpow();
num[0]-=1;
printf("%d\n",ans);
for(int i=499;i>=0;i--){
printf("%d",num[i]);
if((499-i+1)%50==0){
printf("\n");
}
}
return 0;
}