Hướng dẫn giải của BASE05: Số thập phân sang thập lục phân
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đổi số nguyên N từ thập phân sang thập lục phân, các chữ số A-F viết hoa. Đề cho |N| ≤ 10^9 nên xử lý dấu âm bằng cách in dấu '-' rồi đổi giá trị tuyệt đối.
Sub 1: Trừ dần theo lũy thừa của 16 — ~O(log_16 N · 16)~
Tìm lũy thừa 16^p lớn nhất không vượt |N|. Với p giảm dần, đếm số lần trừ được 16^p rồi lấy ký tự hex tương ứng. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
const string HEX = "0123456789ABCDEF";
long long n;
cin >> n;
bool neg = n < 0;
long long x = llabs(n);
if (x == 0) { cout << 0 << "\n"; return 0; }
// Vét cạn: tìm lũy thừa 16 lớn nhất không vượt x, rồi với mỗi lũy thừa đếm số lần trừ được
long long p = 1;
while (p * 16 <= x) p *= 16;
string res = neg ? "-" : "";
while (p > 0) {
int digit = 0;
while (x >= p) { x -= p; digit++; }
res += HEX[digit];
p /= 16;
}
cout << res << "\n";
return 0;
}
Sub 2: Chia lấy dư cho 16 — ~O(log_16 N)~
Lặp chia |N| cho 16, lấy số dư tra trong chuỗi "0123456789ABCDEF", rồi đảo ngược kết quả. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
const string HEX = "0123456789ABCDEF";
long long n;
cin >> n;
bool neg = n < 0;
long long x = llabs(n);
if (x == 0) { cout << 0 << "\n"; return 0; }
// Chia liên tiếp cho 16, lấy số dư làm chữ số hex (từ thấp đến cao), sau đó đảo ngược
string res;
while (x > 0) {
res += HEX[x % 16];
x /= 16;
}
reverse(res.begin(), res.end());
cout << (neg ? "-" : "") << res << "\n";
return 0;
}
Bình luận