[백준 알고리즘] 백준 9527 c++

시간 제한, 수의 범위를 유의 하여 비트마스킹으로 문제를 풀어야 한다.

 

주요 점화식 >>

-  비트 자릿수가 i 일때, 그 이전 값들의 총 비트 수를 구하는 점화식

 

d[i]=d[i−1]+d[i]=d[i−1]+(ii번 비트를 뺀 나머지 반복되는 수들의 1의 개수) ++ (i번째 비트에 나타나는 1의 수) 

 

#include <iostream>
#include <cmath>

long long a, b;
long long d[55];

long long go(long long x, long long i = 54) {
    long long ans = x & 1;
    for (; i > 0; i--) {
        if (x & (1LL << i)) {
            ans += d[i - 1] + (x - (1LL << i) + 1);
            x -= 1LL << i;
        }
    }
    return ans;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    d[0] = 1;
    for (long long i = 1; i < 55; i++) {
        d[i] = d[i - 1] * 2 + (1LL << i);
    }
    std::cin >> a >> b;
    std::cout << go(b) - go(a - 1);
}