这根本挑不出错误,为什么是50分(TLE)

P1045 [NOIP2003 普及组] 麦森数

caojiaming @ 2023-08-23 12:50:59

#include <bits/stdc++.h>
using namespace std;
int n;
string ans="1";
int s[510]={};
string mul(string a)
{
    string res="";
    memset(s,0,sizeof(s));
    int k=a.size();
    int m=k;
    for(int i=1;i<=k;i++)
    {
        s[i]=a[m-1]-'0';
        m--;
    }
    for(int i=1;i<=k;i++)
    {
        s[i]*=2;
    }
    for(int i=1;i<=k+1;i++)
    {
        if(s[i]>=10)
        {
            s[i]-=10;
            s[i+1]++;
        }
    }
    for(int i=500;i>=1;i--)
    {
        char p=s[i]+'0';
        res=res+p;
    }
    return res;
}
int main()
{
    cin>>n;
    cout<<(int)(log10(2)*n+1)<<"\n";
    for(int i=1;i<=n;i++)
    {
        ans=mul(ans);
    }
    int t=ans[499]-'0'-1;
    ans[499]=(char)(t+'0');
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<50;j++)
        {
            cout<<ans[i*50+j];
        }
        cout<<"\n";
    }
    return 0;
}

我这复杂度应该是O(500n),吸氧应该能卡过


by Bingxiu @ 2023-08-23 12:58:39

@caojiaming 这题应该得快速幂吧,15.5e8你确定卡的过()


by lujunxuan123 @ 2023-08-23 13:01:00

@caojiaming n最大约933192,且你的mul常数比较大,吸氧能卡过去才怪


by Bingxiu @ 2023-08-23 13:03:19

@lujunxuan123 不,n 明明是 3021377()


by caojiaming @ 2023-08-23 13:05:37

@Bingxiu 高精度么,写不写快速幂有啥区别?


by lujunxuan123 @ 2023-08-23 13:05:41

@Bingxiu 哦,我看错了,我把n想成位数了


by lujunxuan123 @ 2023-08-23 13:06:19

那更不可能卡过去了


by lujunxuan123 @ 2023-08-23 13:07:33

@caojiaming 这确实要快速幂


by Bingxiu @ 2023-08-23 13:10:03

@caojiaming 咋会没区别呢


by caojiaming @ 2023-08-23 13:10:31

@lujunxuan123 写快速幂还要高精乘高精的代码,这太复杂了,还不知道这每次要算250000次的乘法能不能过


by lujunxuan123 @ 2023-08-23 13:12:21

@caojiaming 那你就TLE呗,嫌麻烦打什么代码?


| 下一页