続・optional

こうなった。やりすぎ。

typedef long long LL;

// 素数かどうかを判定する
bool isPrime(LL n){
  if(n == 2) return true;
  if(n % 2 == 0) return false;
  for(LL i=3; i*i<=n; i+=2){
    if(n % i == 0) return false;
  }
  return true;
}


typedef optional<LL> OLL;
// 掛け算
OLL operator*(const OLL &x, const OLL &y){
  if(!x) return x;
  if(!y) return y;
  LL result = (*x) * (*y);
  if(result / (*x) != (*y)){
    // overflow
    return OLL();
  }
  return OLL(result);
}

// 足し算
OLL operator+(const OLL &x, const OLL &y){
  if(!x) return x;
  if(!y) return y;
  LL result = (*x) + (*y);
  if(result - (*x) != (*y)){
    // overflow
    return OLL();
  }
  return OLL(result);
}


// long longでのpow. 
OLL llpow(OLL n, size_t m){
  if(m == 0) return OLL(1);
  if(m == 1) return n;
  return n * llpow(n, m - 1);
}
OLL llpow(LL n, size_t m){
  return llpow(OLL(n), m);
}

// long longでのinvpow
// x ** m >= n となる最初のxを返す
OLL llinvpow(OLL n, size_t m){
  OLL d = 1;
  OLL x = 1;
  OLL p;
  while((p = llpow(x, m)) && *p < *n){
    d = d * 2;
    x = x + d;
  }
  if(d && x){
    LL d2 = *d, x2 = *x;
    while(d2){
      d2 /= 2;
      x2 -= d2;
      p = llpow(x2, m);
      if(p && *p < *n){
	x2 += d2;
      }
    }
    return x2;
  }
  return OLL();
}
OLL llinvpow(LL n, size_t m){
  return llinvpow(OLL(n), m);
}

class StrongPrimePower {
public:
  vector <int> baseAndExponent(string n) {
    LL v = lexical_cast<LL>(n);
    for(size_t i=2; i<64; i++){
      OLL d = llinvpow(v, i);
      if(!d) continue;
      if(*d < 2) break;
      OLL power = llpow(d, i);
      if(power && *power == v){
	if(isPrime(*d)){
	  vector<int> result;
	  result += *d, i;
	  return result;
	}
      }
    }
    vector<int> result;
    return result;
  }
}

なんだかなー。まぁ、銀の弾丸がないということはよくわかった。

昨日帰りに考えた「10*18って順番に探索したら確かにとてつもない時間がかかるだろうけど、powは単調増加な関数なんだから二分探索できるじゃん。それにたくさん累乗するばあい大きな数はすぐにオーバーフローするから答えは1付近に集中しているわけで単純な二分探索よりもっと早くなるんじゃないか？」ってのを実装してみた。実際に早いかどうかは確認してない。