#924638 (C++17) No.2266 Fractions (hard)

提出ソース

結果

問題	No.2266 Fractions (hard)
ユーザー	rogi52
提出日時	2023-10-31 17:43:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	998 ms / 6,000 ms
コード長	13,831 bytes
コンパイル時間	2,832 ms
コンパイル使用メモリ	220,060 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-25 17:42:09
合計ジャッジ時間	14,284 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	17 ms 5,248 KB
testcase_01	AC	616 ms 5,376 KB
testcase_02	AC	236 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	9 ms 5,376 KB
testcase_05	AC	6 ms 5,248 KB
testcase_06	AC	42 ms 5,376 KB
testcase_07	AC	20 ms 5,376 KB
testcase_08	AC	6 ms 5,376 KB
testcase_09	AC	3 ms 5,376 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	10 ms 5,376 KB
testcase_13	AC	523 ms 5,376 KB
testcase_14	AC	115 ms 5,376 KB
testcase_15	AC	129 ms 5,376 KB
testcase_16	AC	532 ms 5,376 KB
testcase_17	AC	417 ms 5,376 KB
testcase_18	AC	621 ms 5,376 KB
testcase_19	AC	619 ms 5,376 KB
testcase_20	AC	105 ms 5,376 KB
testcase_21	AC	664 ms 5,376 KB
testcase_22	AC	313 ms 5,376 KB
testcase_23	AC	146 ms 5,376 KB
testcase_24	AC	147 ms 5,376 KB
testcase_25	AC	843 ms 5,376 KB
testcase_26	AC	147 ms 5,376 KB
testcase_27	AC	594 ms 5,376 KB
testcase_28	AC	146 ms 5,376 KB
testcase_29	AC	146 ms 5,376 KB
testcase_30	AC	147 ms 5,376 KB
testcase_31	AC	146 ms 5,376 KB
testcase_32	AC	533 ms 5,376 KB
testcase_33	AC	2 ms 5,376 KB
testcase_34	AC	387 ms 5,376 KB
testcase_35	AC	354 ms 5,376 KB
testcase_36	AC	998 ms 5,376 KB
testcase_37	AC	768 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "stern-brocot_tree_search.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2262"

#line 2 "/Users/korogi/Desktop/cp-library/src/cp-template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull  = unsigned long long;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
template < class T > bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template < class T > bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template < class T, class U > T ceil (T x, U y) { return (x > 0 ? (x + y - 1) / y :           x / y); }
template < class T, class U > T floor(T x, U y) { return (x > 0 ?           x / y : (x - y + 1) / y); }

#line 2 "/Users/korogi/Desktop/cp-library/src/utility/rep_itr.hpp"
template < class T > struct itr_rep {
    T i, d;
    constexpr itr_rep(const T i) noexcept : i(i), d(1) {}
    constexpr itr_rep(const T i, const T d) noexcept : i(i), d(d) {}
    void operator++() noexcept { i += d; }
    constexpr int operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr_rep x) const noexcept { return d > 0 ? i < x.i : i > x.i; }
};

template < class T > struct rep {
    const itr_rep< T > s, t;
    constexpr rep(const T t) noexcept : s(0), t(t) {}
    constexpr rep(const T s, const T t) noexcept : s(s), t(t) {}
    constexpr rep(const T s, const T t, const T d) noexcept : s(s, d), t(t, d) {}
    constexpr auto begin() const noexcept { return s; }
    constexpr auto end  () const noexcept { return t; }
};

template < class T > struct revrep {
    const itr_rep < T > s, t;
    constexpr revrep(const T t) noexcept : s(t - 1, -1), t(-1, -1) {}
    constexpr revrep(const T s, const T t) noexcept : s(t - 1, -1), t(s - 1, -1) {}
    constexpr revrep(const T s, const T t, const T d) noexcept : s(t - 1, -d), t(s - 1, -d) {}
    constexpr auto begin() const noexcept { return s; }
    constexpr auto end  () const noexcept { return t; }
};
#line 3 "/Users/korogi/Desktop/cp-library/src/utility/io.hpp"

/* 128bit integer */
istream& operator>>(istream& is, i128& x) {
    std::string s; is >> s;
    int pm = (s[0] == '-');
    x = 0;
    for(int i : rep(pm, int(s.size()))) x = x * 10 + (s[i] - '0');
    if(pm) x *= -1;
    return is;
}
ostream& operator<<(ostream& os, const i128& x) {
    if(x == 0) return os << x;
    i128 y = x;
    if(y < 0) {
        os << '-';
        y *= -1;
    }
    std::vector<int> ny;
    while(y > 0) {
        ny.push_back(y % 10);
        y /= 10;
    }
    for(int i : revrep(ny.size())) os << ny[i];
    return os;
}

namespace scanner {
    struct sca {
        template < class T > operator T() {
            T s; std::cin >> s; return s;
        }
    };
    struct vec {
        int n;
        vec(int n) : n(n) {}
        template < class T > operator std::vector< T >() {
            std::vector< T > v(n);
            for(T& x : v) std::cin >> x;
            return v;
        }
    };
    struct mat {
        int h, w;
        mat(int h, int w) : h(h), w(w) {}
        template < class T > operator std::vector< std::vector< T > >() {
            std::vector m(h, std::vector< T >(w));
            for(std::vector< T >& v : m) for(T& x : v) std::cin >> x;
            return m;
        }
    };
    struct speedup {
        speedup() {
            std::cin.tie(0);
            std::ios::sync_with_stdio(0);
        }
    } speedup_instance;
}
scanner::sca in() { return scanner::sca(); }
scanner::vec in(int n) { return scanner::vec(n); }
scanner::mat in(int h, int w) { return scanner::mat(h, w); }

namespace printer {
    void precision(int d) { std::cout << std::fixed << std::setprecision(d); }
    void flush() { std::cout.flush(); }
}

template < class T >
ostream& operator<<(ostream& os, const std::vector< T > a) {
    int n = a.size();
    for(int i : rep(n)) { os << a[i]; if(i != n - 1) os << ' '; }
    return os;
}

int print() { std::cout << '\n'; return 0; }
template < class head, class... tail > int print(head&& h, tail&&... t) {
    std::cout << h; if(sizeof...(tail)) std::cout << ' ';
    return print(std::forward<tail>(t)...);
}
template < class T > int print_n(const std::vector< T > a) {
    int n = a.size();
    for(int i : rep(n)) std::cout << a[i] << "\n";
    return 0;
}


#line 2 "/Users/korogi/Desktop/cp-library/src/utility/key_val.hpp"

template < class K, class V >
struct key_val {
    K key; V val;
    key_val() {}
    key_val(K key, V val) : key(key), val(val) {}
    template < std::size_t Index >
    std::tuple_element_t< Index, key_val >& get() {
        if constexpr (Index == 0) return key;
        if constexpr (Index == 1) return val;
    }
};

namespace std {

template < class K, class V > struct tuple_size < key_val< K, V > > : integral_constant< size_t, 2 > {};
template < class K, class V > struct tuple_element < 0, key_val< K, V > > { using type = K; };
template < class K, class V > struct tuple_element < 1, key_val< K, V > > { using type = V; };

}
#line 2 "/Users/korogi/Desktop/cp-library/src/utility/vec_op.hpp"
template < class T > key_val< int, T > max_of(const vector< T >& a) {
    int i = std::max_element(a.begin(), a.end()) - a.begin();
    return {i, a[i]};
}
template < class T > key_val< int, T > min_of(const vector< T >& a) {
    int i = std::min_element(a.begin(), a.end()) - a.begin();
    return {i, a[i]};
}
template < class S, class T > S sum_of(const vector< T >& a) {
    S sum = 0;
    for(const T x : a) sum += x;
    return sum;
}
template < class S, class T > vector< S > freq_of(const vector< T >& a, T L, T R) {
    vector< S > res(R - L, S(0));
    for(const T x : a) res[x - L] += 1;
    return res;
}
template < class S, class T > struct prefix_sum {
    vector< S > s;
    prefix_sum(const vector< T >& a) : s(a) {
        s.insert(s.begin(), S(0));
        for(int i : rep(a.size())) s[i + 1] += s[i];
    }
    // [L, R)
    S sum(int L, int R) { return s[R] - s[L]; }
};
#line 3 "/Users/korogi/Desktop/cp-library/src/utility/heap.hpp"

template < class T > using heap_min = std::priority_queue< T, std::vector< T >, std::greater< T > >;
template < class T > using heap_max = std::priority_queue< T, std::vector< T >, std::less< T > >;

#line 23 "/Users/korogi/Desktop/cp-library/src/cp-template.hpp"

#line 1 "/Users/korogi/Desktop/cp-library/src/algorithm/bin_search.hpp"
template < class T, class F >
T bin_search(T ok, T ng, F& f) {
    while(abs(ok - ng) > 1) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template < class T, class F >
T bin_search_real(T ok, T ng, F& f, int step = 80) {
    while(step--) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
#line 2 "/Users/korogi/Desktop/cp-library/src/algorithm/argsort.hpp"

template < class T > std::vector< int > argsort(const std::vector< T > &a) {
    std::vector< int > ids((int)a.size());
    std::iota(ids.begin(), ids.end(), 0);
    std::sort(ids.begin(), ids.end(), [&](int i, int j) {
        return a[i] < a[j] || (a[i] == a[j] && i < j);
    });
    return ids;
}
#line 2 "/Users/korogi/Desktop/cp-library/src/number/stern-brocot_tree.hpp"

template < class T >
T sgn(T x) {
    return (0 < x) - (x < 0);
}

template < class I >
class stern_brocot_tree_node {
    struct fraction {
        I upper, lower;
        fraction(I upper = 0, I lower = 1) : upper(upper), lower(lower) {}
        fraction& operator+=(const fraction& r) {
            this->upper += r.upper;
            this->lower += r.lower;
            return *this;
        }
        fraction& operator-=(const fraction& r) {
            this->upper -= r.upper;
            this->lower -= r.lower;
            return *this;
        }
        fraction& operator*=(I v) {
            this->upper *= v;
            this->lower *= v;
            return *this;
        }
        fraction operator+(const fraction& r) const { return fraction(*this) += r; }
        fraction operator-(const fraction& r) const { return fraction(*this) -= r; }
        fraction operator*(I v) { return fraction(*this) *= v; }
    };
    fraction L, M, R;

  public:
    std::vector< I > history;
    I depth;

    stern_brocot_tree_node() : L(0, 1), M(1, 1), R(1, 0), depth(0) {}
    stern_brocot_tree_node(I a, I b) : stern_brocot_tree_node() {
        assert(1 <= a);
        assert(1 <= b);
        I s = a < b ? -1 : +1;
        if(s == -1) std::swap(a, b);
        for(; b != 0; s *= -1) {
            auto [q, r] = std::div(a, b);
            down(s * (q - (r == 0)));
            a = b, b = r;
        }
    }
    stern_brocot_tree_node(std::vector< I > history) : stern_brocot_tree_node() {
        for(I k : history) down(k);
        assert(this->history == history);
    }
    using sbt_n = stern_brocot_tree_node< I >;

    std::pair< I, I > value()       { return std::make_pair(M.upper, M.lower); }
    std::pair< I, I > lower_bound() { return std::make_pair(L.upper, L.lower); }
    std::pair< I, I > upper_bound() { return std::make_pair(R.upper, R.lower); }

    void down_left(I k) {
        assert(1 <= k);
        std::tie(L, M, R)
            = std::make_tuple(L, L * k + M, L * (k - 1) + M);
        history.push_back(-k);
        depth += k;
    }
    void down_right(I k) {
        assert(1 <= k);
        std::tie(L, M, R)
            = std::make_tuple(R * (k - 1) + M, R * k + M, R);
        history.push_back(+k);
        depth += k;
    }
    void down(I k) {
        switch(sgn(k)) {
            case  0: return;
            case -1: return down_left (-k);
            case +1: return down_right(+k);
        }
    }
    void up(I k) {
        assert(0 <= k and k <= depth);
        while(k != 0) {
            I x = std::min(k, std::abs(history.back()));
            if(history.back() > 0) {
                std::tie(L, M, R)
                    = std::make_tuple(L - R * x, L - R * (x - 1), R);
                history.back() -= x;
            } else {
                std::tie(L, M, R)
                    = std::make_tuple(L, R - L * (x - 1), R - L * x);
                history.back() += x;
            }
            if(history.back() == 0) history.pop_back();
            k -= x;
            depth -= x;
        }
    }
    friend sbt_n lca(const sbt_n& L, const sbt_n& R) {
        sbt_n M;
        for(int i : rep(min(L.history.size(), R.history.size()))) {
            I Lx = L.history[i], Rx = R.history[i];
            if(sgn(Lx) == sgn(Rx)) {
                M.down(sgn(Lx) * std::min(abs(Lx), abs(Rx)));
                if(Lx != Rx) break;
            } else break;
        }
        return M;
    }
};

template < class I, class F >
std::pair< I, I > sbt_search(const I N, const F& f) {
    assert(1 <= N);
    if(f({0, 1})) return {0, 1};

    stern_brocot_tree_node< I > sbt_n;
    auto over = [&]() {
        auto [a, b] = sbt_n.value();
        return std::max(a, b) > N;
    };
    int sgn = f(sbt_n.value()) ? -1 : +1;
    auto ng = [&]() { return over() or f(sbt_n.value()) == (sgn > 0); };

    while(true) {
        I x = 1;
        while(true) {
            sbt_n.down(x * sgn);
            if(ng()) { sbt_n.up(x); break; }
            x *= 2;
        }
        x /= 2;
        while(x > 0) {
            sbt_n.down(x * sgn);
            if(ng()) sbt_n.up(x);
            x /= 2;
        }
        sbt_n.down(sgn);
        if(over()) return sbt_n.upper_bound();
        sgn *= -1;
    }
}
#line 2 "/Users/korogi/Desktop/cp-library/src/algorithm/floor_sum.hpp"

// sum_{i in [0, n)} floor((a * i + b) / m) 
ll floor_sum(ll n, ll m, ll a, ll b) {
    if(n == 0) return ll(0);
    ll ans = 0;
    ans += (n - 1) * n / 2 * (a / m), a %= m;
    ans += n * (b / m), b %= m;
    ll y_max = a * n + b;
    ans += floor_sum(y_max / m, a, m, y_max % m);
    return ans;
}
#line 1 "/Users/korogi/Desktop/cp-library/src/algorithm/enumrate_quotient.hpp"
// x in [L, R), floor(N/x) == Q
template < class T, class F >
void for_each_quotient(T N, const F& f) {
    for(T L = 1; L <= N;) {
        T Q = N / L, R = N / Q + 1;
        f(L, R, Q);
        L = R;
    }
}
#line 7 "stern-brocot_tree_search.test.cpp"

int main() {
    ll N = in(), K = in();

    /* Mertens */
    const ll B = 10'000;
    std::vector<ll> bs(N / B + 1, 1), gs(B + 1, 1), vis(N / B + 1, 0);
    bs[0] = gs[0] = 0;
    for(ll i : rep(2LL, N / B + 1)) if(not vis[i]) {
        bs[i] *= -1;
        for(ll j : rep(2*i, N / B + 1, i)) {
            vis[j] = 1;
            if((j / i) % i == 0)
                bs[j] = 0;
            else
                bs[j] *= -1;
        }
    }
    for(ll i : rep(1LL, N / B)) bs[i + 1] += bs[i];
    for(ll i : revrep(1LL, B + 1)) {
        for(ll L = 2; L <= N / i; ) {
            ll Q = N / (i * L), R = N / (i * Q) + 1;
            gs[i] -= (i * L <= B ? gs[i * L] : bs[N / (i * L)]) * (R - L);
            L = R;
        }
    }
    auto M = [&](ll x) {
        if(x < ll(bs.size())) {
            return bs[x];
        } else {
            return gs[N / x];
        }
    };

    auto count = [&](std::pair<ll,ll> x) {
        ll ans = 0;
        ll upper, lower; std::tie(upper, lower) = x;
        for_each_quotient(N, [&](ll L, ll R, ll Q) {
            ans += M(Q) * (floor_sum(R, lower, upper, 0) - floor_sum(L, lower, upper, 0));
        });
        return ans;
    };

    ll C = count({N - 1, N});
    if(K == C + 1) return print("1/1");

    bool rev = false;
    if(K <= C) {}
    else if(K <= 2 * C + 1) {
        rev = true;
        K = 2 * C + 2 - K;
    } else {
        return print(-1);
    }

    auto [f, g] = sbt_search(N, [&](std::pair<ll,ll> x) {
        return count(x) >= K;
    });

    if(rev) std::swap(f, g);
    std::cout << f << "/" << g << std::endl;
}