electicode
HomeCoursesResourcesProblemsNational OlympiadContestsLeaderboard
...
Problems/Bukhara Avenue/Editorial

Editorial: Bukhara Avenue

Let f(x)f(x)f(x) the number of integers in [1,x][1, x][1,x], which are not divisible by 333 and 555. It can be calculated using the idea of inclusion and exclusion principle.

Now, one can see, that f(x)≤f(x+1)f(x) \leq f(x + 1)f(x)≤f(x+1) holds, and thus, binary search on answer can be applied. I.e. it is required to find minimum value of xxx, that f(x)=nf(x) = nf(x)=n.

← Back to Problem
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

long long f(long long x) {
    return x - (x / 3 + x / 5 - x / 15);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    long long n;
    cin >> n;
    long long l = 1, r = 1e18;
    while (l < r) {
        long long m = (l + r) / 2;
        if (f(m) >= n) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    cout << l << "\n";
}