[BOJ/백준][Gold4] 1407 : 2로 몇 번 나누어질까 (C++)

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

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

 

 

[난이도] Gold4
[유형] 이분탐색

[풀이]
규칙성을 찾아서 수학적 수식으로 푸는것이 정해인 것 같은데
무식하게 이분탐색으로 풀었습니다.

A<= x <=B 인 x에 대해
x가 2^k * p (k>=1) 꼴로 나타내지는 것들에 대해서는 2^k 만큼 더해주면 됩니다.

결국 B를 넘지 않는 모든 2^k에 대해
A<= 2^k * p <=B 를 만족하도록 하는 p의 범위를 구해주면 됩니다.

이를 이분탐색으로 구할 수 있습니다.
A<= 2^k * left <= 2^k* right <= B
A보다 크거나 같게 만드는 left, B보다 작거나 같게 만드는 right를 이분탐색으로 각각 구하면
right-left+1 만큼이 A<= 2^k * p <=B 를 만족하는 p의 개수가 됩니다.
결국 정답 ans에 2^k * (right-left+1)를 더해주면 됩니다.

주의할 것이 k의 최댓값부터 반대로 검사를 해주면서 acnt (정답에 포함된 A<= x <= B 인 x의 개수) 를 누적해주어야 합니다. 2^k 에서 답에 누적된 x들은 2^(k-1) 에 반드시 포함되므로 이것을 빼줘야 하기 때문입니다.
그래서 right-left+1 대신 right-left+1-acnt를 사용하였습니다.

 

 

#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
ll A,B;
ll bsearch(ll v,ll lo,ll hi,ll c,bool left){
    while(lo+1<hi){
        ll mid = (lo+hi)/2;
        if(v*mid>c) hi=mid;
        else if(v*mid<=c) lo=mid;
    }
    if(left){
        if(lo*v<c) lo++;
    }else{
        if(lo*v>c) lo--;
    }
    return lo;
}
int main(){
    scanf("%lld%lld",&A,&B);

    vector<ll> vec;
    for(ll i=2;;i*=2){
       if(i>B) break;
       vec.push_back(i);
    }
    ll ans=0,acnt=0;
    for(int i=vec.size()-1;i>=0;i--){
        ll v = vec[i];
        ll lo=1,hi=(1e15+2)/v;
        ll left = bsearch(v,lo,hi,A,1);
        ll right = bsearch(v,lo,hi,B,0);
        if(left<=right && v*left>=A && v*right<=B) {
            ll cur = right-left+1-acnt;
            acnt+=cur;
            ans+=cur*v;
        }
    }
    printf("%lld",ans+(B-A+1-acnt));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1407.cpp