f(m) =am + bm [log2(m)] + cm^3 및 (a =1, 2, 3, …), (b =1, 2, 3, …), (c =0, 1, 2, 3, …)
여기서 [log2(m)]은 밑이 2인 로그이고 값을 내림합니다. 그래서
m =1이면 값은 0입니다.
m =2-3이면 값은 1입니다.
m =4-7인 경우 값은 2입니다.
m =8-15인 경우 값은 3입니다. 따라서 on
f(m) =l이 되도록 m 값을 찾아야 합니다. l이 시퀀스에 없으면 0을 인쇄해야 합니다. 값은 64비트 및 100보다 작거나 같은 세 개의 정수 a, b 및 c.
따라서 입력이 a =2, b =1, c =1, l =12168587437017이면 출력은 f(23001) =12168587437017과 같이 23001이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
SMALLER_VAL :=1000000
-
LARGER_VAL :=1000000000000000
-
solve() 함수를 정의합니다. 이것은, b, c, n
이 걸립니다. -
답변 :=a * n
-
lg_val :=n의 로그 밑수 2의 바닥
-
ans :=ans + b * n * lg_val
-
ans :=ans + c * n^3
-
반환
-
기본 방법에서 다음을 수행하십시오 -
-
시작 :=1
-
끝 :=SMALLER_VAL
-
c가 0과 같으면
-
끝 :=LARGER_VAL
-
-
답변 :=0
-
동안 시작 <=종료, 수행
-
mid :=(시작 + 끝) / 2(정수 부분만 사용)
-
val :=해결(a, b, c, 중간)
-
val이 k와 같으면
-
as :=중간
-
루프에서 나오다
-
-
그렇지 않으면 val> k일 때
-
끝 :=중간 - 1
-
-
그렇지 않으면
-
시작 :=중간 + 1
-
-
-
반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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))
입력
2,1,1,12168587437017
출력
23001