P1045 麦森数

- 日理万妓 2021-10-29 09:16 175阅读 0赞

这道题纯粹是考数学。编程复杂度不大（别看我写了一百多行其实有些是可以不必写的）。

计算位数不必用高精时刻存，不然可想而知时间复杂度之大。首先大家要知道一个数学公式 logn(a\*b)=logn(a)+logn(b)至于证明翻数学书吧。而且，用log10(n)+1即可求出n的位数。则2^p的位数=log10(2^p)+1=p\*log10(2)+1。这样，我们算的时候就不必随时存着位数了。

但是，如果直接写高精和n次循环，时间复杂度依旧很高。所以我们就要用快速幂。幂的运算是初中内容，几个公式如下:n^a\*n^b=n^(a+b)，(n^a)^b=n^(a\*b)。

所以，我们就可以将乘方的复杂度优化成O(logn)了。

代码：

\#include<bits/stdc++.h>  
using namespace std;

struct Hint \{  
static const int MAX=4000;  
short a\[MAX+1\];  
int Len;  
Hint() \{  
memset(a,0,sizeof(a));  
Len=1;  
\}

Hint operator=(std::string N) \{  
memset(a,0,sizeof(a));  
if(N\[0\]=='-') \{  
Len=N.size()-1;  
a\[0\]=1;  
for(int i=1; i<=Len; ++i)  
a\[i\]=N\[Len-i+1\]-'0';  
return \*this;  
\}  
if(N\[0\]=='+') \{  
Len=N.size()-1;  
a\[0\]=0;  
for(int i=1; i<=Len; ++i)  
a\[i\]=N\[Len-i+1\]-'0';  
return \*this;  
\}  
Len=N.size();  
for(int i=1; i<=Len; ++i)  
a\[i\]=N\[Len-i\]-'0';  
return \*this;  
\}

Hint operator=(const int & b) \{  
char s\[MAX+1\];  
sprintf(s,"%d",b);  
\*this=s;  
return \*this;  
\}

Hint(std::string N) \{  
\*this=N;  
\}  
Hint(const int &b) \{  
\*this=b;  
\}

int read() \{  
char s\[MAX+1\];  
int t=scanf("%s",s);  
\*this=s;  
return t;  
\}

void write() \{  
int r,re=1,now=0;  
for(int i=Len; i>=1; --i) \{  
cout<<a\[i\];  
\++now;  
if(now%50==0)cout<<endl;  
\}  
\}  
Hint operator\*(Hint x) \{  
Hint c;  
c.Len=Len+x.Len;  
for(int i=1; i<=Len; ++i) \{  
for(int j=1; j<=x.Len; ++j) \{  
c.a\[i+j-1\]+=a\[i\]\*x.a\[j\];  
if(c.a\[i+j-1\]>=10) \{  
c.a\[i+j\]+=c.a\[i+j-1\]/10;  
c.a\[i+j-1\]%=10;  
\}  
\}  
\}  
c.Len=500;  
return c;  
\}

\}two,ans;

int p;

Hint quick\_power(int y)  
\{  
if(y==1)return two;  
if(y==0)return 1;  
Hint re;  
if(y%2==0)  
\{  
re=quick\_power(y/2);  
re=re\*re;  
\}  
else  
\{  
re=quick\_power(y/2);  
re=re\*re\*two;  
\}  
return re;  
\}

int main()  
\{  
two=2;  
cin>>p;  
cout<<(long long)(log10(2)\*p+1)<<endl;  
ans=quick\_power(p);  
ans.a\[1\]-=1;  
ans.write();  
return 0;  
\}

转载于:https://www.cnblogs.com/20020219-liu/p/11199814.html