취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1407번 문제인 2로 몇 번 나누어질까 이다.

문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/1407 

A 이상 B 이하의 수 중 (2의 k거듭제곱)의 배수가 몇 개인지 세는 것은 어렵지 않다.

먼저 모든 수는 2의 0 거듭제곱의 배수이니 A 이상 B 이하의 각 수 k마다 f(k)의 값이 최소 1 이상일 것임을 알 수 있다. 각 k마다 1씩 값을 답에 더해주자.

또한, 2의 1 거듭제곱의 배수인 k에 대해서는 f(k)의 값이 최소 2 이상일 것일 것임을 알 수 있다. 앞선 단계에서 f(k)값의 일부인 1씩은 이미 더했으므로, 2의 1 거듭제곱의 배수인 k 개수만큼 1씩만을 답에 더해주자.

마찬가지로, 2의 2 거듭제곱의 배수인 k에 대해서는 f(k)의 값이 최소 4 이상일 것일 것임을 알 수 있다. 앞선 단계에서 f(k)값의 일부인 2씩은 이미 더했으므로, 2의 1 거듭제곱의 배수인 k 개수만큼 2씩만을 답에 더해주자.

위의 과정을 반복하는 것으로 이 문제는 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

typedef long long ll;

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

	ll L, R; cin >> L >> R; L--;
	ll ans = R - L;
	ll exp = 1LL << 60;
	while (exp > 1) {
		ll lcnt = L / exp, rcnt = R / exp;
		ans += (rcnt - lcnt) * (exp >> 1);
		exp >>= 1;
	}

	cout << ans;
}