fraction.hpp¶
提供规范化的 64 位有理数四则与比较；适合必须精确保存分数、不能用浮点的题目。
\[
\displaystyle x = p/q
\]
Complexity: Time: \(O(\log \max (\lvert \mathrm{num}\rvert , \mathrm{den}))\) construction/arithmetic; \(O(1)\) comparison. Space: \(O(1)\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log max(|num|,den)) construction/arithmetic; O(1) comparison.
/// Space: O(1).
#include <cassert>
#include <compare>
#include <cstdint>
#include <limits>
#include <numeric>
namespace noya {
/// @brief Normalized signed 64-bit rational number; arithmetic results must fit
/// int64, while comparison and intermediate products use signed 128-bit.
struct fraction {
std::int64_t num = 0;
std::int64_t den = 1;
fraction() = default;
fraction(std::int64_t nx, std::int64_t dx = 1) : num(nx), den(dx) {
normalize();
}
void normalize() {
assert(den != 0);
auto g = std::gcd(magnitude(num), magnitude(den));
*this = from_reduced(__int128(num) / g, __int128(den) / g);
}
friend bool operator==(const fraction &, const fraction &) = default;
friend std::strong_ordering operator<=>(const fraction &a,
const fraction &b) {
__int128 l = __int128(a.num) * b.den;
__int128 r = __int128(b.num) * a.den;
return l < r ? std::strong_ordering::less
: l > r ? std::strong_ordering::greater
: std::strong_ordering::equal;
}
friend fraction operator+(const fraction &a, const fraction &b) {
return add(a, b, 1);
}
friend fraction operator-(const fraction &a, const fraction &b) {
return add(a, b, -1);
}
friend fraction operator*(const fraction &a, const fraction &b) {
auto g = std::gcd(magnitude(a.num), std::uint64_t(b.den));
auto h = std::gcd(magnitude(b.num), std::uint64_t(a.den));
return from_reduced(__int128(a.num / std::int64_t(g)) * (b.num / std::int64_t(h)),
__int128(a.den / std::int64_t(h)) * (b.den / std::int64_t(g)));
}
friend fraction operator/(const fraction &a, const fraction &b) {
assert(b.num != 0);
auto g = std::gcd(magnitude(a.num), magnitude(b.num));
auto h = std::gcd(a.den, b.den);
return from_reduced((__int128(a.num) / g) * (b.den / h),
(__int128(b.num) / g) * (a.den / h));
}
friend fraction operator-(const fraction &val) {
return from_reduced(-__int128(val.num), val.den);
}
private:
static std::uint64_t magnitude(std::int64_t n) {
return n < 0 ? std::uint64_t(0) - std::uint64_t(n) : std::uint64_t(n);
}
static fraction add(const fraction &a, const fraction &b, int sgn) {
auto g = std::gcd(a.den, b.den);
auto ad = a.den / g, bd = b.den / g;
__int128 n = __int128(a.num) * bd + sgn * __int128(b.num) * ad;
// Coprime ad and bd leave only factors of g to cancel.
auto h = std::gcd(std::int64_t(n % g), g);
return from_reduced(n / h, __int128(ad) * (b.den / h));
}
static fraction from_reduced(__int128 n, __int128 d) {
assert(d != 0);
if (d < 0) {
n = -n;
d = -d;
}
assert(n >= std::numeric_limits<std::int64_t>::lowest() &&
n <= std::numeric_limits<std::int64_t>::max() &&
d <= std::numeric_limits<std::int64_t>::max());
fraction res;
res.num = std::int64_t(n);
res.den = std::int64_t(d);
return res;
}
};
} // namespace noya
// NOYA_FRACTION_HPP
#ifndef NOYA_FRACTION_HPP
#define NOYA_FRACTION_HPP 1
/// @complexity Time: O(log max(|num|,den)) construction/arithmetic; O(1) comparison.
/// Space: O(1).
#include <cassert>
#include <compare>
#include <cstdint>
#include <limits>
#include <numeric>
namespace noya {
/// @brief Normalized signed 64-bit rational number; arithmetic results must fit
/// int64, while comparison and intermediate products use signed 128-bit.
struct fraction {
std::int64_t num = 0;
std::int64_t den = 1;
fraction() = default;
fraction(std::int64_t nx, std::int64_t dx = 1) : num(nx), den(dx) {
normalize();
}
void normalize() {
assert(den != 0);
auto g = std::gcd(magnitude(num), magnitude(den));
*this = from_reduced(__int128(num) / g, __int128(den) / g);
}
friend bool operator==(const fraction &, const fraction &) = default;
friend std::strong_ordering operator<=>(const fraction &a,
const fraction &b) {
__int128 l = __int128(a.num) * b.den;
__int128 r = __int128(b.num) * a.den;
return l < r ? std::strong_ordering::less
: l > r ? std::strong_ordering::greater
: std::strong_ordering::equal;
}
friend fraction operator+(const fraction &a, const fraction &b) {
return add(a, b, 1);
}
friend fraction operator-(const fraction &a, const fraction &b) {
return add(a, b, -1);
}
friend fraction operator*(const fraction &a, const fraction &b) {
auto g = std::gcd(magnitude(a.num), std::uint64_t(b.den));
auto h = std::gcd(magnitude(b.num), std::uint64_t(a.den));
return from_reduced(__int128(a.num / std::int64_t(g)) * (b.num / std::int64_t(h)),
__int128(a.den / std::int64_t(h)) * (b.den / std::int64_t(g)));
}
friend fraction operator/(const fraction &a, const fraction &b) {
assert(b.num != 0);
auto g = std::gcd(magnitude(a.num), magnitude(b.num));
auto h = std::gcd(a.den, b.den);
return from_reduced((__int128(a.num) / g) * (b.den / h),
(__int128(b.num) / g) * (a.den / h));
}
friend fraction operator-(const fraction &val) {
return from_reduced(-__int128(val.num), val.den);
}
private:
static std::uint64_t magnitude(std::int64_t n) {
return n < 0 ? std::uint64_t(0) - std::uint64_t(n) : std::uint64_t(n);
}
static fraction add(const fraction &a, const fraction &b, int sgn) {
auto g = std::gcd(a.den, b.den);
auto ad = a.den / g, bd = b.den / g;
__int128 n = __int128(a.num) * bd + sgn * __int128(b.num) * ad;
// Coprime ad and bd leave only factors of g to cancel.
auto h = std::gcd(std::int64_t(n % g), g);
return from_reduced(n / h, __int128(ad) * (b.den / h));
}
static fraction from_reduced(__int128 n, __int128 d) {
assert(d != 0);
if (d < 0) {
n = -n;
d = -d;
}
assert(n >= std::numeric_limits<std::int64_t>::lowest() &&
n <= std::numeric_limits<std::int64_t>::max() &&
d <= std::numeric_limits<std::int64_t>::max());
fraction res;
res.num = std::int64_t(n);
res.den = std::int64_t(d);
return res;
}
};
} // namespace noya
#endif // NOYA_FRACTION_HPP
/// @complexity Time: O(log max(|num|,den)) construction/arithmetic; O(1) comparison.
/// Space: O(1).
#include <cassert>
#include <compare>
#include <cstdint>
#include <limits>
#include <numeric>
namespace noya {
/// @brief Normalized signed 64-bit rational number; arithmetic results must fit
/// int64, while comparison and intermediate products use signed 128-bit.
struct fraction {
std::int64_t num = 0;
std::int64_t den = 1;
fraction() = default;
fraction(std::int64_t nx, std::int64_t dx = 1) : num(nx), den(dx) {
normalize();
}
void normalize() {
assert(den != 0);
auto g = std::gcd(magnitude(num), magnitude(den));
*this = from_reduced(__int128(num) / g, __int128(den) / g);
}
friend bool operator==(const fraction &, const fraction &) = default;
friend std::strong_ordering operator<=>(const fraction &a,
const fraction &b) {
__int128 l = __int128(a.num) * b.den;
__int128 r = __int128(b.num) * a.den;
return l < r ? std::strong_ordering::less
: l > r ? std::strong_ordering::greater
: std::strong_ordering::equal;
}
friend fraction operator+(const fraction &a, const fraction &b) {
return add(a, b, 1);
}
friend fraction operator-(const fraction &a, const fraction &b) {
return add(a, b, -1);
}
friend fraction operator*(const fraction &a, const fraction &b) {
auto g = std::gcd(magnitude(a.num), std::uint64_t(b.den));
auto h = std::gcd(magnitude(b.num), std::uint64_t(a.den));
return from_reduced(__int128(a.num / std::int64_t(g)) * (b.num / std::int64_t(h)),
__int128(a.den / std::int64_t(h)) * (b.den / std::int64_t(g)));
}
friend fraction operator/(const fraction &a, const fraction &b) {
assert(b.num != 0);
auto g = std::gcd(magnitude(a.num), magnitude(b.num));
auto h = std::gcd(a.den, b.den);
return from_reduced((__int128(a.num) / g) * (b.den / h),
(__int128(b.num) / g) * (a.den / h));
}
friend fraction operator-(const fraction &val) {
return from_reduced(-__int128(val.num), val.den);
}
private:
static std::uint64_t magnitude(std::int64_t n) {
return n < 0 ? std::uint64_t(0) - std::uint64_t(n) : std::uint64_t(n);
}
static fraction add(const fraction &a, const fraction &b, int sgn) {
auto g = std::gcd(a.den, b.den);
auto ad = a.den / g, bd = b.den / g;
__int128 n = __int128(a.num) * bd + sgn * __int128(b.num) * ad;
// Coprime ad and bd leave only factors of g to cancel.
auto h = std::gcd(std::int64_t(n % g), g);
return from_reduced(n / h, __int128(ad) * (b.den / h));
}
static fraction from_reduced(__int128 n, __int128 d) {
assert(d != 0);
if (d < 0) {
n = -n;
d = -d;
}
assert(n >= std::numeric_limits<std::int64_t>::lowest() &&
n <= std::numeric_limits<std::int64_t>::max() &&
d <= std::numeric_limits<std::int64_t>::max());
fraction res;
res.num = std::int64_t(n);
res.den = std::int64_t(d);
return res;
}
};
} // namespace noya
// NOYA_FRACTION_HPP