1. 2^n 마다 규칙이 있음
2. f(n)을 2^n ~ 2^(n+1)-1 에서의 1의 개수라고 한다면, f(n) = 2^n + f(i) ( 0 <= i <= n-1 ) 이 성립한다.
3. 그리고 들어오는 수 A,B에 대해
(1~B 까지의 1의 개수) - (1~A-1 까지의 1의 개수) 를 하면 값이 나온다.
4. 2에서의 규칙에따라 end가 주어지면 0에서 end까지의 1의 개수를 구하는 함수를 선언한다.
-> 이때 end 미만의 최대 2^n의 n를 구한다.
-> 2에서의 규칙에 따라 0~n까지의 f(n)을 구한다.
-> 그럼 나머지 2^(n+1) ~ end 에서의 1의 개수를 구하면 된다.
5. 나머지를 구하는 함수를 선언한다. 2^(n+1)에서 end까지 구하면 된다.
-> 이때 2^(n+1) ~ end 사이의 값들의 맨앞은 전부 1이고, 개수는 end - 2^(n+1) + 1이다.
-> 그리고 그 맨앞의 1을 떼고 보면, 0부터 end - 2^(n+1) 까지의 이진수 분포와 동일하다
-> 따라서 다시 end - 2^(n+1)을 위 4번 함수에 넣으면 된다.
코드
#include <iostream>#include <cmath>using namespace std;long long a, b;long long DP[55];long long getN(int N);long long countOne(long long end);long long getRest(long long start, long long end);int main() { cin >> a >> b; DP[0] = 1; cout << countOne(b) - countOne(a-1) << endl;}long long countOne(long long end) { if (end <= 2) return end; int n = 0; long long temp = 1; while (temp < end) { temp *= 2; n++; } if (temp - end <=1) n -= 1; else n -= 2; long long result = 0; for (int i = 0; i <= n; i++) result += getN(i); result += getRest(pow(2, n+1), end); return result;}long long getN(int N) { if (N == 0) return 1; if (DP[N] != 0) return DP[N]; long long result = pow(2, N); for (int i = N - 1; i >= 0; i--) result += getN(i); return DP[N] = result;}long long getRest(long long start, long long end) { if (start > end) return 0; return end - start + 1 + countOne(end - start);}