Ý 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;
}
}
}
```
Semicolon
Created at
2 likes