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; }