问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and the first lines of Python solution to this problem, and will write in Python the remaining lines of the program to produce a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the second part of the program that you wrote.
### Question:
You are given an integer k and an integer x.
Consider s is the 1-indexed binary representation of an integer num. The price of a number num is the number of i's such that i % x == 0 and s[i] is a set bit.
Return the greatest integer num such that the sum of prices of all numbers from 1 to num is less than or equal to k.
Note:

In the binary representation of a number set bit is a bit of value 1.
The binary representation of a number will be indexed from right to left. For example, if s == 11100, s[4] == 1 and s[2] == 0.


Example 1:

Input: k = 9, x = 1
Output: 6
Explanation: The numbers 1, 2, 3, 4, 5, and 6 can be written in binary representation as "1", "10", "11", "100", "101", and "110" respectively.
Since x is equal to 1, the price of each number is the number of its set bits.
The number of set bits in these numbers is 9. So the sum of the prices of the first 6 numbers is 9.
So the answer is 6.
Example 2:

Input: k = 7, x = 2
Output: 9
Explanation: Since x is equal to 2, we should just check even^th bits.
The second bit of binary representation of numbers 2 and 3 is a set bit. So the sum of their prices is 2.
The second bit of binary representation of numbers 6 and 7 is a set bit. So the sum of their prices is 2.
The fourth bit of binary representation of numbers 8 and 9 is a set bit but their second bit is not. So the sum of their prices is 2.
Numbers 1, 4, and 5 don't have set bits in their even^th bits in their binary representation. So the sum of their prices is 0.
The second and the fourth bit of the binary representation of the number 10 are a set bit. So its price is 2.
The sum of the prices of the first 9 numbers is 6.
Because the sum of the prices of the first 10 numbers is 8, the answer is 9.

Constraints:

1 <= k <= 10^15
1 <= x <= 8

### Format: You will use the following starter code to write the solution to the problem and enclose your code within delimiters.
```python
class Solution(object):
def findMaximumNumber(self, k, x):
"""
:type k: int
:type x: int
:rtype: int
"""
def floor_log2(x):
return x.bit_length()-1

def binary_search_right(left, right, check):
while left <= right:
mid = left+(right-left)//2
if not check(mid):
right = mid-1
else:
left = mid+1
return right

def count(l):
return (prefix_cnt<<(x*l))+lookup[l]

result = prefix_cnt = 0
lookup = [0]
i = 0
while (lookup[-1]<<x)+(1<<(i+x-1)) <= k:
lookup.append((lookup[-1]<<x)+(1<<(i+x-1)))
i += x
while k >= prefix_cnt:
# l = result.bit_length()
# assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:])))
l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k)
cnt, i = count(l), x*l
c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1)
```

### Answer: (enclose your partial completion in backticks. Only write the missing portion of the code, not the entire code. Be very careful to match the appropriate indentation. Directly appending your code after the partial code should produce a correct completion solution.)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
result |= (1 << i) | ((1 << (i + c)) - (1 << i))
prefix_cnt += cnt * ((1 << c) - 1)
k -= cnt * ((1 << c) - 1)
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
deepseek-r1

```python
for j in range(c, -1, -1):
bit = 1 << (i + j)
if j == x - 1:
m = i + j + 1
new_num = result + bit
cycle = 1 << m
half = cycle >> 1
full_cycles = (new_num + 1) // cycle
rem = (new_num + 1) % cycle
curr = full_cycles * half + max(0, rem - half)
prev_full = (result + 1) // cycle
prev_rem = (result + 1) % cycle
prev_contribution = prev_full * half + max(0, prev_rem - half)
delta = curr - prev_contribution
if delta > k:
continue
k -= delta
prefix_cnt += delta
result += bit
else:
result += bit
break
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
gpto1 ```python
if cnt == 0 or c < 0:
break
result |= 1 << (i + c)
prefix_cnt += cnt << c
k -= cnt << c
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
gpt-4o-2024-08-06 ```python
result += (1 << (i + c))
prefix_cnt += cnt * (1 << c)
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
Meta-Llama-3.1-405B-Instruct-Turbo ```python
result += (1<<i)*((1<<c)-1)
k -= cnt*((1<<c)-1)
prefix_cnt += (1<<c)-1
if c < x-1:
result += 1<<i+c
k -= cnt
prefix_cnt += 1
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
Meta-Llama-3.1-70B-Instruct-Turbo ```python
k -= cnt<<c
prefix_cnt += cnt<<c
result += (1<<i)<<c
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
DeepSeek-Coder-V2-Lite-Instruct ```python
result += (1 << i)
k -= cnt
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
Qwen2-72B-Instruct ```python
result |= (1 << c) if c < i else ((1 << (c - i + 1)) - 1) << (i - 1)
k -= cnt * (1 << c) if c < i else cnt * ((1 << (c - i + 1)) - 1)
prefix_cnt += (1 << c) if c < i else ((1 << (c - i + 1)) - 1)
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
baichuan4 ```python
while i+c <= l and (prefix_cnt<<(x*(i+c)))+lookup[i+c] <= k:
i += c
result += (1<<(i-1))
prefix_cnt += (1<<(i-1))
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
doubao ```python
result += 1 << i
prefix_cnt += cnt
return result - 1
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
gpto1 ```python
if cnt == 0 or c < 0:
break
result |= 1 << (i + c)
prefix_cnt += cnt << c
k -= cnt << c
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
kimi ```python
result = (result<<c)+(1<<c-1)
prefix_cnt += cnt
if i+c >= x*l:
lookup.append(0)
l += 1
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
minimax ```python
while i > 0 and cnt + prefix_cnt + count(c) <= k:
cnt += count(c)
i -= 1
c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1)
result += 1 << (i-1)
prefix_cnt += cnt
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
wenxinyiyan ```python
k -= cnt
prefix_cnt += cnt
result |= (1<<i)
if c < x-1:
break
k -= 1<<(i+c)
prefix_cnt += 1<<(i+c)
for j in range(c):
if i+j < 64: # assuming 64-bit integers
result |= (1<<(i+j))
l = result.bit_length()
while k > 0:
if l % x == 0 and k >= (1<<(l-1)):
result |= (1<<(l-1))
k -= (1<<(l-1))
l -= 1
return result
```

### Explanation:

The given starter code sets up the necessary helper functions and initializes some variables for the binary search and prefix sum calculations. However, it stops just before the main loop that increments `result` based on the available `k` value and the `x` constraint.

The missing portion of the code completes this loop, handling the following steps:

1. It performs a binary search to find the largest `l` such that `count(l) <= k`. The `count` function calculates the prefix sum of prices for all numbers up to `2^(x*l) - 1` using a lookup table.

2. It updates `k` by subtracting the prefix sum found in the binary search.

3. It adds the corresponding bit to `result` at position `i = x*l`, which represents the highest set bit in the current group of `x` bits.

4. It checks if there are any remaining bits to set within the current group of `x` bits. If `c` (the number of remaining bits) is less than `x-1`, it breaks out of the loop since no further bits can be set in this group.

5. If there are still bits to set, it updates `k` and `prefix_cnt` to account for the additional set bits and adds them to `result`.

After the main loop, there may be some remaining `k` value that hasn't been used. The code then enters a second loop to handle this remaining `k`:

1. It iterates from the current bit length of `result` down to 1.

2. If the current bit position `l` is divisible by `x` and `k` is greater than or equal to `2^(l-1)`, it sets the bit at position `l-1` in `result` and updates `k` accordingly.

Finally, the function returns the `result`, which represents the greatest integer `num` such that the sum of prices of all numbers from 1 to `num` is less than or equal to `k`.		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
zhipu ```python
k -= cnt << c
result |= (1 << c) - 1 << i
prefix_cnt += (1 << c) * ((c + x - 1) // x)
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1
deepseek-v3 ```python
i += c
num = (1<<i)-1
k -= cnt*(1<<c)
prefix_cnt += cnt*(1<<c)
result = num
return result
```		 class Solution(object): def findMaximumNumber(self, k, x): """ :type k: int :type x: int :rtype: int """ def floor_log2(x): return x.bit_length()-1 def binary_search_right(left, right, check): while left <= right: mid = left+(right-left)//2 if not check(mid): right = mid-1 else: left = mid+1 return right def count(l): return (prefix_cnt<<(x*l))+lookup[l] result = prefix_cnt = 0 lookup = [0] i = 0 while (lookup[-1]<<x)+(1<<(i+x-1)) <= k: lookup.append((lookup[-1]<<x)+(1<<(i+x-1))) i += x while k >= prefix_cnt: # l = result.bit_length() # assert(prefix_cnt == sum(c == '1' and (l-i)%x == 0 for i, c in enumerate(bin(result)[2:]))) l = binary_search_right(1, len(lookup)-1, lambda l: count(l) <= k) cnt, i = count(l), x*l c = min(floor_log2(k//cnt) if cnt else float("inf"), x-1) cnt <<= c i += c k -= cnt result += 1<<i prefix_cnt += int((i+1)%x == 0) return result-1