// ratio standard header (core)
#pragma once
#ifndef _RATIO_
#define _RATIO_
#ifndef RC_INVOKED
#include <stdint.h>
#include <type_traits>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,_STL_WARNING_LEVEL)
 #pragma warning(disable: _STL_DISABLED_WARNINGS)
 _STL_DISABLE_CLANG_WARNINGS
 #pragma push_macro("new")
 #undef new

_STD_BEGIN
	// STRUCT TEMPLATE _Abs
template<intmax_t _Val>
	struct _Abs
		: integral_constant<intmax_t, (_Val < 0 ? -_Val : _Val)>
	{	// computes absolute value of _Val
	};

	// STRUCT TEMPLATE _Safe_mult
template<intmax_t _Ax,
	intmax_t _Bx,
	bool _Sfinae = false,
	bool _Good = (_Abs<_Ax>::value <= INTMAX_MAX / (_Bx == 0 ? 1 : _Abs<_Bx>::value))>
	struct _Safe_mult
		: integral_constant<intmax_t, _Ax * _Bx>
	{	// computes _Ax * _Bx without overflow
	};

template<intmax_t _Ax,
	intmax_t _Bx,
	bool _Sfinae>
	struct _Safe_mult<_Ax, _Bx, _Sfinae, false>
	{	// _Ax * _Bx would overflow
	static_assert(_Sfinae,
		"integer arithmetic overflow");
	};

	// STRUCT TEMPLATE _Sign_of
template<intmax_t _Val>
	struct _Sign_of
		: integral_constant<intmax_t, (_Val < 0 ? -1 : 1)>
	{	// computes sign of _Val
	};

	// STRUCT TEMPLATE _Safe_add
template<intmax_t _Ax,
	intmax_t _Bx,
	bool _Good,
	bool _Also_good>
	struct _Safe_addX
		: integral_constant<intmax_t, _Ax + _Bx>
	{	// computes _Ax + _Bx without overflow
	};

template<intmax_t _Ax,
	intmax_t _Bx>
	struct _Safe_addX<_Ax, _Bx, false, false>
	{	// _Ax + _Bx would overflow
	static_assert(_Always_false<_Safe_addX>,
		"integer arithmetic overflow");
	};

template<intmax_t _Ax,
	intmax_t _Bx>
	struct _Safe_add
		: _Safe_addX<_Ax, _Bx,
			_Sign_of<_Ax>::value != _Sign_of<_Bx>::value,
			(_Abs<_Ax>::value <= INTMAX_MAX - _Abs<_Bx>::value)>::type
	{	// computes _Ax + _Bx, forbids overflow
	};

	// STRUCT TEMPLATE _Gcd
template<intmax_t _Ax,
	intmax_t _Bx>
	struct _GcdX
		: _GcdX<_Bx, _Ax % _Bx>::type
	{	// computes greatest common divisor of _Ax and _Bx
	};

template<intmax_t _Ax>
	struct _GcdX<_Ax, 0>
		: integral_constant<intmax_t, _Ax>
	{	// computes greatest common divisor of _Ax and 0
	};

template<intmax_t _Ax,
	intmax_t _Bx>
	struct _Gcd
		: _GcdX<_Abs<_Ax>::value, _Abs<_Bx>::value>::type
	{	// computes greatest common divisor of abs(_Ax) and abs(_Bx)
	};

template<>
	struct _Gcd<0, 0>
		: integral_constant<intmax_t, 1>	// contrary to mathematical convention
	{	// avoids division by 0 in ratio_less
	};

	// STRUCT TEMPLATE ratio
template<intmax_t _Nx,
	intmax_t _Dx = 1>
	struct ratio
	{	// holds the ratio of _Nx to _Dx
	static_assert(_Dx != 0,
		"zero denominator");
	static_assert(-INTMAX_MAX <= _Nx,
		"numerator too negative");
	static_assert(-INTMAX_MAX <= _Dx,
		"denominator too negative");

	static constexpr intmax_t num = _Sign_of<_Nx>::value
		* _Sign_of<_Dx>::value * _Abs<_Nx>::value / _Gcd<_Nx, _Dx>::value;

	static constexpr intmax_t den = _Abs<_Dx>::value / _Gcd<_Nx, _Dx>::value;

	typedef ratio<num, den> type;
	};

	// VARIABLE TEMPLATE _Is_ratio_v
template<class _Ty>
	_INLINE_VAR constexpr bool _Is_ratio_v = false;	// test for ratio type

template<intmax_t _R1,
	intmax_t _R2>
	_INLINE_VAR constexpr bool _Is_ratio_v<ratio<_R1, _R2>> = true;

	// ALIAS TEMPLATE ratio_add
template<class _R1,
	class _R2>
	struct _Ratio_add
	{	// add two ratios
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_add<R1, R2> requires R1 and R2 to be ratio<>s.");

	static constexpr intmax_t _N1 = _R1::num;
	static constexpr intmax_t _D1 = _R1::den;
	static constexpr intmax_t _N2 = _R2::num;
	static constexpr intmax_t _D2 = _R2::den;

	static constexpr intmax_t _Gx = _Gcd<_D1, _D2>::value;

	// typename ratio<>::type is necessary here
	typedef typename ratio<
		_Safe_add<
			_Safe_mult<_N1, _D2 / _Gx>::value,
			_Safe_mult<_N2, _D1 / _Gx>::value
			>::value,
		_Safe_mult<_D1, _D2 / _Gx>::value
		>::type type;
	};

template<class _R1,
	class _R2>
	using ratio_add = typename _Ratio_add<_R1, _R2>::type;

	// ALIAS TEMPLATE ratio_subtract
template<class _R1,
	class _R2>
	struct _Ratio_subtract
	{	// subtract two ratios
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_subtract<R1, R2> requires R1 and R2 to be ratio<>s.");

	static constexpr intmax_t _N2 = _R2::num;
	static constexpr intmax_t _D2 = _R2::den;

	typedef ratio_add<_R1, ratio<-_N2, _D2>> type;
	};

template<class _R1,
	class _R2>
	using ratio_subtract = typename _Ratio_subtract<_R1, _R2>::type;

	// ALIAS TEMPLATE ratio_multiply
template<class _R1,
	class _R2>
	struct _Ratio_multiply
	{	// multiply two ratios
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_multiply<R1, R2> requires R1 and R2 to be ratio<>s.");

	static constexpr intmax_t _N1 = _R1::num;
	static constexpr intmax_t _D1 = _R1::den;
	static constexpr intmax_t _N2 = _R2::num;
	static constexpr intmax_t _D2 = _R2::den;

	static constexpr intmax_t _Gx = _Gcd<_N1, _D2>::value;
	static constexpr intmax_t _Gy = _Gcd<_N2, _D1>::value;

	typedef _Safe_mult<_N1 / _Gx, _N2 / _Gy, true> _Num;
	typedef _Safe_mult<_D1 / _Gy, _D2 / _Gx, true> _Den;
	};

template<class _R1,
	class _R2,
	bool _Sfinae = true,
	class = void>
	struct _Ratio_multiply_sfinae
	{	// detect overflow during multiplication
	static_assert(_Sfinae,
		"integer arithmetic overflow");
	};

template<class _R1,
	class _R2,
	bool _Sfinae>
	struct _Ratio_multiply_sfinae<_R1, _R2, _Sfinae, void_t<
		typename _Ratio_multiply<_R1, _R2>::_Num::type,
		typename _Ratio_multiply<_R1, _R2>::_Den::type>>
	{	// typename ratio<>::type is unnecessary here
	typedef ratio<
		_Ratio_multiply<_R1, _R2>::_Num::value,
		_Ratio_multiply<_R1, _R2>::_Den::value> type;
	};

template<class _R1,
	class _R2>
	using ratio_multiply = typename _Ratio_multiply_sfinae<_R1, _R2, false>::type;

	// ALIAS TEMPLATE ratio_divide
template<class _R1,
	class _R2>
	struct _Ratio_divide
	{	// divide two ratios
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_divide<R1, R2> requires R1 and R2 to be ratio<>s.");

	static constexpr intmax_t _N2 = _R2::num;
	static constexpr intmax_t _D2 = _R2::den;

	typedef ratio<_D2, _N2> _R2_inverse;
	};

template<class _R1,
	class _R2,
	bool _Sfinae = true>
	using _Ratio_divide_sfinae = typename _Ratio_multiply_sfinae<
		_R1, typename _Ratio_divide<_R1, _R2>::_R2_inverse, _Sfinae>::type;

template<class _R1,
	class _R2>
	using ratio_divide = _Ratio_divide_sfinae<_R1, _R2, false>;

	// STRUCT TEMPLATE ratio_equal
template<class _R1,
	class _R2>
	struct ratio_equal
		: bool_constant<_R1::num == _R2::num && _R1::den == _R2::den>
	{	// tests if ratio == ratio
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
	};

template<class _R1,
	class _R2>
	_INLINE_VAR constexpr bool ratio_equal_v = ratio_equal<_R1, _R2>::value;

	// STRUCT TEMPLATE ratio_not_equal
template<class _R1,
	class _R2>
	struct ratio_not_equal
		: bool_constant<!ratio_equal_v<_R1, _R2>>
	{	// tests if ratio != ratio
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_not_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
	};

template<class _R1,
	class _R2>
	_INLINE_VAR constexpr bool ratio_not_equal_v = ratio_not_equal<_R1, _R2>::value;

	// STRUCT TEMPLATE ratio_less
struct _Big_uint128
	{
	uint64_t _Upper;
	uint64_t _Lower;

	constexpr bool operator<(const _Big_uint128 _Rhs) const noexcept
		{
		if (_Upper != _Rhs._Upper)
			{
			return (_Upper < _Rhs._Upper);
			}

		return (_Lower < _Rhs._Lower);
		}
	};

constexpr _Big_uint128 _Big_multiply(const uint64_t _Lfactor, const uint64_t _Rfactor) noexcept
	{	// multiply two 64-bit integers into a 128-bit integer, Knuth's algorithm M
	const uint64_t _Llow = _Lfactor & 0xFFFF'FFFFULL;
	const uint64_t _Lhigh = _Lfactor >> 32;
	const uint64_t _Rlow = _Rfactor & 0xFFFF'FFFFULL;
	const uint64_t _Rhigh = _Rfactor >> 32;

	uint64_t _Temp = _Llow * _Rlow;
	const uint64_t _Lower32 = _Temp & 0xFFFF'FFFFULL;
	uint64_t _Carry = _Temp >> 32;

	_Temp = _Llow * _Rhigh + _Carry;
	const uint64_t _Mid_lower = _Temp & 0xFFFF'FFFFULL;
	const uint64_t _Mid_upper = _Temp >> 32;

	_Temp = _Lhigh * _Rlow + _Mid_lower;
	_Carry = _Temp >> 32;

	return {_Lhigh * _Rhigh + _Mid_upper + _Carry, (_Temp << 32) + _Lower32};
	}

constexpr bool _Ratio_less(const int64_t _N1, const int64_t _D1,
		const int64_t _N2, const int64_t _D2) noexcept
	{
	if (_N1 >= 0 && _N2 >= 0)
		{
		return (_Big_multiply(static_cast<uint64_t>(_N1), static_cast<uint64_t>(_D2))
			< _Big_multiply(static_cast<uint64_t>(_N2), static_cast<uint64_t>(_D1)));
		}

	if (_N1 < 0 && _N2 < 0)
		{
		return (_Big_multiply(static_cast<uint64_t>(-_N2), static_cast<uint64_t>(_D1))
			< _Big_multiply(static_cast<uint64_t>(-_N1), static_cast<uint64_t>(_D2)));
		}

	return (_N1 < _N2);
	}

template<class _R1,
	class _R2>
	struct ratio_less
		: bool_constant<_Ratio_less(_R1::num, _R1::den, _R2::num, _R2::den)>
	{	// tests if ratio < ratio
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_less<R1, R2> requires R1 and R2 to be ratio<>s.");
	};

template<class _R1,
	class _R2>
	_INLINE_VAR constexpr bool ratio_less_v = ratio_less<_R1, _R2>::value;

	// STRUCT TEMPLATE ratio_less_equal
template<class _R1,
	class _R2>
	struct ratio_less_equal
		: bool_constant<!ratio_less_v<_R2, _R1>>
	{	// tests if ratio <= ratio
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_less_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
	};

template<class _R1,
	class _R2>
	_INLINE_VAR constexpr bool ratio_less_equal_v = ratio_less_equal<_R1, _R2>::value;

	// STRUCT TEMPLATE ratio_greater
template<class _R1,
	class _R2>
	struct ratio_greater
		: ratio_less<_R2, _R1>::type
	{	// tests if ratio > ratio
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_greater<R1, R2> requires R1 and R2 to be ratio<>s.");
	};

template<class _R1,
	class _R2>
	_INLINE_VAR constexpr bool ratio_greater_v = ratio_greater<_R1, _R2>::value;

	// STRUCT TEMPLATE ratio_greater_equal
template<class _R1,
	class _R2>
	struct ratio_greater_equal
		: bool_constant<!ratio_less_v<_R1, _R2>>
	{	// tests if ratio >= ratio
	static_assert(_Is_ratio_v<_R1> && _Is_ratio_v<_R2>,
		"ratio_greater_equal<R1, R2> requires R1 and R2 to be ratio<>s.");
	};

template<class _R1,
	class _R2>
	_INLINE_VAR constexpr bool ratio_greater_equal_v = ratio_greater_equal<_R1, _R2>::value;

	// SI TYPEDEFS
typedef ratio<1, 1000000000000000000LL> atto;
typedef ratio<1, 1000000000000000LL> femto;
typedef ratio<1, 1000000000000LL> pico;
typedef ratio<1, 1000000000> nano;
typedef ratio<1, 1000000> micro;
typedef ratio<1, 1000> milli;
typedef ratio<1, 100> centi;
typedef ratio<1, 10> deci;
typedef ratio<10, 1> deca;
typedef ratio<100, 1> hecto;
typedef ratio<1000, 1> kilo;
typedef ratio<1000000, 1> mega;
typedef ratio<1000000000, 1> giga;
typedef ratio<1000000000000LL, 1> tera;
typedef ratio<1000000000000000LL, 1> peta;
typedef ratio<1000000000000000000LL, 1> exa;
_STD_END
 #pragma pop_macro("new")
 _STL_RESTORE_CLANG_WARNINGS
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _RATIO_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */