如何优化?

P1045 [NOIP2003 普及组] 麦森数

蒟蒻lxy @ 2019-08-20 23:49:08

RT,指令集和putchar都用上了。。。

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int a[1005],la;
    node()
    {
        memset(a,0,sizeof(a));
        la=1;
    };
    void init()
    {
        string s;
        cin >> s;
        la=s.size();
        for(int i=la,j=0;i>=1;i--,j++)
            a[i]=s[j]-'0';
    };
    void print()
    {
        //cout << la << endl;
        int lla=500;
        for(int i=10;i>=1;i--)
        {
            for(int k=1;k<=50;k++)
                if(i>la)
                    putchar('0'),lla--;
                else
                    printf("%d",a[lla]),lla--;
            putchar('\n');
        }
        putchar('\n');
    };
    void clean()
    {
        la=1;
        memset(a,0,sizeof(a));
    };
    bool operator<(const node TAT) const
    {
        if(la!=TAT.la)
            return la<TAT.la;
        else
        {
            for(int i=la;i>=1;i--)
                if(a[i]!=TAT.a[i])
                    return a[i]<TAT.a[i];
            return 0;
        }
    };
    bool operator>(const node TAT) const
    {
        return TAT<*this;
    };
    bool operator==(const node TAT) const
    {
        if(!(*this<TAT) && !(*this>TAT))
            return 1;
        else
            return 0;
    };
    bool operator<=(const node TAT) const
    {
        if(*this<TAT || *this==TAT)
            return 1;
        else
            return 0;
    };
    bool operator>=(const node TAT) const
    {
        if(*this>TAT || *this==TAT)
            return 1;
        else
            return 0;
    };
    node operator-(const node TAT) const
    {
        node b,a2;
        a2=*this;
        memset(b.a,0,sizeof(b.a));
        b.la=max(la,TAT.la);
        for(int i=1;i<=la;i++)
        {
            if(a[i]<TAT.a[i])
            {
                a2.a[i+1]--;
                a2.a[i]+=10;
            }
            b.a[i]=a2.a[i]-TAT.a[i];
        }
        while(b.a[la]==0 && b.la>1)
            b.la--;
        return b;
    };
    node operator*(const node TAT) const
    {
        node b;
        memset(b.a,0,sizeof(b.a));
        b.la=la+TAT.la;
        if(b.la>500)
            b.la=500;
        for(int i=1;i<la+TAT.la && i<=500;i++)
        {
            int x=0;
            for(int j=1;j<=TAT.la && j<=500;j++)
            {
                if(i+j-1>500)
                    break;
                b.a[i+j-1]+=a[i]*TAT.a[j]+x;
                x=b.a[i+j-1]/10;
                b.a[i+j-1]%=10;
            }
            if(i+TAT.la<=500) 
                b.a[i+TAT.la]=x;
        }
        while(b.a[b.la]==0 && b.la>1)
            b.la--;
        return b;
    };
    node operator+=(const node TAT)
    {
        *this=*this+TAT;
        return *this;
    };
    node operator-=(const node TAT)
    {
        *this=*this-TAT;
        return *this;
    };
    node operator*=(const node TAT)
    {
        *this=*this*TAT;
        return *this;
    };
}yi,er;
int x;
int wei(int x)
{
    return ceil(x*1.0*log10(2));
}
/*node ksm(int x)//这里错了 
{
    node re,er;
    re.a[1]=1,er.a[1]=2;
    while(x)
    {
        if(x%2!=0)
            re*=er;
        re*=re;
        x/=2;
        cout << x <<' ';
    }
    return re;
}*/
node ksm(int x)//新,正确 
{
    return x==1?er:x%2==0?ksm(x/2)*ksm(x/2):ksm(x/2)*ksm(x/2)*er;
}
int main()
{
    scanf("%d",&x);
    printf("%d\n",wei(x));
    //jisuan(x);
    yi.a[1]=1;
    er.a[1]=2;
    (ksm(x)-yi).print();
    return 0;
}
//1279

by Jelly_Goat @ 2019-08-20 23:51:51

您这是怎么了


by 蒟蒻lxy @ 2019-08-21 00:02:16

我这是自闭了


by 蒟蒻lxy @ 2019-08-21 00:05:14

(;´༎ຶД༎ຶ`)


by 蒟蒻lxy @ 2019-08-21 00:06:59

好像输入3021377时会卡住??


by su226 @ 2019-08-21 00:14:37

正解python(雾)

理论上java也水得过去,但是我提交java就re


by _H1kar1 @ 2019-08-21 01:21:16

那你不如把算法改进一下


by tgs9311 @ 2019-08-21 07:53:23

?暴力出奇迹?


by 蒟蒻lxy @ 2019-08-21 11:14:29

萌新刚学高精度应该是ksm()的问题,有大佬帮忙一下吗?


by theaceblock @ 2019-08-26 10:30:40

re*=re;

这里挂掉了

er*=er; //这样就对了

这个码风很容易写挂好不好

node QuickPower(int x)
{
    node result, current;
    result.a[1]= 1;
    current.a[1]= 2;

    while (x)
    {
        if (x&1)
        {
            result*=current;
        }

        current*= current;
        x>>= 1;
    }

    return result;
}

还有前面那一堆没太大用


by theaceblock @ 2019-08-26 10:38:58

来看我的


|