样例通过但是0pts(WA+TLE)求助 算法：简单高精度

P1045 [NOIP2003 普及组] 麦森数

zhangmingsheng3521 @ 2023-07-25 22:31:26

rt，代码如下，求大佬找错

#include"bits/stdc++.h"
using namespace std;
int main()
{
    bool flag=false;
    int ans=0;
    int p;
    int gaojing[502];
    memset(gaojing,0,sizeof(gaojing));
    scanf("%d",&p); 
    gaojing[1]=1;
    for (int i=1;i<=p;i++)
    {
        for (int j=1;j<=500;j++)
        {
            gaojing[j]=gaojing[j]*2;
        }
        for (int j=1;j<=499;j++)
        {
            if (gaojing[j]>9)
            {
                gaojing[j+1]+=gaojing[j]/10;
                gaojing[j]=gaojing[j]%10;
            }
        }
    }
    gaojing[1]--;
    for (int i=500;i>=1;i--)
    {
        if (gaojing[i]!=0)
        {
            flag=true;
        }
        if (flag)
        {
            ans++;
        }
    }
    printf("%d",ans);
    printf("\r\n");
    for (int i=500;i>=1;i--)
    {
        printf("%d",gaojing[i]);
    }
    return 0;
}

by 15167987933yy @ 2023-08-02 14:10:05

我是这样做的，你和我的方法对比一下

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int f[1001],p,res[1001],sav[1001];
void result_1(){
    memset(sav,0,sizeof(sav));
    for(register int i=1;i<=500;i+=1)
        for(register int j=1;j<=500;j+=1)
            sav[i+j-1]+=res[i]*f[j];
    for(register int i=1;i<=500;i+=1){
        sav[i+1]+=sav[i]/10;
        sav[i]%=10;
    }
    memcpy(res,sav,sizeof(res));
}
void result_2(){
    memset(sav,0,sizeof(sav));
    for(register int i=1;i<=500;i+=1)
        for(register int j=1;j<=500;j+=1)
            sav[i+j-1]+=f[i]*f[j];
    for(register int i=1;i<=500;i+=1){
        sav[i+1]+=sav[i]/10;
        sav[i]%=10;
    }
    memcpy(f,sav,sizeof(f));
}
int main(){
    scanf("%d",&p);
    printf("%d\n",(int)(log10(2)*p+1));
    res[1]=1;
    f[1]=2;
    while(p!=0){
        if(p%2==1)result_1();
        p/=2;
        result_2();
    }
    res[1]-=1;
    for(register int i=500;i>=1;i-=1)
        if(i!=500&&i%50==0)printf("\n%d",res[i]);
        else printf("%d",res[i]);
    return 0;
}

by wanglexi @ 2023-09-06 19:53:49

关于\textcolor{red}{WA}

啊题目说了：

所以呢，我们要

于是输出部分变成了

    for (int i=500;i>=1;i--)
    {
        printf("%d",gaojing[i]);
        if(i%10==0)printf("\n");//换行
    }

然后

\textcolor{red}{0 \to 20 }

关于大数据

我们输入2000，得到了：

500
-19483298084596463898746277344711896086305533142593135616665
.....[后略]

答：1.后面疯狂向前面进位，前面炸了！2.而且，超过500位的部分就不知道前面有几位了！3.\textcolor{brown}{TLE}：总共乘310000次，每次乘500次，很容易就TLE！

  1. 让gaojing[500]也向gaojing[501]进位就行了

  2. 换底公式：

    \log_b(N)=\frac{\log_a(N)}{\log_a(b)}
3. 快速幂即可 后面我也真的不会了，~~还是看题解吧~~

by wanglexi @ 2023-09-06 19:54:45

@wanglexi 呃.....Markdown怎么坏了？？

by wanglexi @ 2023-09-06 19:55:27

@wanglexi 没办法，在编辑区看都是好的

by wanglexi @ 2023-09-06 19:59:23

好吧，我确实挺蒟蒻的

|