AcWing 416. 麦森数
原题链接
简单
作者:
xiaoQ
,
2021-05-13 20:39:29
,
所有人可见
,
阅读 292
C++ 代码
/* 算法:快速幂加高精
这题可以分两个子问题来求,
首先求2^p-1的位数,因为2^p的最后一位只能为2,4,8,6均大于1,即2^p-1的位数
和2^p相同,所以只要求2^p的位数,那么要如何来求呢?
我们先来看个例子,假设有一个位数为p=3的数x,那么100<=x<999,
即10^(k-1)<=x<10^p-->k-1<=log10(x)<k,向下取整可得k-1=log10(x),
现在令x=2^p,k-1=log10(2^p)-->k=p*log10(2)+1
那么接下来只要求出2^p-1的最后500位数,即只要对最后500位数字进行计算,
又因时间复杂度的关系,这里就用快速幂来求,
先简单的介绍一下快速幂:这是一个用来求a^b的算法,
有数学知识可知,任何一个正整数可以唯一表示若干个指数不重复的2都次幂的和
所以b=2^t1+2^t2+...+2^tn,所以a^b=a^(2^t1+2^t2+...+2^tn)
也就得出a^b=a^(2^t1)*a^(2^t2)*...*a^(2^tn),
那么怎么才可以知道t1,t2...tn这些的值呢,只要化为二进制,
例如:10=(1010)--二进制,此时k=2^1+2^3,
*/
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N=510;
int a[N],c[N],res[N];
void mul(int a[],int b[],int res[])
{
memset(c,0,N*4); //初始化为0
for(int i=0;i<500;i++)
{
for(int j=0;j<500;j++)
{
if(i+j < 500)
c[i+j] += a[i]*b[j];
}
}
for(int i=0,t=0;i<500;i++)
{
t+=c[i];
res[i]=t%10;
t/=10;
}
}
void qmi(int p)
{
res[0]=1;
a[0]=2;
while(p)
{
if(p & 1) mul(a,res,res);
p >>= 1;
mul(a,a,a); //反复平方求a^(2^0),a^(2^1)...a^(2^tn)
}
res[0]--;
}
int main()
{
int p;
cin>>p;
cout << int(log10(2)*p)+1<<endl;
qmi(p);
for(int i=499,k=0;i>=0;i--)
{
if(k==50)
{
cout<<endl;
k=0;
}
cout<<res[i];
k++;
}
return 0;
}