繰り返し二乗法 (Other/fast_power.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-04-13 19:22:19+09:00
• Include: #include "Other/fast_power.hpp"

繰り返し二乗法

xのn乗を、繰り返し二乗法を用いて高速に計算する関数です。

fast_pow

template <class S>
S fast_pow(S x, long long n, function<S(S, S)> mul, function<S()> e)

• x: 底となる元
• n: 指数（非負整数）
• mul: 乗算を定義する二項演算（結合則 mul(a, mul(b, c)) = mul(mul(a, b), c) を満たす必要あり）
• e: 乗算の単位元(mul(a, e) = a)を返す関数

モノイド (S, mul) において、x の n 乗を計算します。

制約

• $0 \leq n$

計算量

• $O(\log n)$

Required by

• 高速素因数分解 (Math/fast_factorizer.hpp)
• 整数累乗 (mod) (Math/mod_power.hpp)
• 素数判定 (Math/primality_test.hpp)

Verified with

• test/Math/fast_factorize/yosupo-factorize.cpp
• test/Math/mod_power/aoj-NTL_1_B.cpp
• test/Math/mod_power/my_test.cpp
• test/Math/pow_of_matrix/yosupo-pow_of_matrix.cpp
• test/Math/primality_test/yosupo-primality_test.cpp

Code

#include <bits/stdc++.h>
using namespace std;

template <class S>
S fast_pow(S x, long long n, function<S(S, S)> mul, function<S()> e)
{
    assert(0 <= n);

    S ans = e();

    while (n)
    {
        if (n & 1)
        {
            ans = mul(ans, x);
        }
        x = mul(x, x);
        n >>= 1;
    }

    return ans;
}

#line 1 "Other/fast_power.hpp"
#include <bits/stdc++.h>
using namespace std;

template <class S>
S fast_pow(S x, long long n, function<S(S, S)> mul, function<S()> e)
{
    assert(0 <= n);

    S ans = e();

    while (n)
    {
        if (n & 1)
        {
            ans = mul(ans, x);
        }
        x = mul(x, x);
        n >>= 1;
    }

    return ans;
}

Back to top page