UVa 13036 : Birthday Gift to SJ - 2

問題リンク :
https://uva.onlinejudge.org/external/130/13036.pdf

問題概要 :
フィボナッチ数の積として表されるような数で、a以上b以下のものの最大値を求めよ

解法 :
laycrsさんの解説を読んで解いた
フィボナッチ数のうち2から89までを前半、それ以降を後半として列挙する
前半のフィボナッチ数を入れた配列をX、後半のフィボナッチ数を入れた配列をYとする
Xの各要素について、b/X[i]となるようなYの最大値を求める

これでも結構時間がかかるので、
素因数分解した時に、全て他のフィボナッチ数で表されるようなものは配列から除外した(8と144だけかな

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll MAX = 1000000000000000000LL;

vector<ll> sasami_san_kawaii(vector<ll> vec) {
  vector<ll> S;
  S.push_back(1);
  rep(i,(int)vec.size()) {
    ll coef = vec[i];
    vector<ll> tmp = S;
    tmp.push_back(coef);
    rep(j,(int)S.size()) {
      ll v = S[j];
      while( v <= v * coef && v * coef <= MAX ) {
        v *= coef;
        tmp.push_back(v);
      }
    }
    S = tmp;
  }
  S.erase(S.begin());
  sort(S.begin(),S.end());
  S.erase(unique(S.begin(),S.end()),S.end());
  return S;
}


int main() {

  vector<ll> X,Y;
  {
    vector<ll> fib1,fib2;
    fib1.push_back(2);
    fib1.push_back(3);
    fib1.push_back(5);
    fib1.push_back(13);
    fib1.push_back(21);
    fib1.push_back(34);
    fib1.push_back(55);
    fib1.push_back(89);

    fib2.push_back(233);
    fib2.push_back(377);
    while( 1 ) {
      int size = (int)fib2.size()-1;
      ll tmp = fib2[size] + fib2[size-1];
      if( tmp > MAX || tmp < 0 ) break;
      fib2.push_back(tmp);
    }
    X = sasami_san_kawaii(fib1);
    Y = sasami_san_kawaii(fib2);
  }
  int T;
  cin >> T;
  while( T-- ) {
    ll a,b;
    cin >> a >> b;
    ll maxi = -1LL;
    rep(i,(int)Y.size()) {
      if( Y[i] < a ) continue;
      if( Y[i] > b ) break;
      maxi = max(maxi,Y[i]);
      if( maxi == b ) break;
    }
    rep(i,(int)X.size()) {
      if( X[i] < a ) continue;
      if( X[i] > b ) break;
      maxi = max(maxi,X[i]);
      if( maxi == b ) break;
    }
    
    rep(i,(int)X.size()) {
      if( X[i] > b ) break;
      if( a <= X[i] && X[i] <= b ) maxi = max(maxi,X[i]);
      if( maxi == b ) break;
      ll v = b / X[i];
      if( v < 233LL ) continue;
      
      int pos = lower_bound(Y.begin(),Y.end(),v) - Y.begin();
      if( 0 <= pos && pos < (int)Y.size() && Y[pos] > v ) --pos;
      if( pos < 0 || (int)Y.size() <= pos ) continue;
      maxi = max(maxi,X[i] * Y[pos]);
    }
    cout << maxi << endl;
  }
  return 0;
}