问一下我用了Bigint,但是超时4个点(这上面已经有两个我问的问题了…… )

P1045 [NOIP2003 普及组] 麦森数

卷王 @ 2022-07-26 15:01:40

我不想用快速幂,于是用了Bigint,结果T了4个点,不知道咋搞。。。

#include<bits/stdc++.h> //60分代码
using namespace std;
struct Bigint
{
    int f[1000],len;
    Bigint(int x=0)
    {
        memset(f,0,sizeof(f));
        for(len=1;x;len++)
            f[len]=x%10,x/=10;
        len--;
    }
    void flatten(int L)
    {
        len=L;
        for(int i=1;i<=500;i++)
        {
            f[i+1]+=f[i]/10;
            f[i]%=10;
        }
        for(;!f[len];) len--;
        len=min(len,500);
    }
    void print()
    {
        for(int i=max(len,1);i>=1;i--) cout<<f[i];
    }
};
Bigint operator*(Bigint a,int b)
{
    Bigint c;
    int mlen=a.len;
    for(int i=1;i<=500;i++)
        c.f[i]=a.f[i]*b;
    c.flatten(mlen+11);
    return c;
}
int p; Bigint ans(1);
int main() {
    cin>>p;
    cout<<int(log10(2)*p+1)<<endl;
    for(int i=1;i<=p;i++) ans=ans*2;
    ans.f[1]--;
    ans.len=500;
    for(int i=500;i>=1;i--) {
        cout<<ans.f[i];
        if(i!=500&&i%50==1) cout<<endl;
    }
    return 0;
}

by hy233 @ 2022-07-26 15:41:29

@holdyhao_Genius 你不写快速幂复杂度是O(500p)的,直接T飞啊


by hy233 @ 2022-07-26 15:42:05

@hy233 快速幂不是背个板子的事情(当然理解也很重要啊


by 卷王 @ 2022-07-26 15:43:34

嗯……我再学习学习可能就行了。。

感谢dalao


by 喵仔牛奶 @ 2022-07-26 15:48:18

@holdyhao_Genius 不写FFT/NTT/快速幂写裸压位高精也能过。


by 卷王 @ 2022-07-26 16:27:42

OK,我试试


上一页 |