doubling-pow() (繰り返し二乗法)
(Algorithm/doubling-pow.hpp)

#pragma once
#include <cmath>
#include "../Util/int-alias.hpp"

/**
 * @brief doubling-pow() (繰り返し二乗法)
 */
template <class Integer>
constexpr Integer doublingPow(const Integer& n, const i64 expv) {
    Integer ret = 1, square = n;
    for (u64 p = std::abs(expv); p; p >>= 1) {
        if (p & 1) ret *= square;
        square *= square;
    }
    return (expv < 0) ? (1 / ret) : ret;
}

#line 2 "Algorithm/doubling-pow.hpp"
#include <cmath>
#line 2 "Util/int-alias.hpp"
#include <cstdint>

/**
 * @brief int-alias (整数型のエイリアス)
 */
using i64 = int64_t;
using u64 = uint64_t;
#line 4 "Algorithm/doubling-pow.hpp"

/**
 * @brief doubling-pow() (繰り返し二乗法)
 */
template <class Integer>
constexpr Integer doublingPow(const Integer& n, const i64 expv) {
    Integer ret = 1, square = n;
    for (u64 p = std::abs(expv); p; p >>= 1) {
        if (p & 1) ret *= square;
        square *= square;
    }
    return (expv < 0) ? (1 / ret) : ret;
}