PKU : 2552 - Assistance Required

問題概要

http://poj.org/problem?id=2552
2,3,4,5,... の連続する番号があります.
はじめ, 1番目の数字を見ます. 2なので, 2個とばしで数字を消していきます.
次に, 2番目の数字を見ます. 先ほどの操作で残っている数字に対して, 3個とばしで数字を消していきます.
この操作を繰り返してできあがる数列で, n番目の数字を求めよ.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 //最初の数字
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 //2個とばしで消す
2 3 5 7 11 13 17 19 23 25 29 //3個とばしで消す
2 3 5 7 11 13 17 23 25 29 //5個とばしで消す

アルゴリズム

3000項目の数字はそんなに大きくないので, ただのシミュレートで解けてしまいます.

プログラム

int main(void){
  vector<int> v;
  for(int i=2;i<=35000;i++){
    v.push_back(i);
  }
  for(int i=0;i<v.size() && i<3000;i++){
    vector<int> nv;
    for(int j=0;j<v.size();j++){
      if(j <= i || (j-i) % v[i] != 0){
        nv.push_back(v[j]);
      }
    }
    v = nv;
  }

  int n;

  while(cin>>n,n){
    cout<<v[n-1]<<endl;
  }
}