#include "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; }