Cho trước số nguyên dương N, hãy cho biết N có thuộc dãy Hamming hay không? Nếu thuộc thì nó đứng ở vị trí thứ mấy trong dãy Hamming các phần tử được sắp xếp tăng?
Xem clip hướng dẫn
Thứ Tư, 10 tháng 7, 2019
Dãy Hamming 2
Dãy Hamming là dãy số nguyên dương có các số hạng là số nguyên dương có ước nguyên tố không lớn hơn 5. Ví dụ sô 10 là 1 số thuộc dãy Hamming vì 10 = 2x5 nhưng 14 thì không phải vì 14=2x7 nó có ước nguyên tố là 7>5.
Cho trước số nguyên dương N, hãy cho biết N có thuộc dãy Hamming hay không? Nếu thuộc thì nó đứng ở vị trí thứ mấy trong dãy Hamming các phần tử được sắp xếp tăng?
Cho trước số nguyên dương N, hãy cho biết N có thuộc dãy Hamming hay không? Nếu thuộc thì nó đứng ở vị trí thứ mấy trong dãy Hamming các phần tử được sắp xếp tăng?
Đăng ký:
Đăng Nhận xét (Atom)
Nhận xét này đã bị tác giả xóa.
Trả lờiXóa/// Code by hhoangcpascal
Trả lờiXóa/// Problem: HAMMING
/// Time: O(log2(10*18) * log3(10^18) * log5(10^18) * log2(log2(10*18) * log3(10^18) * log5(10^18)))
#include
#include
#include
#define llong long long
#define name_file "HAMMING"
using namespace std;
template
bool fast_scan(T &num) {
num = 0;
register char c = getchar();
while (c != '-' && (c < '0' || '9' < c)) {
if (feof(stdin)) return false;
c = getchar();
}
bool neg = false;
if (c == '-') {
neg = true;
c = getchar();
}
for(; '0' <= c && c <= '9'; c = getchar()) num = (num << 1) + (num << 3) + (c - '0');
if (neg) num = -num;
return true;
}
vector V;
void init() {
const llong mmax = 1e18;
for(llong a=1; a<=mmax; a *= 2)
for(llong b=1; a * b <= mmax; b *= 3)
for(llong c=1; a * b * c <= mmax; c *= 5) V.push_back(a*b*c);
sort(V.begin(), V.end());
}
int main() {
#ifndef ONLINE_JUGDE
freopen(name_file".inp", "r", stdin);
freopen(name_file".out", "w", stdout);
#endif //ONLINE_JUGDE
init();
int n; fast_scan(n);
while (n--) {
llong t; fast_scan(t);
int p = lower_bound(V.begin(), V.end(), t) - V.begin();
if (p == (int) V.size() || V[p] != t) cout << "Not in sequence\n"; else cout << p+1 << "\n";
}
return 0;
}