POJ 2661 : Factstone Benchmark

問題リンク:2661 -- Factstone Benchmark

問題概要：
とある会社が1960年に4-bitコンピュータをリリースした
1970年には8-bit,1980年には16-bit,....
といった感じで、10年毎にbit数が2倍になっていく
ある年y( 1960 <= y <= 2160 ) が与えられるので、
その年のコンピュータがunsigned intで表現できるn!のnを求めよ

解法：
2^y >= n! となるような最大のnを求めたい
log2(n!) <= y と変形する
log2(a*b) = log2(a) + log2(b)なので
log2(1) + log2(2) + log2(3) + ....としていってyを越えたときの値-1が答えとなる

コード:

#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

int main(){
  int year[21], bit[21];
  year[0] = 1960, bit[0] = 4;
  REP(i,1,21) {
    year[i] = year[i-1] + 10;
    bit[i] = bit[i-1] * 2;
  }
  int y;
  while( scanf("%d",&y), y ){
    int pos = lower_bound(year,year+20,y) - year;
    if( year[pos] > y ) pos--;
    double limit = bit[pos];
    int n = 0;
    double logn = 0;
    while( !equals(logn,limit) && logn < limit ){
      n++;
      logn += log2(n);
    }
    cout << n-1 << endl;
  }
  return 0;
}