#1407 2로 몇 번 나누어질까(Mathematics)

이번 문제는 주어진 수 n를 나눌 수 있는 최대 2의 거듭제곱수를 구하고, 일정 범위의 수에 대하여 그 거듭제곱수의 합을 구해야 하는 문제입니다.  난이도는 Gold IV로 높지는 않습니다.

 

n이란 수가 12라면 12를 나눌 수 있는 최대 2의 거듭제곱수는 4이므로 f(12) = 4가 됩니다.

 

또는 다음과 같이 해도 됩니다.  n이란 수를 나눌 수 있는 최대 2의 거듭제곱수는 n을 2진수로 표현했을 때, 가장 오른쪽 1의 위치이다와 동일합니다.  12는 2진수로 1100이므로, 가장 오른쪽 1을 찾게되면 2진수로 100이 되고, 이 값은 4가 됩니다.  그리고 이것을 C 언어에서는 비트연산자를 이용해서 간단하게 계산할 수 있습니다.  x & (-x) 를 계산하면 가장 오른쪽 비트를 얻게 됩니다.

 

하지만 이 문제는 숫자의 범위가 꽤 크기 때문에 이렇게 계산해서는 안 됩니다.  10의 15승정도의 숫자는 아주 큰 숫자입니다.

 

이것을 풀기 위해서는 2의 거듭제곱으로 나누어서 처리하면 됩니다.  1부터 n까지의 범위의 숫자를 나눌 수 있는 최대 2의 거듭제곱수의 합은 다음과 같은 식으로 구할 수 있습니다.

 

\[ F(n) = \sum_{k=0}^{\infty} 2^{k-1} \lfloor \frac{n}{2^k} \rfloor \]

 

a에서부터 b까지 범위라면, \( F(b) - F(a-1) \) 을 구하면 됩니다.  10의 15승이면, 위 식을 돌기 위해서 최대 50번정도이니, 아주 짧은 시간에 계산을 완료할 수 있습니다.  그리고 당연히 long long 변수 타입을 사용해야 합니다.

 

제가 작성한 소스입니다.

 

//----------------------------------------------------------
//  baekjoon #1407 - zvrk
//    - by Aubrey Choi
//    - created at 2019-02-26
//----------------------------------------------------------
#include <stdio.h>

long long f(long long n)
{
  long long r=n;
  for(long i=2;i<=n;i*=2) r+=(n/i)*(i/2);
  return r;
}

int main()
{
  long long a, b;
  scanf("%lld%lld",&a,&b);
  printf("%lld\n", f(b)-f(a-1));
}