以用高精度,但是不知道输出都是0,求助大佬,帮我看看哪一步错了

P1045 [NOIP2003 普及组] 麦森数

456laji @ 2020-05-07 13:03:18

代码丑陋,见谅。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=500;
const int N=909526; 
int num[N],len=0,p,n;

inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int a[N],b[N],c[N];

int s(int *temp,int lent)
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b)); 
    memset(c,0,sizeof(c)); 
    for(int i=0;i<=lent;i++)
        a[i]=temp[i],b[i]=temp[i];
    int up=0;
    for(int j=0;j<=lent;j++)
    {
        up=0;
        for(int i=0;i<=lent;i++)
        {
            c[i+j]+=a[i]*b[j]+up;//printf("%d %d %d\n",a[i],b[j],c[i+j]);
            up=c[i+j]/10;
            c[i+j]%=10;
        }
        c[lent+j]=up;
    }
    int lenc=lent*2;
    while(lenc>0&&c[lenc]==0)
        lenc--;//printf("lenc=%d\n",lenc);
     for(int i = lenc; i >=0 ; i--) // 逆序输出
        cout << c[i];cout<<endl;
    len=lenc;
    return *c;
}

int ksm(int k)
{
    if(k*2>n) return 0;//printf("k=%d  len=%d\n",k,len);
    *num=s(num,len);
    /*for(int i = len; i >=0 ; i--) // 逆序输出
        cout << num[i];cout<<endl;*/
    p=pow(2,k);
    ksm(p);
}

int main()
{
    ll res,j=0,a=0;
    num[0]=2;
    n=read();
    ksm(1);
    printf("%d\n",len);
    if(len-1<500)
    {
        a=500-len;
        for(int i=0;i<a;i++)
        {
            j++;
            printf("0");
            if(j==50) j=0,printf("\n");
        }
    }
    j--;
    if(len>500) a=len-500;
    else a=0;
    for(int i=0;i<len;i++)
    {
        if(num[0]>=1)
        {
            num[0]-=1;
            break;
        }
        else
        {
            if(num[i]>=i)
            {
                for(int y=i-1;y>=0;y--)
                    num[y]+=1;
                num[0]-=1;
                break;
            }   
        }

    }
    for(int i=len-1;i>=a;i--)
    {
        j++;
        printf("%d",num[i]);
        if(j==50) j=0,printf("\n");
    }   
    return 0;
} 

by 456laji @ 2020-05-07 13:08:55

我的思路是:

2*2=4

4*4=16

16*16=256 .........

就是这样逐渐逼近n


by Steven__Chen @ 2020-05-07 13:30:14

@456laji 好想法,为什么不试试以此为基础的快速幂呢


by OvOAuto @ 2020-05-07 13:32:08

看了一下题面我怎么想到了打表


by OvOAuto @ 2020-05-07 13:32:38

不过你的解法挺妙


by 闪电皮卡丘 @ 2020-05-07 13:34:13

@456laji int num[n]是不是爆掉了(全开longlong)


by critnos @ 2020-05-07 14:11:27

其实这个解法似乎下界 \log n 上界 n


by Na2PtCl6 @ 2020-05-07 14:13:48

@Steven__Chen TA用了快速幂啊,那么大的ksm你没看见?人家只是用递归写的


by Na2PtCl6 @ 2020-05-07 14:15:31

@456laji 你的p爆了


by Na2PtCl6 @ 2020-05-07 14:16:52

这里

p=pow(2,k);

p会超过整型


by 456laji @ 2020-05-11 08:49:19

@DarwinLuo 谢谢,原来是这里,太感谢大佬了。


| 下一页