繰り返し二乗法
(algorithm/Math/Algebra/power.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/Algebra/power.hpp"

概要

$n$ を $k$ 乗した値 $n^k$ を求める（ただし，$k$ は非負整数）．

本実装では「繰り返し二乗法」を用いており，計算量は $\mathcal{O}(\log k)$ となる．

参考文献

1. “冪乗”. Wikipedia. https://ja.wikipedia.org/wiki/冪乗.

Required by

• 累乗根（ニュートン法） (algorithm/Math/Algebra/nth_root.hpp)

Verified with

• verify/aoj-ITP1_10_D-nth_root.test.cpp
• verify/aoj-ITP1_10_D-nth_root.test.cpp

Code

#ifndef ALGORITHM_POWER_HPP
#define ALGORITHM_POWER_HPP 1

#include <cassert>

namespace algorithm {

// 繰り返し二乗法．O(logK).
template <typename Type>
constexpr Type pow(Type n, long long k) {
    assert(k >= 0);
    Type res = 1;
    while(k > 0) {
        if(k & 1LL) res *= n;
        n *= n;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/Algebra/power.hpp"



#include <cassert>

namespace algorithm {

// 繰り返し二乗法．O(logK).
template <typename Type>
constexpr Type pow(Type n, long long k) {
    assert(k >= 0);
    Type res = 1;
    while(k > 0) {
        if(k & 1LL) res *= n;
        n *= n;
        k >>= 1;
    }
    return res;
}

}  // namespace algorithm

Back to top page