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

UVa443 Humble Numbers

問題
http://uva.onlinejudge.org/external/4/443.html

概要
{2, 3, 5, 7} を素因数に持つ数字をのうち、N番目のものを言い当てよ。

解法
{2, 3, 5, 7} からそれぞれ任意個数分選び、乗算する。それぞれ素数同士なので、別の組み合わせによる値の重複はない。
また、LIMIT が 10 桁なので、枝狩りの際の乗算の値は最大でも 7*LIMIT となり long long に収まるのでオーバーフローはしない。
出力で注意すべきこととしては、与えられた N について N%100 == 11, 12, 13 では suffix が "th" となることがある。

反省
乗算するとき値の初期化に注意しないとならなかった。
自分は初め以下のコードで、num = a*b*c; とせずに num *= c; としていたため、前の組み合わせの num に繰り返し値を掛けていたミスがあった。

int const MAX = 5842;
ll const LIMIT = 2000000000;
 
ll humble[MAX];
 
void solve() {
   
  int cnt = 0; 
  rep(i, MAX) {
    ll a = pow(7., i);
    if(a > LIMIT) break;
    ll num = a;
     
    rep(j, MAX) {
      ll b = pow(5., j);
      num = a*b; if(num > LIMIT) break;
       
      rep(k, MAX) {
        ll c = pow(3., k);
        num = a*b*c; if(num > LIMIT) break;
         
        rep(l, MAX) {
          ll d = pow(2., l);
          num = a*b*c*d; if(num > LIMIT) break;
          humble[cnt++] = num;
        }
      }
    }
  }
   
  sort(humble, humble+MAX);
   
}
 
string getNumberWithSuffix(int num) {
  int x = num%100;
  string suffix;
  if(x == 11
     || x == 12
     || x == 13) suffix = "th";
  else if(x%10 == 1) suffix = "st";
  else if(x%10 == 2) suffix = "nd";
  else if(x%10 == 3) suffix = "rd";
  else suffix = "th";
   
  return toStr(num) + suffix;
}
 
int main() {
   
  solve();
   
  int N;
  while(cin >> N && N) {
    cout << "The " << getNumberWithSuffix(N) << " humble number is " << humble[N-1] << "." << endl;
  }
   
  return 0;
}