[Codeforces] 768B: Code For 1

https://codeforces.com/problemset/problem/768/B

 

이 문제는 쉽게 말하면 자연수 n을 받으면 n으로 비트열을 만드는 문제이다.

(x mod 2 : x를 2로 나눈 나머지)

 

문자열을 다 구할 수는 없다. n이 2의 50승까지 가능하기때문에.

희한한 방법으로 풀어야한다.

n, l, r이 주어졌을 때 재귀로 풀어낼 것이다.

 

C++ 코드

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

long long solve(long long n, long long l, long long r) {
    long long temp, len, mid;
    temp = n / 2;
    len = 1;
    while (temp > 0) {
        len = len*2 + 1;
        temp /= 2;
    }
    // 전부일 경우
    if (l == 1 && r == len)
        return n;

    // 중간 포인트
    mid = (len+1)/2;
    if (l > mid) return solve(n/2, l - mid, r - mid);
    if (r < mid) return solve(n/2, l, r);
    if (l == mid && r == mid) return n % 2;
    if (l == mid) return solve(n/2, 1, r - mid) + n % 2;
    if (r == mid) return solve(n/2 , l, mid - 1) + n % 2;
    return solve(n/2, l, mid-1) + solve(n/2, 1, r - mid) + n % 2;
}

int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    long long n, l, r;
    cin >> n >> l >> r;
    cout << solve(n, l, r);

    return 0;
}