読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 2247 Humble Numbers

問題

素因数が2,3,5,7のみであるものをHumble Numberという。n番目のHumble Numberを出力せよ。(1 <= n <= 5842)

やりかた

setにhumble numberを突っ込んでいって一番小さいものから取り出してそれらに2,3,5,7をかけてもう一度setに突っ込んで、また一番小さいものから取り出してを十分な数まで繰り返してやればいい。

以下ソース。

int main(int argc, char **argv){
  set<ll> q;
  q.insert(1);

  vector<ll> hum;
  set<ll>::iterator it = q.begin();
  for(int i = 0; i < 7000; i++){
    ll t = *it;
    hum.push_back(t);
    q.insert(t * 2); q.insert(t * 3); q.insert(t * 5); q.insert(t * 7);
    it++;
  }
  
  int n;
  while(scanf("%d", &n), n){
    int c = n % 100;
    if(c == 11 || c == 12 || c == 13) 
      printf("The %dth humble number is %d.\n", n, hum[n - 1]);
    else if(n % 10 == 1)
      printf("The %dst humble number is %d.\n", n, hum[n - 1]);
    else if(n % 10 == 2)
      printf("The %dnd humble number is %d.\n", n, hum[n - 1]);
    else if(n % 10 == 3)
      printf("The %drd humble number is %d.\n", n, hum[n - 1]);
    else
      printf("The %dth humble number is %d.\n", n, hum[n - 1]);
  }
  return 0;
}
しょげないでよBaby 眠れば治る