This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub plasmatic1/templates
#pragma once #include "template.hpp" template <typename T = int64_t> struct Fraction { T n, d; void reduce() { T gv = __gcd(abs(n), abs(d)); n /= gv; d /= gv; if (d < 0) { n *= -1; d *= -1; } } Fraction(T a, T b) : n(a), d(b) { reduce(); } Fraction(T x) : n(x), d(1) { reduce(); } Fraction inv() const { return Fraction(d, n); } Fraction neg() const { return Fraction(-n, d); } Fraction mul(Fraction f) const { return Fraction(n * f.n, d * f.d); } Fraction div(Fraction f) const { return mul(f.inv()); } Fraction add(Fraction f) const { return Fraction(n * f.d + f.n * d, d * f.d); } Fraction sub(Fraction f) const { return add(f.neg()); } bool operator==(const Fraction o) const { return n == o.n && d == o.d; } bool operator!=(const Fraction o) const { return n != o.n || d != o.d; } bool operator<(const Fraction o) const { return n * o.d < o.n * d; } bool operator>(const Fraction o) const { return o < *this; } bool operator<=(const Fraction o) const { return !(o < *this); } bool operator>=(const Fraction o) const { return !(*this < o); } }; ostream& operator<<(ostream &out, const Fraction o) { out << o.n << " / " << o.d; return out; }
#line 2 "template.hpp" #include <bits/stdc++.h> #define DEBUG 1 using namespace std; // Defines #define fs first #define sn second #define pb push_back #define eb emplace_back #define mpr make_pair #define mtp make_tuple #define all(x) (x).begin(), (x).end() // Basic type definitions #if __cplusplus == 201703L // CPP17 only things template <typename T> using opt_ref = optional<reference_wrapper<T>>; // for some templates #endif using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<long long, long long>; #ifdef __GNUG__ // PBDS order statistic tree #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T, class comp = less<T>> using os_tree = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>; template <typename K, typename V, class comp = less<K>> using treemap = tree<K, V, comp, rb_tree_tag, tree_order_statistics_node_update>; // HashSet #include <ext/pb_ds/assoc_container.hpp> template <typename T, class Hash> using hashset = gp_hash_table<T, null_type, Hash>; template <typename K, typename V, class Hash> using hashmap = gp_hash_table<K, V, Hash>; const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); struct chash { ll operator()(ll x) const { return x ^ RANDOM; } }; #endif // More utilities int SZ(string &v) { return v.length(); } template <typename C> int SZ(C &v) { return v.size(); } template <typename C> void UNIQUE(vector<C> &v) { sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); } template <typename T, typename U> void maxa(T &a, U b) { a = max(a, b); } template <typename T, typename U> void mina(T &a, U b) { a = min(a, b); } const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f; #line 3 "fraction.cpp" template <typename T = int64_t> struct Fraction { T n, d; void reduce() { T gv = __gcd(abs(n), abs(d)); n /= gv; d /= gv; if (d < 0) { n *= -1; d *= -1; } } Fraction(T a, T b) : n(a), d(b) { reduce(); } Fraction(T x) : n(x), d(1) { reduce(); } Fraction inv() const { return Fraction(d, n); } Fraction neg() const { return Fraction(-n, d); } Fraction mul(Fraction f) const { return Fraction(n * f.n, d * f.d); } Fraction div(Fraction f) const { return mul(f.inv()); } Fraction add(Fraction f) const { return Fraction(n * f.d + f.n * d, d * f.d); } Fraction sub(Fraction f) const { return add(f.neg()); } bool operator==(const Fraction o) const { return n == o.n && d == o.d; } bool operator!=(const Fraction o) const { return n != o.n || d != o.d; } bool operator<(const Fraction o) const { return n * o.d < o.n * d; } bool operator>(const Fraction o) const { return o < *this; } bool operator<=(const Fraction o) const { return !(o < *this); } bool operator>=(const Fraction o) const { return !(*this < o); } }; ostream& operator<<(ostream &out, const Fraction o) { out << o.n << " / " << o.d; return out; }