SRM471 div1 easy

まずはエラトステネスのふるいから解いてみる．

  int getLargestGenerator(int N, int D) {
    int dp[N+1];
    vector list;
    list.push_back(-1);
    memset(dp, 0, sizeof dp);
    dp[2] = 1;
    set prime; prime.insert(2);
    set::iterator it;
    for(int i = 3; i < N+1; i += 2) {
      bool flag = true;
      for(it = prime.begin(); (*it)*(*it) <= i; it++) {
	if(i % (*it) == 0) {
	  flag = false;
	}
      }
      if(flag) {
	prime.insert(i); dp[i] = dp[i/2]+1;
	if(dp[i] >= D) {
	  list.push_back(i);
	}
      }
    }
    return list.back();
  }
//2000000で1.3sなので、10000000ではかなりきつい．というか、無理．
//dp[10000001]の配列はとれないという致命的な欠点もある．たしか、topcoderのメモリは64MBで設定されているはず．
//あと、listは別にいらないよね．int型で十分．

そこで、

//一番目の問題に対しては、nの倍数(n:prime)は順次消していく方法をとる．
//2番目の問題に対しては、intではなく、vector を用いると良い．
  int getLargestGenerator(int N, int D) {
    vector dp(N+1, -1);
    int ans = -1;
    dp[2] = 1;
    for(int i = 4; i <= N; i += 2) {
      dp[i] = 0;
    }
    for(int i = 3; i <= N; i += 2) {
      if(dp[i] == 0) continue;    
      for(int j = 2*i; j <= N; j += i) {
	dp[j] = 0;
      }
      dp[i] = dp[i/2]+1;
      if(dp[i] >= D) {
	ans = i;
      }
    }
    return ans;
  }
//N = 10000000 で0.95s

もっと早くする方法もある．それは、vector --> vectorにするということ．dp[N]の値はせいぜい20くらいみたいなので。

    vector dp(N+1, -1);  //change
    int ans = -1;
    dp[2] = 1;
    for(int i = 4; i <= N; i += 2) {
      dp[i] = 0;
    }
    for(int i = 3; i <= N; i += 2) {
      if(dp[i] == 0) continue;    
      for(int j = 2; j <= N; j += i) {
	dp[j] = 0;
      }
      dp[i] = dp[i/2]+1;
      if(dp[i] >= D) {
	ans = i;
      }
    }
    return ans;
  }
//N=10000000で0.56s