[18265] MooBuzz

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

18265번: MooBuzz

함수 f(x)가 x번째까지 게임을 진행했을때, 숫자의 등장 횟수를 return 한다고 생각해보면,

선형에 불가능하니 이분탐색으로 답을 찾아볼 수 있다.

실제로는 f(x)==n인 최소의 x를 찾아야 하므로, f(x)가 n이면 x가 5의 배수도, 3의 배수도 아닐때동안 x를 감소시킨다.

f()자체는 포함배제의 원리로, x-(x/3)-(x/5)+(x/15);로 구현할 수 있다. 

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

ll n, ans;

ll f(ll mid) {

    ll ret = mid;

    ll a = mid / 3LL, b = mid / 5LL, c = mid / 15LL;

    ret = ret - a - b + c;

    return ret;

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    ll s = 1, e = 1e14;

    ans = e;

    while (s <= e) {

        ll mid = s + e >> 1LL;

        ll ret = f(mid);

        if (ret == n) {

            while (1) {

                if (mid % 3 != 0 && mid % 5 != 0) break;

                mid--;

            }

            cout << mid;

            return 0;

        }

        if (ret > n)

            e = mid - 1;

        else

            s = mid + 1;

    }

    return 0;

}

---