压位高精求麦森数

king_xbz · 2019-12-27 16:27:57 · 题解

在分治问题中麦森数是一个非常典型的高精度问题，

于是我就写了一个基础的高精

inline void myson() 
{
    a[500]=1;
    //初始进位 
    for(fint i=1;i<=n;i++)
    {
        for(fint j=500;j>=1;j--)
        a[j]*=2;
        //算每位*2 
        for(fint j=500;j>=1;j--)
        {
        a[j-1]+=a[j]/10;
        a[j]%=10;
        //进位
    }
    }
    a[500]--;
    //注意减一位，不然连暴力分也拿不到了 
}

提交，拿了60分。

不解，看题解，发现大多数神牛都在用快速幂。偶然的，我发现竟然可以用一次处理多次的方式来压时间

于是：

inline void mysons()
{
    a[500]=1;
    //初始化进位 
    int x=pow(2,60);
    //每次乘2的60次方 
    for(fint i=1;i<=n;i+=60)
    {
        for(fint j=500;j>=1;j--)
        {
        if(n-i+1<60)
        a[j]*=pow(2,n-i+1);
        //注意当剩余不足60位时乘上2的剩余次方位 
        else
        a[j]*=x;
        //否则直接乘2的60次方 
    }
    for(fint j=500;j>=1;j--)
        {
        a[j-1]+=a[j]/10;
        a[j]%=10;
    }
    //处理进位 
}
a[500]--;
//a[500]初始为1，此时应该减去 
}

提交，ac！

完整注释代码

code：

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define fread ios::sync_with_stdio
#define int unsigned long long
#define fint register long long
#define p 14732334
#define h 501
//头文件，宏定义及加速 

using namespace std;
int a[h];
int n;

inline void myson();
inline void prints();
inline void mysons();

signed main()
{
    fread(false);
    //流读入优化 
    cin>>n;
    cout<<floor(log10(2)*n+1)<<endl;
    //根据2^p-1的位数=2^p的位数可推出位数是log10^2*n+1向下取整（数学方法） 
    mysons();
    //调用函数求麦森数 
    prints();
    //输出 
    exit(0);
    //结束 
}
暴力高精度（60分） ： 
inline void myson() 
{
    a[500]=1;
    //初始进位 
    for(fint i=1;i<=n;i++)
    {
        for(fint j=500;j>=1;j--)
        a[j]*=2;
        //算每位*2 
        for(fint j=500;j>=1;j--)
        {
        a[j-1]+=a[j]/10;
        a[j]%=10;
        //进位
    }
    }
    a[500]--;
    //注意减一位，不然连暴力分也拿不到了 
}
inline void prints()
{
    for(fint i=1;i<=500;i++)
    {
        cout<<a[i];
        //输出 
        if(i%50==0)
        cout<<endl;
        //每50位换行 
    }
}
压位做法（100分）： 
inline void mysons()
{
    a[500]=1;
    //初始化进位 
    int x=pow(2,60);
    //每次乘2的60次方 
    for(fint i=1;i<=n;i+=60)
    {
        for(fint j=500;j>=1;j--)
        {
        if(n-i+1<60)
        a[j]*=pow(2,n-i+1);
        //注意当剩余不足60位时乘上2的剩余次方位 
        else
        a[j]*=x;
        //否则直接乘2的60次方 
    }
    for(fint j=500;j>=1;j--)
        {
        a[j-1]+=a[j]/10;
        a[j]%=10;
    }
    //处理进位 
}
a[500]--;
//a[500]初始为1，此时应该减去 
}

祝大家ac