#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 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 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(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 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(B + 1, 1LL)) { 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 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 x) { return count(x) >= K; }); if(rev) std::swap(f, g); print(f, g); }