Em có một đề bài và code đáp án ngắn gọn nhưng em không hiểu, mọi người giải thích giùm em được không ạ. K lẻ thì bằng 1 nhưng em chưa hiểu tại sao k chẵn thì mỗi lần chia đôi + 1 sẽ ra kết quả.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
long n, k;
cin >> n >> k;
long l = 1;
while (k % 2 == 0)
{
k /= 2;
l++;
}
cout << l << endl;
}
return 0;
}
Bài này giải không mẹo thì sẽ là 
for(i=31;k;--i) if(1UL << i >= k) k -= (1UL << i);
Như vậy bit 1 cuối (chính là số lẻ) sẽ ứng với số 1, và dãy bit 1000…0 mà & với 0111…1 là 0.
Hay đáp số là 1 + __builtin_ctz(k).
Anh giải thích cho em dòng code đó đã làm gì ạ. Với anh xem hộ em còn có ý tưởng nào để dễ hiểu cho tân binh như em không
Dãy cấp 1 có độ dài 2^1 - 1 = 1
Dãy cấp n+1 có độ dài |A_{n+1}| = |A_n| +1 + |A_n| =(2^n - 1 + 1) + 2^n - 1 = 2^{n+1} - 1
Do dãy cấp n+1 được tạo thành từ dãy cấp n nên vị trí thứ p và p + 2^n là bằng nhau.
ví dụ:
k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
A = [1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 ...]
^ ^ ^ ^
k = 1 = 2^\textcolor{red}0 thì A_k = \textcolor{red}0+1 = 1
k = 2 = 2^\textcolor{red}1 thì A_k = \textcolor{red}1+1 = 2
k =4 = 2^\textcolor{red}2 thì A_k = \textcolor{red}2+1 = 3
k =8 = 2^\textcolor{red}3 thì A_k = \textcolor{red}3+1 = 4
ví dụ:
k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
A = [1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 ...]
^ ^
* *
k = 14 đối xứng với k = 6 qua x = 4 = 3 + 1 nên A_{6} = A_{6+2^3} = A_{14}
k = 6 đối xứng với k = 2 qua x = 3 = 2 + 1 nên A_{2} = A_{2+2^2} = A_{6}
viết ra dưới dạng nhị phân thì dễ thấy hơn :V
và
tổng hợp 2 quy luật, rút từ từ k từ quy luật 2 về quy luật 1 ra thì
tức là rút số bit 1 bên trái k đi tới khi nào còn x = 2^n, với n là số bit 0 bên phải của k khi biểu diễn k dưới dạng nhị phân :V
nhận thấy đáp án chỉ cần đếm số bit 0 bên phải của k khi biểu diễn k dưới dạng nhị phân nên ta ko cần bước loại bỏ số bit 1 làm gì, đếm thẳng số bit 0 bên phải như code đáp án kia luôn :V
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?