Hướng dẫn giải của [200 đề thầy Đức] Bài 67: Tìm giá trị
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
Với $n > 0$, viết $n = 2^m + p$ trong đó $m$ là số mũ lớn nhất sao cho $2^m \le n$. Cần in ra $m$ và $p$.
Sub 1: Vét cạn số mũ — ~O(\log n)~
Thử lần lượt các số mũ $k = 0, 1, \dots, 31$, giữ lại $k$ lớn nhất thỏa $2^k \le n$. Sau đó $p = n - 2^m$. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử mọi m từ 0 đến 31, lấy m lớn nhất sao cho 2^m <= n.
long long m = 0;
for (int k = 0; k <= 31; k++)
if ((1LL << k) <= n) m = k;
long long p = n - (1LL << m);
cout << m << " " << p << "\n";
return 0;
}
Sub 2: Dùng vị trí bit cao nhất — ~O(1)~
Số mũ $m$ chính là vị trí của bit 1 cao nhất trong biểu diễn nhị phân của $n$, hàm __lg(n) của GCC trả về đúng giá trị này. Khi đã có $m$ thì $p = n - 2^m$.
Ví dụ: $n = 11 = 1011_2$ có bit cao nhất ở vị trí 3, nên $m = 3$ và $p = 11 - 8 = 3$.
Bẫy cần chú ý: với $n = 1$ thì $m = 0$, $p = 0$. Vì $n \le 10^9$ nên dùng long long cho $2^m$ là an toàn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// m là số mũ lớn nhất sao cho 2^m <= n, chính là vị trí bit cao nhất của n.
// __lg(n) trả về vị trí bit 1 cao nhất (với n > 0).
int m = __lg(n);
long long p = n - (1LL << m);
cout << m << " " << p << "\n";
return 0;
}
Bình luận