P1045 麦森数
P1045 [NOIP2003 普及组] 麦森数
P1045 麦森数
输入n,求出 2 p − 1 2^p-1 2p−1 位数和500个尾数
思路
运用对数转换， n ∗ ( l o g 10 ( 2 ) ) + 1 n*(log10(2))+1 n∗(log10(2))+1 即位数。
只需要保留后500，可以用一个数组，不断更新。初始化数组 a [ 0 ] = 1 , 其余为 0 a[0]=1,其余为0 a[0]=1,其余为0.
2 很特殊，可以直接用 <<
- 左移P,数据溢出
- 每次移动小，时间复杂度高
所以，每次移动10位，可以避免这个问题（换成其他也可以）
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int a[550]={1};
signed main()
{
IOS
int n;
cin>>n;
int p=n*(log10(2))+1;
cout<<p<<'\n';
for(;n>0;n-=10)
{ int f=0;
int h=min(n,(long long)10);
for(int i=0;i<=499;i++)
{
a[i]<<=h;
a[i]+=f;
f=a[i]/10;
a[i]%=10;
}
}
a[0]-=1;
for(int i=1;i<=10;i++)
{
for(int j=549-50*i;j>499-50*i;j--)
{
cout<<a[j];
}cout<<'\n';
}
}