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

AOJ0162 Hamming Numbers

解法
先にハミング数を全列挙してクエリに答える。
2と3と5の数を決めうちして列挙する。重複を許さないように、得られた値は set に詰める。
2^20 が100万を超えるので、2, 3, 4 は 20 個まで選択すれば十分。

#include <bits/stdc++.h>
using namespace std;
 
set<int> hamming;
void make_hamming() {
  for(int i=0; i<20; i++) 
    for(int j=0; j<20; j++)
      for(int k=0; k<20; k++)
        hamming.insert(pow(2.0, i)*pow(3.0, j)*pow(5.0, k));
}
 
int main() {
  make_hamming();
  int m, n;
  while(cin >> m >> n && m) {
    set<int>::iterator it = hamming.begin();
    int cnt = 0;
    for(it; it!=hamming.end(); it++) {
      if(m<=*it && *it <=n) cnt ++;
    }
    cout << cnt << endl;
  }
  return 0;
}