题解 P1045 【麦森数】

· · 题解

裸的高精度题

1求位数:直接套用数学公式log10(2)乘上n就好了（c++中有log10函数）

2求后五百位：如果直接模拟高精度肯定会超时，所以要优化看见。其他人都是快速幂，这里提供一种时间较慢，但容易实现的方法：

对于2^n，可以分解成（2^x）^(n/x)，这是本解题思路的核心，这样就不用运算n次，而是n/x次，只要2^x在范围内，就可以实现优化，可以通过本题。

不过要注意，因为c++中除法运算会自动向下取整（整型），所以还要多乘上一个2^(n%x)

最后，再把最后一位减一就可以了

代码如下：

    #include<iostream>
    #include<cmath>
    #define x 50
    using namespace std;
    long long n,f[502],Pow[x+1],tmp;
    double count;
    void output()
    {
        count=log10(2)*n;//数学公式 
        while(count>1)
        {
            tmp++;
            count--;
        }
        if(count) tmp++;//不是整数则向上取整 
        cout<<tmp<<endl;
        for(int i=500;i>=1;i--)
        {
            cout<<f[i];
            if(i%50==1) cout<<endl;
        }
        return ;
    }
    int main()
    {
        Pow[0]=1;
        for(int i=1;i<=x;i++)
          Pow[i]=Pow[i-1]*2;//Pow[i]:2的i次方 
        cin>>n;
        f[1]++;
        for(int i=1;i<=n/x;i++)
        {
            for(int j=1;j<=500;j++)
              f[j]*=Pow[x];
            for(int j=1;j<=500;j++)
              if(f[j]>=10)
              {
                    f[j+1]+=f[j]/10;
                    f[j]%=10;
              }
            f[501]=0;

}//高精度主体

        for(int i=1;i<=x-1;i++)
          if(n%x==i)
          {
              for(int j=1;j<=500;j++)
                f[j]*=Pow[i];
              for(int j=1;j<=500;j++)
                if(f[j]>=10)
                {
                      f[j+1]+=f[j]/10;
                      f[j]%=10;
                }
              f[501]=0;

}//乘上2的n%x次方 f[1]--;

    output();

    return 0;

}