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

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;
}

by Light_az @ 2023-08-23 13:14:52

@lujunxuan123 直接预处理 2^20 次方就好了吧

by talkwithcpp @ 2023-08-23 13:15:06

你函数加个inline试试，不行的话你把string换成char数组，string似乎比较慢

by talkwithcpp @ 2023-08-23 13:21:28

对了，我想起来了，你要一个一个乘的话一次要左移60位，剩余的再单独算。但这样的话会爆char,要换成unsigned long long。

by caojiaming @ 2023-08-24 09:16:40

#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;
}
string mul2(string a,string b)
{
    string res="";
    int s1[510],s2[510],s3[1024];
    int l1=a.size(),l2=b.size(),l3=l1+l2;
    for(int i=0;i<l1;i++)
    {
        s1[l1-i]=a[i]-'0';
    }
    for(int i=0;i<l2;i++)
    {
        s2[l2-i]=b[i]-'0';
    }
    for(int i=1;i<=l1;i++)
    {
        for(int j=1;j<=l2;j++)
        {
            s3[i+j-1]=s1[i]*s2[j];
        }
    }
    for(int i=1;i<=l3;i++)
    {
        int u=s3[i]/10;
        s3[i]%=10;
        s3[i+1]+=u;
    }
    l3=500;
    for(int i=1;i<=l3;i++)
    {
        char p=s3[i]+'0';
        res=p+res;
    }
    return res;
}
string qpow(int n)
{
    if(n==1) return "1";
    if(n%2)
    {
        string temp=qpow(n/2);
        return mul2(temp,temp);
    }
    else
    {
        return mul2("2",qpow(n-1));
    }
}
int main()
{
    cin>>n;
    cout<<(int)(log10(2)*n+1)<<"\n";
    ans=qpow(n);
    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;
}

我勉强写了个高精快速幂，0分全WA 求改错!

by caojiaming @ 2023-08-24 09:19:08

@Bingxiu

by caojiaming @ 2023-08-24 10:20:09

终于做对了，此帖终

by Bingxiu @ 2023-08-24 10:20:15

@caojiaming 把你的 \texttt{qpow} 函数中的 if(n%2) 改成 if(n%2==0)