Hướng dẫn giải của BASE03: Số thập phân sang bát 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ố N từ hệ thập phân sang hệ bát phân (cơ số 8). Đề cho |N| ≤ 10^5 nên có thể 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 8 — ~O(log_8 N · 8)~
Tìm lũy thừa 8^p lớn nhất không vượt |N|. Với p giảm dần, đếm số lần trừ được 8^p rồi ghi chữ số đó. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
// Đề có |N| nên xử lý dấu âm bằng cách in dấu '-' rồi đổi giá trị tuyệt đối
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 8 lớn nhất không vượt x, rồi đếm bằng cách trừ dần
long long p = 1;
while (p * 8 <= x) p *= 8;
string res = neg ? "-" : "";
// Với mỗi lũy thừa 8^i giảm dần, trừ 8^i liên tục cho đến khi không trừ được nữa
while (p > 0) {
int digit = 0;
while (x >= p) { x -= p; digit++; }
res += char('0' + digit);
p /= 8;
}
cout << res << "\n";
return 0;
}
Sub 2: Chia lấy dư cho 8 — ~O(log_8 N)~
Lặp chia |N| cho 8, lấy số dư làm chữ số (thấp nhất trước), rồi đảo ngược chuỗi kết quả. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
// Đề có |N| nên xử lý dấu âm riêng, in '-' rồi đổi thành số dương
bool neg = n < 0;
long long x = llabs(n);
if (x == 0) { cout << 0 << "\n"; return 0; }
// Chia liên tiếp cho 8, lấy số dư lần lượt là các chữ số từ thấp đến cao
string res;
while (x > 0) {
res += char('0' + x % 8);
x /= 8;
}
reverse(res.begin(), res.end());
cout << (neg ? "-" : "") << res << "\n";
return 0;
}
Bình luận