aboutsummaryrefslogtreecommitdiff
path: root/binpow.h
blob: 9553b576edc4dc6bdb491d621f0ac78cf4ccb34d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#pragma once

#include <cstdint>
#include <type_traits>

template <typename T, typename N = uint64_t>
static constexpr T binpow(T a, N n) {
  static_assert(std::is_integral_v<N>);
  auto result = T::mul_id();
  while (n) {
    if (n & 1) {
      result *= a;
    }
    a *= a;
    n >>= 1;
  }
  return result;
}