BOJ 1407 - 2로 몇 번 나누어질까

문제

BOJ 1407 - 2로 몇 번 나누어질까

f(x)를 x에서 2로 나눌 수 있을 때까지 나눈 결과(홀수 부분)라 할 때, A부터 B까지 f(x)의 합을 구하라.

입력

A와 B가 공백으로 구분되어 주어진다 (1 <= A <= B <= 10^15).

출력

f(A) + f(A+1) + ... + f(B)를 출력한다.

예제

풀이

누적합 공식을 이용해 [1, N]의 f(x) 합을 O(log N)에 계산하고, [A, B] = [1, B] - [1, A-1]로 분리한다.

1. [1, N]의 합 = N + sum(floor(N/2^i) * 2^(i-1), i=1..49)
2. 이 공식은 2^i의 배수마다 2^(i-1)씩 추가 기여하는 것을 누적한 것이다
3. [1, B]와 [1, A-1]을 각각 계산하여 빼면 답이다

핵심 아이디어: f(x)의 합을 2의 거듭제곱별 배수 개수로 분해하면, O(log N)에 계산 가능하다.

코드

A, B = map(int, input().split())
A -= 1
a = A
for i in range(1, 50):
    a += (A // 2**i) * (2 ** (i - 1))
 
b = B
for i in range(1, 50):
    b += (B // 2**i) * (2 ** (i - 1))
 
print(b - a)

복잡도

• 시간: O(log B)
• 공간: O(1)