1407 2로 몇 번 나누어질까

A 이상 B 이하의 자연수에 대해서, 각 수와 2의 거듭제곱 과의 공약수 중에 가장 큰 공약수를 골라서 그 수들을 합쳤을때의 결과를 묻는 문제이다.
문제에 주어진대로 풀면 범위가 매우 커서 TLE가 발생한다.
이 문제는 범위로 생각하는게 좋다.
a~b 범위중에 2의 배수의 갯수, 4의 배수의 갯수, ... 2^n(<=b)의 배수의 갯수를 구해서 합쳐줘야한다.
단, 갯수를 구하는 문제가 아니라 실제 수들을 합쳤을때의 결과를 묻기 때문에, 주의해야 한다.
예를들면 4는 2의 배수에도 속하고 4의배수에도 속하기 때문에 2의 배수였을때의 경우를 빼주고 4의배수로 갱신해야 한다.

또 하나 신경써줘야 할것은 A가 2^n의 배수가 아닐경우, A에서 가장 가까운 수부터 그 숫자를 정해야 할탠데, 그 방법은
a를 2^n 으로 나누고, 그 값을 올림 해준다음 2^n으로 곱하면 된다.

소스