power

template <class _Tp, class _Integer, class _MonoidOperation>
_Tp __power(_Tp __x, _Integer __n, _MonoidOperation __opr)
{
  if (__n == 0)
    return identity_element(__opr);
  else {
    while ((__n & 1) == 0) {
      __n >>= 1;
      __x = __opr(__x, __x);
    }

    _Tp __result = __x;
    __n >>= 1;
    while (__n != 0) {
      __x = __opr(__x, __x);
      if ((__n & 1) != 0)
        __result = __opr(__result, __x);
      __n >>= 1;
    }
    return __result;
  }
}

\({2^{\rm{n}}}{\rm{ = }}{2^{(n/2)}}*{2^{(n/2)}}\;\;(n{\rm{\% }}2{\rm{ = = }}0)\)

个别算法详解

原文：https://www.cnblogs.com/xiaojianliu/p/12628875.html