2661:Factstone Benchmark - komiyamの日記

keyword

概要

k<20に対して、2^(2^k)>n!を満たす最大のnを求める問題。積の計算に時間がかかるため、Javaで多倍長使ってもTLEする。なので対数で処理する。精度とかあんまり気にしなくても通った。

int ans[21];

void solve(){
    double bit = 4*log(2), fact = 0.0;
    int p=0;
    for(int i=1;;i++){
        fact += log(i);
        if(fact > bit){
            bit *= 2;
            ans[p++] = i-1;
            if(p==21) return ;
        }
    }
}

int main(){
    solve();
    int n;
    while(n = readint(), n){
        printf("%d\n",ans[(n-1960)/10]);
    }
    return 0;
}