백준 1407번, 2로 몇 번 나누어질까 풀이

문제

백준 1407번

풀이

구간 $[A, B]$를 1씩 증가 시켜보면서 확인하는 방법이 가장 확실하지만, 수의 제한이 무려 $10^{15}$이니 더 빠른 방법을 찾아야 합니다.

 

우리가 관심 있는 것은 구간 $[A, B]$에서 $2^k$의 배수의 개수입니다.

어떤 수, $k$가 주어졌을 때, 구간 $[A,B]$ 내에서 $k$의 배수의 개수는 $B/k-(A-1)/k$라는 수식을 통해 $O(1)$로 구할 수 있습니다. (단, $A \leq B$)

 

두번째, $2^{k+1}$의 배수는 모두 $2^k$의 배수입니다. 예를 들면, $32(2^5)$과 같은 수는 $16(2^4)$의 배수임에 동시에 $8, 4, 2, 1$의 배수이기도 합니다. 즉, $2^k$의 배수는 모두 $2^i (i=0,1,...,k)$의 배수라고 나타낼 수 있습니다.

 

정리하면, 구간 $[A,B]$에서 $2^k\ (k=0,1,2,...,50)$의 배수의 개수를 구하되, 중복되는 수는 빼야 합니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	ll a, b;
	cin >> a >> b;
	--a;

	ll ans = 0, sum = 0;
	for (ll i = 50; i >= 0; i--) { //중복 제거를 위해 위에서부터 봐줌
		ll curr = 1LL << i; //2^i 계산, 오버플로 유의
		ll val = b / curr - a / curr; //[a, b] 사이에서 2^i 배수의 개수를 구함
		val -= sum; //중복 제거
		sum += val; //2^i의 배수를 2^(i-1), 2^(i-2)...에서도 계산하지 않도록 뺌
		ans += val * curr; //중복이 제거된 배수의 개수 * 2^i
	}

	cout << ans;
}