백준 2로 몇 번 나누어질까(1407)

2로 몇 번 나누어질까

1. 힌트

1) $g(x) = \displaystyle\sum_{k=1}^{x}f(k)$로 정의하면 $\displaystyle\sum_{k=A}^{B}f(k)\to g(B)-g(A - 1)$로 생각할 수 있습니다.

2) $f(x)$를 나열해보면 $g(x)$를 구하는데 규칙을 찾을 수 있습니다.

2. 접근

1) $g(x)$

$f(x)$를 빨리 구하기 위해서 $f(x)$의 규칙을 찾으려고 해봤지만 좀 복잡합니다. $g(x) = \displaystyle\sum_{k=1}^{x}f(k)$로 정의하면 $\displaystyle\sum_{k=A}^{B}f(k)\to g(B)-g(A - 1)$로 생각할 수 있습니다. $g(x)$에서 규칙을 찾아서 빠르게 구하는 것을 구현해봅시다.

$f(x)$를 나열해보겠습니다.
$f(x) = 1,\ 2,\ 1,\ 4,\ 1,\ 2,\ 1,\ 8$
$g(x)$는 $f(x)$의 누적 합처럼 이해할 수 있는데, $g(x)$는 $x$보다 작은거나 같은 모든 $2$의 거듭제곱들로 $x$를 나눈 몫들의 합입니다.
그런데 $1$로 나눈 몫들의 합은 $2$로 나눈 몫들의 합에 포함되므로 중복을 제거해줄 필요가 있습니다.
$\displaystyle\sum_{i=0} (2^i - 2^{i - 1}) \times (x / 2^i)$를 구하면 됩니다.
$i=0$인 경우는 $(2^i) \times (x / 2^i)$로 예외처리해줍시다.

3. 구현

public class Main {
	static long[] cache = new long[64];
	
	// 2^x
	static long pow(int x) {
		if (x == -1) return 0;
		if (x == 0) return 1;
		if (cache[x] != 0) return cache[x];
		if (x % 2 == 1) return cache[x] = 2 * pow(x - 1);
		return cache[x] = pow(x / 2) * pow(x / 2);
	}
	
	static long g(long x) {
		long ret = 0;
		for (int i = 0; pow(i) <= x; i++)
			ret += (pow(i) - pow(i - 1)) * (x / pow(i));
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Long A = Long.parseLong(st.nextToken());
		Long B = Long.parseLong(st.nextToken());
		System.out.println(g(B) - g(A - 1));
	}

}