4个超时,求大佬指导优化~!

P1045 [NOIP2003 普及组] 麦森数

h·cei @ 2019-11-13 22:46:40


#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

void chengfa();

void print();

int p,i,a[505];

int main(){

    a[1]=1;
    cin>>p;
    for(int i=1;i<=p;++i)
        chengfa();
    a[1]-=1;
    print();
    return 0;
}
void print(){

    cout<<(int)(p*log(2)/log(10))+1<<endl;
    i=500;
    while(i){
        cout<<a[i--];
        if(i%50==0)
            cout<<endl; 
    }
}
void chengfa(){

    int x=0;
    for(i=1;i<=500;++i){
        a[i]=a[i]*2+x;
        x=a[i]/10;
        a[i]%=10;
    }
 }

by Lifeㅤgoesㅤon @ 2019-11-19 22:22:41

来了


by Lifeㅤgoesㅤon @ 2019-11-19 22:23:24

嗯……有很多优化


by Lifeㅤgoesㅤon @ 2019-11-19 22:24:23

第一个:你log可以自己打个表,log(2)_10=0.30102999566398。


by Lifeㅤgoesㅤon @ 2019-11-19 22:24:37

@aresword 这样可以加快


by Lifeㅤgoesㅤon @ 2019-11-19 22:24:46

@h·cei @一下


by Lifeㅤgoesㅤon @ 2019-11-19 22:26:34

第二个:你可以把*2改成(<<1),第三个我估计你可能不太会改。那就是一次多乘几下,比如说你一次乘以2的24次方,这样就会快很多很多


by Lifeㅤgoesㅤon @ 2019-11-19 22:26:59

第四个你可以加个快速幂,考虑一下?


by h·cei @ 2019-11-19 22:30:39

嗯!会了,谢谢!


|