numnric

最大公约数和最小公倍数的实现

代码是在C++11标准中的实现,如果是C++17的话就换成Stein了

#include <type_traits>
namespace __detail {
  // std::abs is not constexpr, doesn't support unsigned integers,
  // and std::abs(std::numeric_limits<T>::min()) is undefined.
  template<typename _Up, typename _Tp>
    constexpr _Up
    __absu(_Tp __val)
    {
      static_assert(is_unsigned<_Up>::value, "result type must be unsigned");
      static_assert(sizeof(_Up) >= sizeof(_Tp),
   "result type must be at least as wide as the input type");
      return __val < 0 ? -(_Up)__val : (_Up)__val;
    }

  template<typename _Up> void __absu(bool) = delete;

  // GCD implementation
  template<typename _Tp>
    constexpr _Tp
    __gcd(_Tp __m, _Tp __n)
    {
      return __m == 0 ? __n
 : __n == 0 ? __m
 : __detail::__gcd(__n, _Tp(__m % __n));
    }

  // LCM implementation
  template<typename _Tp>
    constexpr _Tp
    __lcm(_Tp __m, _Tp __n)
    {
      return (__m != 0 && __n != 0)
 ? (__m / __detail::__gcd(__m, __n)) * __n
 : 0;
    }
} // namespace __detail

int stein(int a,int b) {
    if(a<b)a^=b,b^=a,a^=b;//交换
    if(!b)return a;
    if((!(a&1)) && (!(b&1)))return stein(a>>1,b>>1)<<1;
    else if((a&1) && (!(b&1)))return stein(a,b>>1);
    else if((!(a&1)) && (b&1))return stein(a>>1,b);
    else return stein(a-b,b);
}

int gcd(int a, int b) {
  //如果a或b为0，返回不为0的那个数
  if (a == 0) return b;
  if (b == 0) return a;
  //定义一个变量k记录除掉的公因数2的个数
  int k = 0;
  //当a和b都是偶数时，同时除以2，并增加k
  while ((a & 1) == 0 && (b & 1) == 0) {
    a >>= 1;
    b >>= 1;
    k++;
  }
  //当有一个数为偶数时，将其除以2
  while ((a & 1) == 0) a >>= 1;
  while ((b & 1) == 0) b >>= 1;
  
   //当两个数都为奇数时，用更相减损法求出最大公约数，并左移k位
   while (true) {
     if (a > b)
       a = (a - b) >> k;
     else if (a < b)
       b = (b - a) >> k;
     else 
       return a << k; 
   }
}