Giả sử chúng ta có một số l và một dãy tăng đơn điệu f (m), trong đó f (m) =am + bm [log2 (m)] + cm ^ 3 và (a =1, 2, 3,…), (b =1, 2, 3,…), (c =0, 1, 2, 3,…)
Ở đây [log2 (m)] là log của cơ số 2 và làm tròn giá trị xuống. vì vậy,
nếu m =1, giá trị là 0.
nếu m =2-3, giá trị là 1.
nếu m =4-7, giá trị là 2.
nếu m =8-15, giá trị là 3 và cứ tiếp tục như vậy
chúng ta phải tìm giá trị m sao cho f (m) =l, nếu l không có trong dãy thì chúng ta phải in ra 0. Chúng ta phải ghi nhớ rằng các giá trị sao cho chúng có thể được biểu diễn trong 64 bit và ba số nguyên a, b và c nhỏ hơn hoặc bằng 100.
Vì vậy, nếu đầu vào là a =2, b =1, c =1, l =12168587437017, thì đầu ra sẽ là 23001 là f (23001) =12168587437017
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
SMALLER_VAL:=1000000
-
LARGER_VAL:=1000000000000000
-
Định nghĩa một hàm giải quyết (). Điều này sẽ mất a, b, c, n
-
ans:=a * n
-
lg_val:=tầng của khúc gỗ cơ số 2 trong n
-
ans:=ans + b * n * lg_val
-
ans:=ans + c * n ^ 3
-
trả lại ans
-
Từ phương thức chính, thực hiện như sau -
-
bắt đầu:=1
-
end:=SMALLER_VAL
-
nếu c giống 0 thì
-
end:=LARGER_VAL
-
-
ans:=0
-
trong khi bắt đầu <=end, thực hiện
-
mid:=(begin + end) / 2 (chỉ lấy phần nguyên)
-
val:=giải quyết (a, b, c, giữa)
-
nếu val giống với k thì
-
ans:=mid
-
đi ra từ vòng lặp
-
-
ngược lại khi val> k thì
-
end:=mid - 1
-
-
nếu không,
-
bắt đầu:=mid + 1
-
-
-
trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
2,1,1,12168587437017
Đầu ra
23001