[ boj : 1407 ] 2로 몇 번 나누어질까

www.acmicpc.net/problem/1407

1407번: 2로 몇 번 나누어질까

문제 : f(n)의 정의가 주어지고 a와 b의 자연수가 주어질때 a~b까지 f(a)~f(b)를 구하시오

 

해설 : 자 이런 xxx같은 문제....(괜히 그러는 겁니다 저가 못나서)

한번 봐봅시다.

먼저 항상 단순하게 생각을 해봅시다. 그냥 a부터 b까지 전부 수들을 보면서 2로 나누어주고 개수를 세고 다 더하면 되겠죠. 그러나....항상 문제는 저희에게 편하게 풀도록 내버려 두지 않습니다. n의 범위가 10^15이니....절대로 안된다는 것을 알수 있습니다.

그러면 우린 다른 방법을 생각을 해봐야하는데 '규칙성'이 있을거라는 '믿음'을 가지고 한번 문제를 바라봅시다.

먼저 n이 주어졌을때 2로 한번도 나눌수 없는 개수를 한번 확인해 보면 ceil(n/2) 의 개수만큼 있습니다.

 

n=10

1 = 2^0

2 = 2^1

3 = 2^0

4 = 2^2

5 = 2^0

6 = 2^1

7 = 2^0

8 = 2^3

9 = 2^0

10 = 2^1

 

=>5개

 

그럼 이 5개를 제외한 수들은 반드시 2로 한번은 나누어지게 됩니다.(n까지의 수들중 2로 한번도 나누어지지 않은 수들을 제외한 것 이니까요) 이 수들 중 2로 단 한번만 나누어지는 수들의 개수는 어떻게 구할까요???또 다시 ceil(n을 2로 나눈 몫/2) 가 됩니다.

 

n=10

1 = 2^0

2 = 2^1

3 = 2^0

4 = 2^2

5 = 2^0

6 = 2^1

7 = 2^0

8 = 2^3

9 = 2^0

10 = 2^1

 

이걸 다시 정리해 보면

n=10

2 = 2^1

4 = 2^2

6 = 2^1

8 = 2^3

10 = 2^1

 

로 후보를 줄일 수 있을 것이고 이 중 2로 단 한번만 나눌 수 있는 수들은 2,6,10 으로 3개가 됩니다.

이 3개의 수는 ceil(n-ceil(n/2) / 2) 의 개수가 된다는 것을 알 수 있죠.

그 다음 2로 2번을 나눌 수 있는 개수는? 

5개의 후보중 2^1의 개수를 제외한 2개 중에서 /2 의 개수가 해당 되겠죠? -> 1개

나머지도 마찬가지 입니다 ㅎㅎ. 그럼 끝난것 입니다.

 

F(A)를 f(1) + f(2) + ...... + f(A-1) + f(A) 라고 정의를 한다면

F(B) - F(A-1) = f(A) + f(A+1) +.......+f(B-1)+f(B) 가 됩니다. 이를 이용해서 그대로 코드로 옮겨주면 됩니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll f(ll x);

int main()
{
	ll a, b,c;
	ll x = 1, A = 0, B = 0;
	cin >> a >> b;
	
	cout << f(b) - f(a - 1);
	return 0;
}
ll f(ll x)
{
	ll ret=0,y;
	for(ll i=1; x>0; x-=y,i*=2) {
		if (x & 1)y = x / 2 + 1;
		else y = x / 2;
		ret += y * i;
	}
	return ret;
}