题解：P1045 [NOIP 2003 普及组] 麦森数

Imerance1018 · 2025-06-23 23:21:10 · 题解

提供封装结构体的高精快速幂板子。

Solution

第一问求的是 \lceil\log_{10}{(2^p-1)}\rceil=\lceil p \log_{10}{2}\rceil，直接输出。

对于第二问，我们使用快速幂。需要实现 500 位的高精乘高精，过程中保留后 500 位即可。

重点在代码。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;

struct Bignum   //养成好习惯
{
    int val[N],len;
    void init()
    {
        memset(val,0,sizeof(val));
        len=0;
    }
    Bignum operator *(const Bignum &x)const
    {
        Bignum res;
        res.init();
        res.len=min(len+x.len,500ll);
        for(int i=0;i<len;i++)
            for(int j=0;j<x.len&&i+j<500;j++)
                res.val[i+j]+=val[i]*x.val[j];
        for(int i=0;i<res.len;i++)
        {
            if(res.val[i]>=10)
            {
                res.val[i+1]+=res.val[i]/10;
                res.val[i]%=10;
            }
        }
        while(res.val[res.len]&&res.len+1<500)
        {
            if(res.val[res.len]>=10)
            {
                res.val[res.len+1]+=res.val[res.len]/10;
                res.val[res.len]%=10;
            }
            res.len++;
        }
        res.val[res.len]=0;
        return res;
    }
    void print()
    {
        val[0]--;     //末位显然不可能是 0，减 1 即可
        for(int i=499;i>=0;i--)
        {
            cout<<val[i];
            if(i%50==0)cout<<"\n";
        }
    }
};

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int p;
    cin>>p;
    cout<<ceil(p*log10(2))<<"\n";
    Bignum ji,base;
    ji.len=base.len=1;
    ji.val[0]=1,base.val[0]=2;
    while(p)
    {
        if(p&1)ji=ji*base;
        base=base*base;
        p>>=1;
    }
    ji.print();
    return 0;
}