Ý tưởng giải của bài toán này là ta sẽ tiền xử lý hết tất cả các số có thể chia hết cho $2,3,5$ trong khoảng từ $[1,10^{18}]$ và kết hợp chặt nhị phân
Nhận xét đầu tiên là ta nhận thấy các số mũ của thừa số nguyên tố $2,3,5$ sẽ không quá lớn nên ta thực hiện tính số mũ tối đa có thể có của từng thừa số nguyên tố:
$\log_2(10^{18}) \approx 60, \log_3(10^{18}) \approx 37, \log_5(10^{18}) \approx 26$.
Dựa vào các số mũ này ta sẽ tiền xử lý để sinh ra các số thoả điều kiện, tuy nhiên giới hạn ở đây khá lớn (tiệm cận LLONG_MAX) nên khi tính số mũ phải nhân dần và if else để tránh bị tràn.
```cpp
int binpow(int a, int b) {
int res = 1;
while (b) {
if (b&1) res *= a;
a*=a;
b>>=1;
}
return res;
}
bool check(int pow1, int pow2, int pow3) {
int res = 1;
for(int i = 1; i <= pow1; i++) {
res *= 2;
if(res > 1e18) {
return false;
}
}
for(int i = 1; i <= pow2; i++) {
res *= 3;
if (res > 1e18) {
return false;
}
}
for(int i = 1; i <= pow3; i++) {
res *= 5;
if (res > 1e18) {
return false;
}
}
if (res <= 1e18) {
return true;
} else {
return false;
}
}
void solve() {
vector<int> ans;
for(int i = 0; i <= 60; i++) {
for(int j = 0; j <= 38; j++) {
for(int k = 0; k <= 26; k++) {
if (check(i, j, k)) {
int tmp = binpow(2, i)*binpow(3, j)*binpow(5, k);
//cout << tmp << endl;
ans.push_back(tmp);
}
}
}
}
sort(ans.begin(), ans.end());
int m,x; cin >> m;
while(m--) {
cin >> x;
int it = lower_bound(ans.begin(), ans.end(), x) - ans.begin();
if (ans[it]==x) {
cout << it+1 << endl;
} else {
cout << -1 << endl;
}
}
}
```
**Nhận xét**: Vì $n \le 10^5$, $m \le 10^{18}$, nếu sinh các số Hamming trong toàn bộ $q$ truy vấn thì sẽ TLE.
### Phương pháp giải
Sinh toàn bộ số Hamming trước khi thực hiện $q$ truy vấn: vì mỗi số Hamming phải thỏa yêu cầu h = $2^x \times 3^y \times 5^z$, nên ta sinh các số Hamming bằng 3 vòng for giá trị $2^x, 3^y, 5^z$:
```
#define ll long long
for (ll p2 = 1; p2 <= maxH; p2 *= 2) {
for (ll p3 = p2; p3 <= maxH; p3 *= 3) {
for (ll p5 = p3; p5 <= maxH; p5 *= 5) {
v.push_back(p5);
}
}
}
```
Sau đó, với mỗi truy vấn, ta sẽ dùng tìm kiếm nhị phân để tìm vị trí cụ thể trong dãy các số Hamming đã sinh,
nếu không tìm thấy sẽ in $-1$.
Semicolon
Created at
6 likes
Long4200
Created at
6 likes