Hướng dẫn giải của [200 đề thầy Đức] Bài 4: Tính chẵn lẻ
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
Tính chẵn lẻ của N là tính chẵn lẻ của số bit 1 trong biểu diễn nhị phân của N: số bit 1 chẵn thì in "even", lẻ thì in "odd".
Chỉ viết 1 sub vì đây là phép đếm bit trực tiếp. Đạt 21/21 test.
Sub 1: Đếm bit bằng chia 2 — ~O(log n)~
Lặp lấy n % 2 để cộng vào bộ đếm rồi chia n cho 2 cho đến khi n = 0. Cuối cùng xét bộ đếm chẵn hay lẻ. Dùng unsigned long long vì N ≤ 10^12.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
unsigned long long n;
cin >> n;
// Đếm số bit 1 bằng cách lấy n chia 2 liên tục
int cnt = 0;
while (n > 0) {
cnt += n % 2;
n /= 2;
}
cout << (cnt % 2 == 0 ? "even" : "odd") << "\n";
}
return 0;
}
Bình luận