问一下我用了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 卷王 @ 2022-07-26 15:03:16

@v7fgg

@JustinXiaoJunyang

感谢你们回答https://www.luogu.com.cn/discuss/445558中我的问题,现在我超时了,请问怎么办?


by Alex_wcq @ 2022-07-26 15:07:09

@holdyhao_Genius 写快速幂


by 喵仔牛奶 @ 2022-07-26 15:14:57

写快速幂,您算算时间复杂度。


by 卷王 @ 2022-07-26 15:16:00

@Alex_wcq 本人实力太差,不太会,问过别人后得知可以写Bigint,而且时间很快,请问您知不知道我的代码能不能缩短循坏的次数(我觉得这是突破口)。


by 卷王 @ 2022-07-26 15:20:32

@喵仔牛奶 我是C党……谁能看出我是java党的啊!!!我查看了他们的提交记录,都是C党,他们的代码应该也是C++/C吧……


by 卷王 @ 2022-07-26 15:24:45

@喵仔牛奶 真的???????????

我在深基里学的……


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

@holdyhao_Genius 写快速幂吧,要不用Python/Haskell


by hy233 @ 2022-07-26 15:35:52

@holdyhao_Genius 如果不想写快速幂的话,建议使用FFT/NTT优化乘法捏


by 卷王 @ 2022-07-26 15:39:16

@hy233 我不会!!【理直气壮】QWQ


by 卷王 @ 2022-07-26 15:39:50

不过还是关注一下您吧……


| 下一页