?????????? ????????? - ??????????????? - /home/agenciai/public_html/cd38d8/integer.zip
???????
PK ^�[� �M� � static_log2.hppnu �[��� // -------------- Boost static_log2.hpp header file ----------------------- // // // Copyright (C) 2001 Daryle Walker. // Copyright (C) 2003 Vesa Karvonen. // Copyright (C) 2003 Gennaro Prota. // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // --------------------------------------------------- // See http://www.boost.org/libs/integer for documentation. // ------------------------------------------------------------------------- // #ifndef BOOST_INTEGER_STATIC_LOG2_HPP #define BOOST_INTEGER_STATIC_LOG2_HPP #include <boost/config.hpp> #include <boost/integer_fwd.hpp> namespace boost { namespace detail { namespace static_log2_impl { // choose_initial_n<> // // Recursively doubles its integer argument, until it // becomes >= of the "width" (C99, 6.2.6.2p4) of // static_log2_argument_type. // // Used to get the maximum power of two less then the width. // // Example: if on your platform argument_type has 48 value // bits it yields n=32. // // It's easy to prove that, starting from such a value // of n, the core algorithm works correctly for any width // of static_log2_argument_type and that recursion always // terminates with x = 1 and n = 0 (see the algorithm's // invariant). typedef boost::static_log2_argument_type argument_type; typedef boost::static_log2_result_type result_type; template <result_type n> struct choose_initial_n { BOOST_STATIC_CONSTANT(bool, c = (argument_type(1) << n << n) != 0); BOOST_STATIC_CONSTANT( result_type, value = !c*n + choose_initial_n<2*c*n>::value ); }; template <> struct choose_initial_n<0> { BOOST_STATIC_CONSTANT(result_type, value = 0); }; // start computing from n_zero - must be a power of two const result_type n_zero = 16; const result_type initial_n = choose_initial_n<n_zero>::value; // static_log2_impl<> // // * Invariant: // 2n // 1 <= x && x < 2 at the start of each recursion // (see also choose_initial_n<>) // // * Type requirements: // // argument_type maybe any unsigned type with at least n_zero + 1 // value bits. (Note: If larger types will be standardized -e.g. // unsigned long long- then the argument_type typedef can be // changed without affecting the rest of the code.) // template <argument_type x, result_type n = initial_n> struct static_log2_impl { BOOST_STATIC_CONSTANT(bool, c = (x >> n) > 0); // x >= 2**n ? BOOST_STATIC_CONSTANT( result_type, value = c*n + (static_log2_impl< (x>>c*n), n/2 >::value) ); }; template <> struct static_log2_impl<1, 0> { BOOST_STATIC_CONSTANT(result_type, value = 0); }; } } // detail // -------------------------------------- // static_log2<x> // ---------------------------------------- template <static_log2_argument_type x> struct static_log2 { BOOST_STATIC_CONSTANT( static_log2_result_type, value = detail::static_log2_impl::static_log2_impl<x>::value ); }; template <> struct static_log2<0> { }; } #endif // include guard PK ^�['O� � extended_euclidean.hppnu �[��� /* * (C) Copyright Nick Thompson 2018. * Use, modification and distribution are subject to the * Boost Software License, Version 1.0. (See accompanying file * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) */ #ifndef BOOST_INTEGER_EXTENDED_EUCLIDEAN_HPP #define BOOST_INTEGER_EXTENDED_EUCLIDEAN_HPP #include <limits> #include <stdexcept> #include <boost/throw_exception.hpp> #include <boost/core/swap.hpp> #include <boost/core/enable_if.hpp> namespace boost { namespace integer { // From "The Joy of Factoring", Algorithm 2.7, with a small optimization to remove tmps from Wikipedia. // Solves mx + ny = gcd(m,n). Returns tuple with (gcd(m,n), x, y). template<class Z> struct euclidean_result_t { Z gcd; Z x; Z y; }; template<class Z> typename boost::enable_if_c< std::numeric_limits< Z >::is_signed, euclidean_result_t< Z > >::type extended_euclidean(Z m, Z n) { if (m < 1 || n < 1) { BOOST_THROW_EXCEPTION(std::domain_error("extended_euclidean: arguments must be strictly positive")); } bool swapped = false; if (m < n) { swapped = true; boost::swap(m, n); } Z u0 = m; Z u1 = 1; Z u2 = 0; Z v0 = n; Z v1 = 0; Z v2 = 1; Z w0; Z w1; Z w2; while(v0 > 0) { Z q = u0/v0; w0 = u0 - q*v0; w1 = u1 - q*v1; w2 = u2 - q*v2; u0 = v0; u1 = v1; u2 = v2; v0 = w0; v1 = w1; v2 = w2; } euclidean_result_t< Z > result; result.gcd = u0; if (!swapped) { result.x = u1; result.y = u2; } else { result.x = u2; result.y = u1; } return result; } }} #endif PK ^�[�V,f� � integer_mask.hppnu �[��� // Boost integer/integer_mask.hpp header file ------------------------------// // (C) Copyright Daryle Walker 2001. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // See http://www.boost.org for updates, documentation, and revision history. #ifndef BOOST_INTEGER_INTEGER_MASK_HPP #define BOOST_INTEGER_INTEGER_MASK_HPP #include <boost/integer_fwd.hpp> // self include #include <boost/config.hpp> // for BOOST_STATIC_CONSTANT #include <boost/integer.hpp> // for boost::uint_t #include <climits> // for UCHAR_MAX, etc. #include <cstddef> // for std::size_t #include <boost/limits.hpp> // for std::numeric_limits // // We simply cannot include this header on gcc without getting copious warnings of the kind: // // boost/integer/integer_mask.hpp:93:35: warning: use of C99 long long integer constant // // And yet there is no other reasonable implementation, so we declare this a system header // to suppress these warnings. // #if defined(__GNUC__) && (__GNUC__ >= 4) #pragma GCC system_header #endif namespace boost { // Specified single-bit mask class declaration -----------------------------// // (Lowest bit starts counting at 0.) template < std::size_t Bit > struct high_bit_mask_t { typedef typename uint_t<(Bit + 1)>::least least; typedef typename uint_t<(Bit + 1)>::fast fast; BOOST_STATIC_CONSTANT( least, high_bit = (least( 1u ) << Bit) ); BOOST_STATIC_CONSTANT( fast, high_bit_fast = (fast( 1u ) << Bit) ); BOOST_STATIC_CONSTANT( std::size_t, bit_position = Bit ); }; // boost::high_bit_mask_t // Specified bit-block mask class declaration ------------------------------// // Makes masks for the lowest N bits // (Specializations are needed when N fills up a type.) #ifdef BOOST_MSVC #pragma warning(push) #pragma warning(disable:4310) // cast truncates constant value #endif template < std::size_t Bits > struct low_bits_mask_t { typedef typename uint_t<Bits>::least least; typedef typename uint_t<Bits>::fast fast; BOOST_STATIC_CONSTANT( least, sig_bits = least(~(least(~(least( 0u ))) << Bits )) ); BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits ); }; // boost::low_bits_mask_t #ifdef BOOST_MSVC #pragma warning(pop) #endif #define BOOST_LOW_BITS_MASK_SPECIALIZE( Type ) \ template < > struct low_bits_mask_t< std::numeric_limits<Type>::digits > { \ typedef std::numeric_limits<Type> limits_type; \ typedef uint_t<limits_type::digits>::least least; \ typedef uint_t<limits_type::digits>::fast fast; \ BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) ); \ BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); \ BOOST_STATIC_CONSTANT( std::size_t, bit_count = limits_type::digits ); \ } #ifdef BOOST_MSVC #pragma warning(push) #pragma warning(disable:4245) // 'initializing' : conversion from 'int' to 'const boost::low_bits_mask_t<8>::least', signed/unsigned mismatch #endif BOOST_LOW_BITS_MASK_SPECIALIZE( unsigned char ); #if USHRT_MAX > UCHAR_MAX BOOST_LOW_BITS_MASK_SPECIALIZE( unsigned short ); #endif #if UINT_MAX > USHRT_MAX BOOST_LOW_BITS_MASK_SPECIALIZE( unsigned int ); #endif #if ULONG_MAX > UINT_MAX BOOST_LOW_BITS_MASK_SPECIALIZE( unsigned long ); #endif #if defined(BOOST_HAS_LONG_LONG) #if ((defined(ULLONG_MAX) && (ULLONG_MAX > ULONG_MAX)) ||\ (defined(ULONG_LONG_MAX) && (ULONG_LONG_MAX > ULONG_MAX)) ||\ (defined(ULONGLONG_MAX) && (ULONGLONG_MAX > ULONG_MAX)) ||\ (defined(_ULLONG_MAX) && (_ULLONG_MAX > ULONG_MAX))) BOOST_LOW_BITS_MASK_SPECIALIZE( boost::ulong_long_type ); #endif #elif defined(BOOST_HAS_MS_INT64) #if 18446744073709551615ui64 > ULONG_MAX BOOST_LOW_BITS_MASK_SPECIALIZE( unsigned __int64 ); #endif #endif #ifdef BOOST_MSVC #pragma warning(pop) #endif #undef BOOST_LOW_BITS_MASK_SPECIALIZE } // namespace boost #endif // BOOST_INTEGER_INTEGER_MASK_HPP PK ^�[~;��s s mod_inverse.hppnu �[��� /* * (C) Copyright Nick Thompson 2018. * Use, modification and distribution are subject to the * Boost Software License, Version 1.0. (See accompanying file * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) */ #ifndef BOOST_INTEGER_MOD_INVERSE_HPP #define BOOST_INTEGER_MOD_INVERSE_HPP #include <stdexcept> #include <boost/throw_exception.hpp> #include <boost/integer/extended_euclidean.hpp> namespace boost { namespace integer { // From "The Joy of Factoring", Algorithm 2.7. // Here's some others names I've found for this function: // PowerMod[a, -1, m] (Mathematica) // mpz_invert (gmplib) // modinv (some dude on stackoverflow) // Would mod_inverse be sometimes mistaken as the modular *additive* inverse? // In any case, I think this is the best name we can get for this function without agonizing. template<class Z> Z mod_inverse(Z a, Z modulus) { if (modulus < Z(2)) { BOOST_THROW_EXCEPTION(std::domain_error("mod_inverse: modulus must be > 1")); } // make sure a < modulus: a = a % modulus; if (a == Z(0)) { // a doesn't have a modular multiplicative inverse: return Z(0); } boost::integer::euclidean_result_t<Z> u = boost::integer::extended_euclidean(a, modulus); if (u.gcd > Z(1)) { return Z(0); } // x might not be in the range 0 < x < m, let's fix that: while (u.x <= Z(0)) { u.x += modulus; } // While indeed this is an inexpensive and comforting check, // the multiplication overflows and hence makes the check itself buggy. //BOOST_ASSERT(u.x*a % modulus == 1); return u.x; } }} #endif PK ^�[!u�G G common_factor.hppnu �[��� // Boost common_factor.hpp header file -------------------------------------// // (C) Copyright Daryle Walker 2001-2002. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // See http://www.boost.org for updates, documentation, and revision history. #ifndef BOOST_INTEGER_COMMON_FACTOR_HPP #define BOOST_INTEGER_COMMON_FACTOR_HPP #include <boost/integer/common_factor_ct.hpp> #include <boost/integer/common_factor_rt.hpp> #endif // BOOST_INTEGER_COMMON_FACTOR_HPP PK ^�[-G��� � integer_log2.hppnu �[��� // ----------------------------------------------------------- // integer_log2.hpp // // Gives the integer part of the logarithm, in base 2, of a // given number. Behavior is undefined if the argument is <= 0. // // Copyright (c) 2003-2004, 2008 Gennaro Prota // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // ----------------------------------------------------------- #ifndef BOOST_INTEGER_INTEGER_LOG2_HPP #define BOOST_INTEGER_INTEGER_LOG2_HPP #include <boost/limits.hpp> #include <boost/config.hpp> #include <boost/assert.hpp> #if defined(BOOST_BORLANDC) #include <climits> #endif namespace boost { namespace detail { template <typename T> int integer_log2_impl(T x, int n) { int result = 0; while (x != 1) { const T t = static_cast<T>(x >> n); if (t) { result += n; x = t; } n /= 2; } return result; } // helper to find the maximum power of two // less than p (more involved than necessary, // to avoid PTS) // template <int p, int n> struct max_pow2_less { enum { c = 2*n < p }; BOOST_STATIC_CONSTANT(int, value = c ? (max_pow2_less< c*p, 2*c*n>::value) : n); }; template <> struct max_pow2_less<0, 0> { BOOST_STATIC_CONSTANT(int, value = 0); }; // this template is here just for Borland :( // we could simply rely on numeric_limits but sometimes // Borland tries to use numeric_limits<const T>, because // of its usual const-related problems in argument deduction // - gps template <typename T> struct width { #ifdef BOOST_BORLANDC BOOST_STATIC_CONSTANT(int, value = sizeof(T) * CHAR_BIT); #else BOOST_STATIC_CONSTANT(int, value = (std::numeric_limits<T>::digits)); #endif }; } // detail // --------- // integer_log2 // --------------- // template <typename T> int integer_log2(T x) { BOOST_ASSERT(x > 0); const int n = detail::max_pow2_less< detail::width<T> :: value, 4 > :: value; return detail::integer_log2_impl(x, n); } } #endif // include guard PK ^�[5��>* * common_factor_ct.hppnu �[��� // Boost common_factor_ct.hpp header file ----------------------------------// // (C) Copyright Daryle Walker and Stephen Cleary 2001-2002. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // See http://www.boost.org for updates, documentation, and revision history. #ifndef BOOST_INTEGER_COMMON_FACTOR_CT_HPP #define BOOST_INTEGER_COMMON_FACTOR_CT_HPP #include <boost/integer_fwd.hpp> // self include #include <boost/config.hpp> // for BOOST_STATIC_CONSTANT, etc. namespace boost { namespace integer { // Implementation details --------------------------------------------------// namespace detail { // Build GCD with Euclid's recursive algorithm template < static_gcd_type Value1, static_gcd_type Value2 > struct static_gcd_helper_t { private: BOOST_STATIC_CONSTANT( static_gcd_type, new_value1 = Value2 ); BOOST_STATIC_CONSTANT( static_gcd_type, new_value2 = Value1 % Value2 ); #ifndef BOOST_BORLANDC #define BOOST_DETAIL_GCD_HELPER_VAL(Value) static_cast<static_gcd_type>(Value) #else typedef static_gcd_helper_t self_type; #define BOOST_DETAIL_GCD_HELPER_VAL(Value) (self_type:: Value ) #endif typedef static_gcd_helper_t< BOOST_DETAIL_GCD_HELPER_VAL(new_value1), BOOST_DETAIL_GCD_HELPER_VAL(new_value2) > next_step_type; #undef BOOST_DETAIL_GCD_HELPER_VAL public: BOOST_STATIC_CONSTANT( static_gcd_type, value = next_step_type::value ); }; // Non-recursive case template < static_gcd_type Value1 > struct static_gcd_helper_t< Value1, 0UL > { BOOST_STATIC_CONSTANT( static_gcd_type, value = Value1 ); }; // Build the LCM from the GCD template < static_gcd_type Value1, static_gcd_type Value2 > struct static_lcm_helper_t { typedef static_gcd_helper_t<Value1, Value2> gcd_type; BOOST_STATIC_CONSTANT( static_gcd_type, value = Value1 / gcd_type::value * Value2 ); }; // Special case for zero-GCD values template < > struct static_lcm_helper_t< 0UL, 0UL > { BOOST_STATIC_CONSTANT( static_gcd_type, value = 0UL ); }; } // namespace detail // Compile-time greatest common divisor evaluator class declaration --------// template < static_gcd_type Value1, static_gcd_type Value2 > struct static_gcd { BOOST_STATIC_CONSTANT( static_gcd_type, value = (detail::static_gcd_helper_t<Value1, Value2>::value) ); }; // boost::integer::static_gcd #if !defined(BOOST_NO_INCLASS_MEMBER_INITIALIZATION) template< static_gcd_type Value1, static_gcd_type Value2 > static_gcd_type const static_gcd< Value1, Value2 >::value; #endif // Compile-time least common multiple evaluator class declaration ----------// template < static_gcd_type Value1, static_gcd_type Value2 > struct static_lcm { BOOST_STATIC_CONSTANT( static_gcd_type, value = (detail::static_lcm_helper_t<Value1, Value2>::value) ); }; // boost::integer::static_lcm #if !defined(BOOST_NO_INCLASS_MEMBER_INITIALIZATION) template< static_gcd_type Value1, static_gcd_type Value2 > static_gcd_type const static_lcm< Value1, Value2 >::value; #endif } // namespace integer } // namespace boost #endif // BOOST_INTEGER_COMMON_FACTOR_CT_HPP PK ^�[��h/�X �X common_factor_rt.hppnu �[��� // (C) Copyright Jeremy William Murphy 2016. // Use, modification and distribution are subject to the // Boost Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_INTEGER_COMMON_FACTOR_RT_HPP #define BOOST_INTEGER_COMMON_FACTOR_RT_HPP #include <boost/assert.hpp> #include <boost/core/enable_if.hpp> #include <boost/config.hpp> // for BOOST_NESTED_TEMPLATE, etc. #include <boost/limits.hpp> // for std::numeric_limits #include <climits> // for CHAR_MIN #include <boost/detail/workaround.hpp> #include <iterator> #include <algorithm> #include <limits> #ifndef BOOST_NO_CXX11_HDR_TYPE_TRAITS #include <type_traits> #endif #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL #include <functional> #endif #if ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64)) #include <intrin.h> #endif #ifdef BOOST_MSVC #pragma warning(push) #pragma warning(disable:4127 4244) // Conditional expression is constant #endif #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS) && !defined(BOOST_NO_CXX11_NOEXCEPT) #define BOOST_GCD_NOEXCEPT(T) noexcept(std::is_arithmetic<T>::value) #else #define BOOST_GCD_NOEXCEPT(T) #endif namespace boost { template <class I> class rational; namespace integer { namespace gcd_detail{ // // some helper functions which really should be constexpr already, but sadly aren't: // #ifndef BOOST_NO_CXX14_CONSTEXPR template <class T> inline constexpr T constexpr_min(T const& a, T const& b) BOOST_GCD_NOEXCEPT(T) { return a < b ? a : b; } template <class T> inline constexpr auto constexpr_swap(T&a, T& b) BOOST_GCD_NOEXCEPT(T) -> decltype(a.swap(b)) { return a.swap(b); } template <class T, class U> inline constexpr void constexpr_swap(T&a, U& b...) BOOST_GCD_NOEXCEPT(T) { T t(static_cast<T&&>(a)); a = static_cast<T&&>(b); b = static_cast<T&&>(t); } #else template <class T> inline T constexpr_min(T const& a, T const& b) BOOST_GCD_NOEXCEPT(T) { return a < b ? a : b; } template <class T> inline void constexpr_swap(T&a, T& b) BOOST_GCD_NOEXCEPT(T) { using std::swap; swap(a, b); } #endif template <class T, bool a = #ifndef BOOST_NO_CXX11_HDR_TYPE_TRAITS std::is_unsigned<T>::value || #endif (std::numeric_limits<T>::is_specialized && !std::numeric_limits<T>::is_signed)> struct gcd_traits_abs_defaults { inline static BOOST_CXX14_CONSTEXPR const T& abs(const T& val) BOOST_GCD_NOEXCEPT(T) { return val; } }; template <class T> struct gcd_traits_abs_defaults<T, false> { inline static T BOOST_CXX14_CONSTEXPR abs(const T& val) BOOST_GCD_NOEXCEPT(T) { // This sucks, but std::abs is not constexpr :( return val < T(0) ? -val : val; } }; enum method_type { method_euclid = 0, method_binary = 1, method_mixed = 2 }; struct any_convert { template <class T> any_convert(const T&); }; struct unlikely_size { char buf[9973]; }; unlikely_size operator <<= (any_convert, any_convert); unlikely_size operator >>= (any_convert, any_convert); template <class T> struct gcd_traits_defaults : public gcd_traits_abs_defaults<T> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(T& val) BOOST_GCD_NOEXCEPT(T) { unsigned r = 0; while (T(0) == (val & 1u)) { #ifdef _MSC_VER // VC++ can't handle operator >>= in constexpr code for some reason val = val >> 1; #else val >>= 1; #endif ++r; } return r; } inline static BOOST_CXX14_CONSTEXPR bool less(const T& a, const T& b) BOOST_GCD_NOEXCEPT(T) { return a < b; } static T& get_value(); #ifndef BOOST_NO_SFINAE static const bool has_operator_left_shift_equal = sizeof(get_value() <<= 2) != sizeof(unlikely_size); static const bool has_operator_right_shift_equal = sizeof(get_value() >>= 2) != sizeof(unlikely_size); #else static const bool has_operator_left_shift_equal = true; static const bool has_operator_right_shift_equal = true; #endif static const method_type method = std::numeric_limits<T>::is_specialized && std::numeric_limits<T>::is_integer && has_operator_left_shift_equal && has_operator_right_shift_equal ? method_mixed : method_euclid; }; // // Default gcd_traits just inherits from defaults: // template <class T> struct gcd_traits : public gcd_traits_defaults<T> {}; // // Some platforms have fast bitscan operations, that allow us to implement // make_odd much more efficiently, unfortunately we can't use these if we want // the functions to be constexpr as the compiler intrinsics aren't constexpr. // #if defined(BOOST_NO_CXX14_CONSTEXPR) && ((defined(BOOST_MSVC) && (BOOST_MSVC >= 1600)) || (defined(__clang__) && defined(__c2__)) || (defined(BOOST_INTEL) && defined(_MSC_VER))) && (defined(_M_IX86) || defined(_M_X64)) #pragma intrinsic(_BitScanForward,) template <> struct gcd_traits<unsigned long> : public gcd_traits_defaults<unsigned long> { BOOST_FORCEINLINE static unsigned find_lsb(unsigned long val) BOOST_NOEXCEPT { unsigned long result; _BitScanForward(&result, val); return result; } BOOST_FORCEINLINE static unsigned make_odd(unsigned long& val) BOOST_NOEXCEPT { unsigned result = find_lsb(val); val >>= result; return result; } }; #ifdef _M_X64 #pragma intrinsic(_BitScanForward64) template <> struct gcd_traits<unsigned __int64> : public gcd_traits_defaults<unsigned __int64> { BOOST_FORCEINLINE static unsigned find_lsb(unsigned __int64 mask) BOOST_NOEXCEPT { unsigned long result; _BitScanForward64(&result, mask); return result; } BOOST_FORCEINLINE static unsigned make_odd(unsigned __int64& val) BOOST_NOEXCEPT { unsigned result = find_lsb(val); val >>= result; return result; } }; #endif // // Other integer type are trivial adaptations of the above, // this works for signed types too, as by the time these functions // are called, all values are > 0. // template <> struct gcd_traits<long> : public gcd_traits_defaults<long> { BOOST_FORCEINLINE static unsigned make_odd(long& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<unsigned int> : public gcd_traits_defaults<unsigned int> { BOOST_FORCEINLINE static unsigned make_odd(unsigned int& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<int> : public gcd_traits_defaults<int> { BOOST_FORCEINLINE static unsigned make_odd(int& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<unsigned short> : public gcd_traits_defaults<unsigned short> { BOOST_FORCEINLINE static unsigned make_odd(unsigned short& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<short> : public gcd_traits_defaults<short> { BOOST_FORCEINLINE static unsigned make_odd(short& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<unsigned char> : public gcd_traits_defaults<unsigned char> { BOOST_FORCEINLINE static unsigned make_odd(unsigned char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<signed char> : public gcd_traits_defaults<signed char> { BOOST_FORCEINLINE static unsigned make_odd(signed char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<char> : public gcd_traits_defaults<char> { BOOST_FORCEINLINE static unsigned make_odd(char& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; #ifndef BOOST_NO_INTRINSIC_WCHAR_T template <> struct gcd_traits<wchar_t> : public gcd_traits_defaults<wchar_t> { BOOST_FORCEINLINE static unsigned make_odd(wchar_t& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; #endif #ifdef _M_X64 template <> struct gcd_traits<__int64> : public gcd_traits_defaults<__int64> { BOOST_FORCEINLINE static unsigned make_odd(__int64& val)BOOST_NOEXCEPT{ unsigned result = gcd_traits<unsigned __int64>::find_lsb(val); val >>= result; return result; } }; #endif #elif defined(BOOST_GCC) || defined(__clang__) || (defined(BOOST_INTEL) && defined(__GNUC__)) template <> struct gcd_traits<unsigned> : public gcd_traits_defaults<unsigned> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned mask)BOOST_NOEXCEPT { return __builtin_ctz(mask); } BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned& val)BOOST_NOEXCEPT { unsigned result = find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<unsigned long> : public gcd_traits_defaults<unsigned long> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(unsigned long mask)BOOST_NOEXCEPT { return __builtin_ctzl(mask); } BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned long& val)BOOST_NOEXCEPT { unsigned result = find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<boost::ulong_long_type> : public gcd_traits_defaults<boost::ulong_long_type> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned find_lsb(boost::ulong_long_type mask)BOOST_NOEXCEPT { return __builtin_ctzll(mask); } BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(boost::ulong_long_type& val)BOOST_NOEXCEPT { unsigned result = find_lsb(val); val >>= result; return result; } }; // // Other integer type are trivial adaptations of the above, // this works for signed types too, as by the time these functions // are called, all values are > 0. // template <> struct gcd_traits<boost::long_long_type> : public gcd_traits_defaults<boost::long_long_type> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(boost::long_long_type& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<boost::ulong_long_type>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<long> : public gcd_traits_defaults<long> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(long& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<int> : public gcd_traits_defaults<int> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(int& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned long>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<unsigned short> : public gcd_traits_defaults<unsigned short> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned short& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<short> : public gcd_traits_defaults<short> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(short& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<unsigned char> : public gcd_traits_defaults<unsigned char> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(unsigned char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<signed char> : public gcd_traits_defaults<signed char> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(signed char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; } }; template <> struct gcd_traits<char> : public gcd_traits_defaults<char> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(char& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; } }; #ifndef BOOST_NO_INTRINSIC_WCHAR_T template <> struct gcd_traits<wchar_t> : public gcd_traits_defaults<wchar_t> { BOOST_FORCEINLINE static BOOST_CXX14_CONSTEXPR unsigned make_odd(wchar_t& val)BOOST_NOEXCEPT { unsigned result = gcd_traits<unsigned>::find_lsb(val); val >>= result; return result; } }; #endif #endif // // The Mixed Binary Euclid Algorithm // Sidi Mohamed Sedjelmaci // Electronic Notes in Discrete Mathematics 35 (2009) 169-176 // template <class T> BOOST_CXX14_CONSTEXPR T mixed_binary_gcd(T u, T v) BOOST_GCD_NOEXCEPT(T) { if(gcd_traits<T>::less(u, v)) constexpr_swap(u, v); unsigned shifts = 0; if(u == T(0)) return v; if(v == T(0)) return u; shifts = constexpr_min(gcd_traits<T>::make_odd(u), gcd_traits<T>::make_odd(v)); while(gcd_traits<T>::less(1, v)) { u %= v; v -= u; if(u == T(0)) return v << shifts; if(v == T(0)) return u << shifts; gcd_traits<T>::make_odd(u); gcd_traits<T>::make_odd(v); if(gcd_traits<T>::less(u, v)) constexpr_swap(u, v); } return (v == 1 ? v : u) << shifts; } /** Stein gcd (aka 'binary gcd') * * From Mathematics to Generic Programming, Alexander Stepanov, Daniel Rose */ template <typename SteinDomain> BOOST_CXX14_CONSTEXPR SteinDomain Stein_gcd(SteinDomain m, SteinDomain n) BOOST_GCD_NOEXCEPT(SteinDomain) { BOOST_ASSERT(m >= 0); BOOST_ASSERT(n >= 0); if (m == SteinDomain(0)) return n; if (n == SteinDomain(0)) return m; // m > 0 && n > 0 unsigned d_m = gcd_traits<SteinDomain>::make_odd(m); unsigned d_n = gcd_traits<SteinDomain>::make_odd(n); // odd(m) && odd(n) while (m != n) { if (n > m) constexpr_swap(n, m); m -= n; gcd_traits<SteinDomain>::make_odd(m); } // m == n m <<= constexpr_min(d_m, d_n); return m; } /** Euclidean algorithm * * From Mathematics to Generic Programming, Alexander Stepanov, Daniel Rose * */ template <typename EuclideanDomain> inline BOOST_CXX14_CONSTEXPR EuclideanDomain Euclid_gcd(EuclideanDomain a, EuclideanDomain b) BOOST_GCD_NOEXCEPT(EuclideanDomain) { while (b != EuclideanDomain(0)) { a %= b; constexpr_swap(a, b); } return a; } template <typename T> inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_mixed, T>::type optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T) { return gcd_detail::mixed_binary_gcd(a, b); } template <typename T> inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_binary, T>::type optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T) { return gcd_detail::Stein_gcd(a, b); } template <typename T> inline BOOST_CXX14_CONSTEXPR BOOST_DEDUCED_TYPENAME enable_if_c<gcd_traits<T>::method == method_euclid, T>::type optimal_gcd_select(T const &a, T const &b) BOOST_GCD_NOEXCEPT(T) { return gcd_detail::Euclid_gcd(a, b); } template <class T> inline BOOST_CXX14_CONSTEXPR T lcm_imp(const T& a, const T& b) BOOST_GCD_NOEXCEPT(T) { T temp = boost::integer::gcd_detail::optimal_gcd_select(a, b); #if BOOST_WORKAROUND(BOOST_GCC_VERSION, < 40500) return (temp != T(0)) ? T(a / temp * b) : T(0); #else return temp != T(0) ? T(a / temp * b) : T(0); #endif } } // namespace detail template <typename Integer> inline BOOST_CXX14_CONSTEXPR Integer gcd(Integer const &a, Integer const &b) BOOST_GCD_NOEXCEPT(Integer) { if(a == (std::numeric_limits<Integer>::min)()) return a == static_cast<Integer>(0) ? gcd_detail::gcd_traits<Integer>::abs(b) : boost::integer::gcd(static_cast<Integer>(a % b), b); else if (b == (std::numeric_limits<Integer>::min)()) return b == static_cast<Integer>(0) ? gcd_detail::gcd_traits<Integer>::abs(a) : boost::integer::gcd(a, static_cast<Integer>(b % a)); return gcd_detail::optimal_gcd_select(static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(b))); } template <typename Integer> inline BOOST_CXX14_CONSTEXPR Integer lcm(Integer const &a, Integer const &b) BOOST_GCD_NOEXCEPT(Integer) { return gcd_detail::lcm_imp(static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(a)), static_cast<Integer>(gcd_detail::gcd_traits<Integer>::abs(b))); } #ifndef BOOST_NO_CXX11_VARIADIC_TEMPLATES // // This looks slightly odd, but the variadic forms must have 3 or more arguments, and the variadic argument pack may be empty. // This matters not at all for most compilers, but Oracle C++ selects the wrong overload in the 2-arg case unless we do this. // template <typename Integer, typename... Args> inline BOOST_CXX14_CONSTEXPR Integer gcd(Integer const &a, Integer const &b, const Integer& c, Args const&... args) BOOST_GCD_NOEXCEPT(Integer) { Integer t = gcd(b, c, args...); return t == 1 ? 1 : gcd(a, t); } template <typename Integer, typename... Args> inline BOOST_CXX14_CONSTEXPR Integer lcm(Integer const &a, Integer const &b, Integer const& c, Args const&... args) BOOST_GCD_NOEXCEPT(Integer) { return lcm(a, lcm(b, c, args...)); } #endif // // Special handling for rationals: // template <typename Integer> inline typename boost::enable_if_c<std::numeric_limits<Integer>::is_specialized, boost::rational<Integer> >::type gcd(boost::rational<Integer> const &a, boost::rational<Integer> const &b) { return boost::rational<Integer>(static_cast<Integer>(gcd(a.numerator(), b.numerator())), static_cast<Integer>(lcm(a.denominator(), b.denominator()))); } template <typename Integer> inline typename boost::enable_if_c<std::numeric_limits<Integer>::is_specialized, boost::rational<Integer> >::type lcm(boost::rational<Integer> const &a, boost::rational<Integer> const &b) { return boost::rational<Integer>(static_cast<Integer>(lcm(a.numerator(), b.numerator())), static_cast<Integer>(gcd(a.denominator(), b.denominator()))); } /** * Knuth, The Art of Computer Programming: Volume 2, Third edition, 1998 * Chapter 4.5.2, Algorithm C: Greatest common divisor of n integers. * * Knuth counts down from n to zero but we naturally go from first to last. * We also return the termination position because it might be useful to know. * * Partly by quirk, partly by design, this algorithm is defined for n = 1, * because the gcd of {x} is x. It is not defined for n = 0. * * @tparam I Input iterator. * @return The gcd of the range and the iterator position at termination. */ template <typename I> std::pair<typename std::iterator_traits<I>::value_type, I> gcd_range(I first, I last) BOOST_GCD_NOEXCEPT(I) { BOOST_ASSERT(first != last); typedef typename std::iterator_traits<I>::value_type T; T d = *first; ++first; while (d != T(1) && first != last) { d = gcd(d, *first); ++first; } return std::make_pair(d, first); } template <typename I> std::pair<typename std::iterator_traits<I>::value_type, I> lcm_range(I first, I last) BOOST_GCD_NOEXCEPT(I) { BOOST_ASSERT(first != last); typedef typename std::iterator_traits<I>::value_type T; T d = *first; ++first; while (d != T(0) && first != last) { d = lcm(d, *first); ++first; } return std::make_pair(d, first); } template < typename IntegerType > class gcd_evaluator #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL : public std::binary_function<IntegerType, IntegerType, IntegerType> #endif { public: #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL typedef IntegerType first_argument_type; typedef IntegerType second_argument_type; typedef IntegerType result_type; #endif IntegerType operator()(IntegerType const &a, IntegerType const &b) const { return boost::integer::gcd(a, b); } }; template < typename IntegerType > class lcm_evaluator #ifdef BOOST_NO_CXX11_HDR_FUNCTIONAL : public std::binary_function<IntegerType, IntegerType, IntegerType> #endif { public: #ifndef BOOST_NO_CXX11_HDR_FUNCTIONAL typedef IntegerType first_argument_type; typedef IntegerType second_argument_type; typedef IntegerType result_type; #endif IntegerType operator()(IntegerType const &a, IntegerType const &b)const { return boost::integer::lcm(a, b); } }; } // namespace integer } // namespace boost #ifdef BOOST_MSVC #pragma warning(pop) #endif #endif // BOOST_INTEGER_COMMON_FACTOR_RT_HPP PK ^�[��(�a a static_min_max.hppnu �[��� // Boost integer/static_min_max.hpp header file ----------------------------// // (C) Copyright Daryle Walker 2001. // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // See http://www.boost.org for updates, documentation, and revision history. #ifndef BOOST_INTEGER_STATIC_MIN_MAX_HPP #define BOOST_INTEGER_STATIC_MIN_MAX_HPP #include <boost/config.hpp> #include <boost/integer_fwd.hpp> // self include namespace boost { // Compile-time extrema class declarations ---------------------------------// // Get the minimum or maximum of two values, signed or unsigned. template <static_min_max_signed_type Value1, static_min_max_signed_type Value2> struct static_signed_min { BOOST_STATIC_CONSTANT(static_min_max_signed_type, value = (Value1 > Value2) ? Value2 : Value1 ); }; template <static_min_max_signed_type Value1, static_min_max_signed_type Value2> struct static_signed_max { BOOST_STATIC_CONSTANT(static_min_max_signed_type, value = (Value1 < Value2) ? Value2 : Value1 ); }; template <static_min_max_unsigned_type Value1, static_min_max_unsigned_type Value2> struct static_unsigned_min { BOOST_STATIC_CONSTANT(static_min_max_unsigned_type, value = (Value1 > Value2) ? Value2 : Value1 ); }; template <static_min_max_unsigned_type Value1, static_min_max_unsigned_type Value2> struct static_unsigned_max { BOOST_STATIC_CONSTANT(static_min_max_unsigned_type, value = (Value1 < Value2) ? Value2 : Value1 ); }; } // namespace boost #endif // BOOST_INTEGER_STATIC_MIN_MAX_HPP PK ^�[� �M� � static_log2.hppnu �[��� PK ^�['O� � extended_euclidean.hppnu �[��� PK ^�[�V,f� � integer_mask.hppnu �[��� PK ^�[~;��s s �% mod_inverse.hppnu �[��� PK ^�[!u�G G �, common_factor.hppnu �[��� PK ^�[-G��� � "/ integer_log2.hppnu �[��� PK ^�[5��>* * ?8 common_factor_ct.hppnu �[��� PK ^�[��h/�X �X �E common_factor_rt.hppnu �[��� PK ^�[��(�a a � static_min_max.hppnu �[��� PK � ��
| ver. 1.6 |
Github
|
.
| PHP 8.2.30 | ??????????? ?????????: 0 |
proxy
|
phpinfo
|
???????????