Div1 250 PrimeSequence

問題

漸化式 a_k+1＝[a_k / 2] により数列を作る．その初めの D 項 a₁〜a_D が全て素数となる，N 以下で最大の a₁ を求めよ．
ただし[]はガウス記号で要するに小数点以下切り捨て．

考え方

ただ普通にループを1ずつ回すと間に合わないので，ある程度制約を考える必要がある．
(D-1)回2で割り(端数切り捨て)，最初を含めてD回連続で素数ということは，

1. D回連続で奇数→2進数で xxx1…(D個)…1 (xxxは適当に入る)
2. (D-1)回連続奇数で，最後は2→2進数で 101…(D-1個)…1

のいずれかになる．
1.の条件に当てはまる数は 2^D(X＋1)−1 で表されるので，X部分だけループで回せばよい．
2.の条件に当てはまる数は，実は 2,5,11,23,47 の5つしかない．かつ D が決まれば（Nとの大小関係は別として）一意に定まる．というのも例えば D=2 のときに 11,23,47 は1.の条件と被るから．なのでこちらはNとの大小関係だけ気にすればOK．

コード

static int to2[] = {-1, 2, 5, 11, 23, 47};
class PrimeSequences
{
  bool isPrime(int n)
  {
    for( int k = 3 ; k * k <= n ; k += 2 ) {
      if( n % k == 0 ) return false;
    }
    return true;
  }
  bool isDiv2(int n, int d)
  {
    for( int i = 0 ; i < d ; ++i ) {
      if( n > 3 ) {
        if( (n & 1) == 0 ) return false;
        if( !isPrime(n) ) return false;
      } else if( n < 2 ) return false;
      n /= 2;
    }
    return true;
  }
public:
  int getLargestGenerator(int N, int D)
  {
    const int MOD = 1 << D;
    int pDiv2 = -1, qDiv2 = -1;
    if( D < 6 && to2[D] <= N ) qDiv2 = to2[D];
    int n = N / MOD * MOD + MOD - 1;
    if( n > N ) n -= MOD;
    for(  ; n > 0 && n > qDiv2 ; n -= MOD ) {
      if( isDiv2(n, D) ) {
        pDiv2 = n;
        break;
      }
    }
    return (pDiv2 > qDiv2) ? pDiv2 : qDiv2;
  }
};