Tìm vị trí phần tử trong dãy đơn điệu cho trước trong Python

Cho số l và dãy đơn điệu tăng f(m) = a·m + b·m·⌊log₂(m)⌋ + c·m³ với a,b ∈ {1,2,3...}, c ∈ {0,1,2,3...}. Tìm m sao cho f(m) = l, không có thì trả 0.

Ví dụ: a=2, b=1, c=1, l=12168587437017 → m=23001.

Thuật toán Binary Search

1. Hàm solve(a,b,c,n) tính f(n).
2. Giới hạn tìm kiếm: nếu c=0 thì upper bound lớn (10¹⁵), ngược lại 10⁶.
3. Binary search trên m: tính val = solve(a,b,c,mid), so sánh với k.
4. Trả về m tìm được hoặc 0.

Ví dụ code

from math import log2, floor

SMALLER_VAL = 1000000
LARGER_VAL = 1000000000000000

def solve(a, b, c, n):
    ans = a * n
    lg_val = floor(log2(n))
    ans += b * n * lg_val
    ans += c * n**3
    return ans

def get_pos(a, b, c, k):
    begin = 1
    end = SMALLER_VAL
    if c == 0:
        end = LARGER_VAL
    ans = 0
    while begin <= end:
        mid = (begin + end) // 2
        val = solve(a, b, c, mid)
        if val == k:
            ans = mid
            break
        elif val > k:
            end = mid - 1
        else:
            begin = mid + 1
    return ans

a = 2
b = 1
c = 1
k = 12168587437017
print(get_pos(a, b, c, k))

Input

2, 1, 1, 12168587437017

Output

23001