• P1045 [NOIP2003 普及組] 麥森數(shù)

解析

看似只是正常的一個(gè)高精
然而

暗藏殺機(jī)

一開(kāi)始隨手那么一寫(xiě)
。。。
(即使用了快速冪)時(shí)間復(fù)雜度過(guò)于感人
后來(lái)我們發(fā)現(xiàn)：
第一問(wèn)位數(shù)的計(jì)算不必真的算出來(lái)，只需把2的p次冪轉(zhuǎn)化為10的k次冪即可（具體請(qǐng)參看高中數(shù)學(xué)必修1）

(為了大家，我還是敲一下吧。。）
2^p=10的log10(2^p)次方=10^p*log10(2)
k應(yīng)該等于p*log10（2）

我們就可以使用log10() 函數(shù)水掉第一問(wèn)
至于第二問(wèn)，既然只問(wèn)后500位，就可以暴力刨掉后面了~~~
（慷慨的我們又送了十位，不客氣）
PS：別忘了50位一換行（別問(wèn)我為啥要強(qiáng)調(diào)這個(gè)。。。）

代碼

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<string> #include<climits> using namespace std; int p,ans[3100002],res[3100002]; double r=log10(2); int *a=&ans[1],*b=&res[1]; void cheng(int *x,int *y){int l1=*(x-1);int l2=*(y-1);int f[31002]={ };for(int i=1;i<=l1;i++){for(int j=1;j<=l2;j++){f[i+j-1] += *(x+i-1) * *(y+j-1);}}f[0]=l1+l2+5;for(int i=1;i<=f[0];i++){f[i+1]+=f[i]/10;f[i]%=10;}while(f[f[0]]==0) f[0]--;f[0]=min(f[0],510);for(int i=0;i<=f[0];i++){*(x+i-1)=f[i];} } void ksm(int n){while(n){if(n%2==1) cheng(a,b);cheng(b,b);n /= 2;} } int main(){ans[0]=res[0]=ans[1]=1;res[1]=2;scanf("%d",&p);ksm(p);int as=floor(p*r)+1;printf("%d",as);ans[1]--;int place=1;while(ans[place]<0){ans[place]+=10;ans[place+1]--;place++;}for(int i=500;i>=1;i--){if((500-i)%50==0) printf("\n");printf("%d",ans[i]);}return 0; }

AC快樂(lè)！

總結(jié)

以上是生活随笔為你收集整理的高精度：麦森数*（洛谷P1045）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。