BOJ 15224 EvenOdd

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

15224번: EvenOdd

 

어떤 정수 $x$에 특정한 연산을 반복해서 취할 때, $x$가 1일 될 때까지 취해야 하는 연산의 갯수를 $f(x)$라고 정의해봅시다. 이 때 두 수 $l$과 $r$이 주어졌을 때, $f(l) + f(l + 1) + \cdots + f(r - 1) + f(r)$의  값을 구해야 합니다. 이런 식의 문제를 풀 때 유효하게 생각해 볼 수 있는 접근 방법이 있는데, $f(1) + f(2) + \cdots + f(x-1) + f(x)$을 $g(x)$라고 할 때 $g(r) - g(l-1)$로 문제를 치환하는 것입니다. $g(x)$를 빠르게 구할 수 있다면, 우리가 찾고자 하는 답도 빠르게 구할 수 있다는 뜻이 됩니다.

 

그렇다면 이 문제에서 $g(x)$를 어떻게 빠르게 구할 수 있을까요? 저도 그렇고 제 주변의 여러 사람들도 그랬듯이 2를 나누는 연산을 여러번 반복하니까 2진법으로 나타냈을 때의 비트를 가지고 어떻게 잘 하면 되지 않을까 싶어집니다. 하지만 이렇게 접근하면 정답에 다가가기 상당히 어려워집니다. 이 문제의 경우 2진법으로 접근하기보다는 홀짝을 나눠서 생각하는 접근을 통해 풀 수 있습니다.

 

$g(x)$를 풀어서 쓰면 (당연하게도) $f(1) + f(2) + \cdots + f(x-1) + f(x)$입니다. 이를 홀짝을 나눠서 적어보면 ($x$가 짝수일 경우) $f(1) + f(3) + \cdots + f(x - 3) + f(x-1)$와 $f(2) + f(4) + \cdots + f(x-2) + f(x)$를 더한 값입니다. 이 때 1을 제외한 임의의 홀수 $k$에 대하여 $f(k) = f(k+1) + 1$이 됩니다. 이를 이용해 앞의 식을 정리하면 $(0 + f(4) + \cdots + f(x-2) + f(x) + (x / 2 + 1))$ $+$ $(f(2) + f(4) + \cdots + f(x-2) + f(x))$ $=$ $0 + (f(4) + \cdots + f(x-2) + f(x)) *2 + f(2)$라는 식이 나옵니다. 이 식을 재귀적으로 계산해주면 답을 구할 수 있습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>

#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long

const int MOD = 1e9 + 7;

using namespace std;

int T, l, r;

int calc(int x) {
    if (x == 0 || x == 1) return 0;
    if (x == 2) return 1;
    int ret = 0;
    while (x > 1) {
        if (x % 2) x++;
        else x /= 2;
        ret++;
    }
    return ret;
}

int func(int x) {
    if (!x) return 0;
    if (x == 1) return 0;

    int ret = x / 2 - 1;
    ret -= 1;
    ret += ((func(x / 2) % MOD + (x / 2) % MOD) % MOD) * 2;
    if (x % 2) ret += calc(x);

    return ret % MOD;
}

int32_t main(void) {
    FastIO;

#ifdef HN
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    T = 1;
    //cin >> T;

    while (T--) {
        cin >> l >> r;
        int ans = func(r) - func(l - 1);
        if (ans < 0) ans += MOD;
        cout << ans << endl;
    }

    return 0;
}