[Baekjoon, 9527] 1의 개수 세기

정석적인 풀이인 자리수에 대한 누적합을 비트마스킹하여 풀지 않고 이진수의 1의 개수에 대한 규칙을 찾아 풀었다. 규칙은 노트에 이진수와 합과 숫자를 계속 끄적이다보니 알게되었다.

규칙은 아래와 같다.

sum[5] = {0, 1, 2, 4, 5}

if (x < 5)
  then sum[x]
else if (x % 2)
  then f(x) = f(x + 1) - countOnes(x + 1)
else
  then f(x) = x / 2 + f(x / 2) + f(x / 2 - 1)

예를 간단히 들어보겠다. 6에 대한 이진수의 1의 갯수를 센다고 하면 아래와 같은 순서로 구하면 된다.

f(6) = 3 + f(3) + f(2)
이때 f(3) = 4, f(2) = 2이니 
f(6) = 3 + 4 + 2 = 9

위의 규칙을 이용하여 정답은 f(b) - f(a - 1)을 계산하여 구하면 된다.

하지만 이대로 10의 16승을 계산하기에는 시간이 너무 오래걸린다. 시간을 단축하기 위해서는 중복되는 계산을 줄일 필요가 있다. 나는 map을 이용하여 해결했다.

구현

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
#include <climits>
#include <cctype>
using namespace std;

int sum = 0;

int f[5] = {0, 1, 2, 4, 5};
map<long long, long long> m;

int countOnes(long long n) {
	int ret = 0;
	while (n > 0) {
		if (n % 2) {
			ret++;
		}
		n /= 2;
	}
	return ret;
}

long long func(long long x) {
	if (x < 5) {
		return f[x];
	}
	if (m.find(x) != m.end()) {
		return m[x];
	}
	if (x % 2) {
		return m[x] = func(x + 1) - countOnes(x + 1);
	}
	return m[x] = x / 2 + func(x / 2) + func(x / 2 - 1);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	long long a, b;
	cin >> a >> b;

	cout << func(b) - func(a - 1) << endl;

	return 0;
}