Nội dung Bài tập
- Mã:
- ZebraLikeNumber
- Tên:
- Số ngựa vằn
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 2 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- Shido
Chúng ta gọi một số nguyên dương giống ngựa vằn nếu biểu diễn nhị phân của nó có các bit xen kẽ lên đến bit có trọng số cao nhất và bit có trọng số thấp nhất bằng 1. Ví dụ, các số 1, 5 và 21 giống ngựa vằn vì biểu diễn nhị phân của chúng là 1, 101 và 10101 đáp ứng các yêu cầu, trong khi số 10 không giống ngựa vằn vì bit có trọng số thấp nhất trong biểu diễn nhị phân 1010 của nó là 0 ( tức là bit cuối cùng là 0) .
Quảng cáo
Chúng ta định nghĩa giá trị ngựa vằn của một số nguyên dương e là số nguyên p nhỏ nhất sao cho e có thể được biểu thị là tổng của p số giống ngựa vằn (có thể giống nhau, có thể khác nhau). Cho ba số nguyên l, r và k, hãy tính số số nguyên x sao cho l ≤ x ≤ r và giá trị ngựa vằn của x bằng k .
Input :
- Dòng đầu tiên chứa một số nguyên t (1≤ t ≤100) — số lượng testcase.
- t dòng tiếp theo chứa ba số nguyên l, r (1≤ l ≤ r ≤ 1018) và k (1 ≤ k ≤ 1018).
Outpur :
- Đối với mỗi tescase hãy xuất ra một số nguyên duy nhất — số lượng số nguyên trong [l,r] có giá trị ngựa vằn k.
Ví dụ:
Input
Output
5
1 100 3
1 1 1
15 77 2
2 10 100
1234567 123456789101112131 12
13
1
3
0
4246658701
Trong trường hợp thử nghiệm đầu tiên, có 13 số phù hợp: 3,7,11,15,23,27,31,43,47,63,87,91,95. Mỗi số có thể được biểu diễn dưới dạng tổng của 3 số giống ngựa vằn.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
Luyện tập LTNC cuối tuần