题解 P1045 【麦森数】

sqrt_7 · 2019-10-15 21:32:57 · 题解

不用快速幂的短代码！！

这题全是用快速幂的，其实可以不用，310万乘500等于15亿，常数好能过。题解里有一篇不用快速幂压位的解法，但是代码长得要死。所以，以下是30行以内的代码：（150ms以内）
首先，我们要计算位数。我们知道10^k有k+1位，而k=lg(10^k)。所以2^p的位数是lg(2^p)+1=p*lg(2)。那么把p读进来之后直接cout出位数就行了。
下面解决500位求值的问题：这里还是开一个a[501]的unsigned long long数组，记为ull，然后还是用每个元素表示1位数，没错，是1位数，这样时间够而且代码简单。每次乘一轮不要乘2，乘2^60（9乘以2的60次方刚好不会溢出），记得把p多减掉59就行了。然后你发现15亿除以60等于2500万，貌似可以...自己机器上只用了半秒。
代码：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
ull a[501]={1};
int main()
{
    int p;
    cin>>p;
    cout<<(int)(p*log10(2))+1<<endl;//log10才是以十为底的对数
    for(;p>0;p-=60)//每次减掉60次幂
    {
        ull f=0;//进位
        for(int i=0;i<500;i++)
        {
            if(p>60)a[i]<<=60;
            else a[i]<<=p;//如果剩下的不够60了就不要乘60了，乘p
            a[i]+=f;
            f=a[i]/10;
            a[i]%=10;
        }
    }
    a[0]-=1;//千万不要忘记减1，否则你会和我第一次一样WA掉全部
    for(int i=499;i>=0;i--)
    {
        putchar(a[i]+'0');
        if(i%50==0)putchar('\n');
    }
    return 0;
}