두 수 A와 B 사이(inclusive)에 속하는 모든 수를 이진수로 나타냈을 때, 1의 개수를 구하는 문제입니다. 단순하게 각 수에 대해 1의 개수를 센다면 약 $O((b-a)\log b)=O(b\log b)$의 시간복잡도가 필요합니다. 하지만 주어지는 수가 상당히 크기 때문에 이 시간복잡도로는 힘들어보입니다. 시간 제한 값을 보면 적어도 $O(\log b)$에는 끝내야할 것 같습니다. 즉, A에서 B까지의 간격은 무시하고 각 자리마다 1의 개수를 한 번에 구하는 알고리즘이 필요합니다. 그 방법은 아래와 같이 생각해낼 수 있습니다.
- 각 자릿수 X에 대해
- A와 B에 대해 각각 작거나 같은 2X의 배수(이하 각각 AX, BX)를 찾음
- AX와 BX의 차이에 1/2를 곱함(=두 수 사이의 모든 수의 X번째 자리의 1의 개수)
- 여기에 B와 BX까지의 X번째 자리의 1의 개수를 더함
- 여기에 A와 AX까지의 X번째 자리의 1의 개수를 뺌
이를 코드로 나타내면 아래와 같이 됩니다.
X2 = (((b >> x) << x) - ((a >> x) << x)) / 2 # 2번 내용
X3 = max(b % (1 << x) - x // 2, 0) # 3번 내용
X4 = max(a % (1 << x) - x // 2, 0) # 4번 내용
위의 코드에서 각 x에 대한 X2 + X3 - X4를 구하여 합을 출력하면 됩니다.
PS알못 OrbitHv의 PS