P1045 麦森数 题解

传送门

前排提醒：本篇题解没有使用压位和快速幂，运用了一种预处理的思想，希望能提供一种新的思路。

首先将 \(2^{p}-1(d)\) 转换为 \(1111…111(b)\)。

关于第一问：

我们先考虑 \(2\) 进制转 \(8\) 进制，将每 \(3\) 位转为 \(1\) 位，即每 \(\log{8}\) 位转为 \(1\) 位。

\(2\) 进制转 \(10\) 进制同理，将每 \(\log{10}\) 位转为 \(1\) 位，位数就是 \(\lceil \frac{p}{\log{10}} \rceil\)。

关于第二问：

考虑用高精度存储后 \(500\) 位，暴力乘上 \(p\) 个 \(2\)，时间复杂度 \(\mathcal{O}(500 \times P)\)，无法通过此题。

考虑优化暴力乘的过程，将几个 \(2\) 合并起来，乘上若干次 \(2^{k}\)，使得 \(\sum k=p\) ，用 long long 存储每一位，那么每一位最多可以放 \(2^{63}-1\)。由于每一位 \(\in [0,9] \approx[0,2^4)\)，所以每次最多可以乘上 \(2^{59}\)。

预处理 \(2^{59}\) 的值，将乘上 \(p\) 个 \(2\) 转换为乘上 \(\lfloor \frac{p}{59} \rfloor\) 个 \(2^{59}\) 和 \(p\mod{59}\) 个 \(2\)，时间复杂度 \(\mathcal{O}(500 \times \lfloor \frac{p}{59} \rfloor)\)。

\(\mathcal{Code}\)：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define int ll
#define F(i,a,b) for(re int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(re int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(re int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
int p;
int str[510],mi[60];
signed main()
{
	p=read();
	mi[0]=1;
	F(i,1,59) mi[i]=mi[i-1]*2;
	str[500]=1;
	F(i,1,p/59)
	{
		DF(k,500,1)
		{
			str[k]*=mi[59];
			str[k]+=str[k+1]/10;
			str[k+1]%=10;
		}
		str[1]%=10;
	}
	F(i,1,p%59)
	{
		DF(k,500,1)
		{
			str[k]<<=1;
			str[k]+=str[k+1]/10;
			str[k+1]%=10;
		}
		str[1]%=10;
	}
	str[500]--;
	printf("%d\n",(int)(ceil(p/log2(10))));
	F(t,1,10)
	{
		F(k,1,50) printf("%d",str[(t-1)*50+k]);
		putchar('\n');
	}
	return 0;
}