繰り返し二乗法
(ugilib/math/pow.hpp)

• View this file on GitHub
• Last update: 2024-04-03 22:46:30+09:00
• Include: #include "ugilib/math/pow.hpp"

Depends on

• ugilib/base/definitions.hpp

Verified with

• tests/math/pow.test.cpp

Code

#pragma once
#include <bits/stdc++.h>
#include "ugilib/base/definitions.hpp"

namespace ugilib {
    /**
     * @brief 繰り返し二乗法
     * @param x 基数
     * @param n 指数
     * @param mod mod
     * @return x^n % mod
     * @note O(log n)
    */
    template <typename T>
    T fast_pow(T x, ll n, T mod = ugilib::constants::INF<T>) {
        assert(n >= 0);
        T res = 1;
        while (n) {
            if (n & 1) res = res*x % mod;
            x = x*x % mod;
            n >>= 1;
        }
        return res;
    }
}  // namespace ugilib

#line 2 "ugilib/math/pow.hpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 4 "ugilib/math/pow.hpp"

namespace ugilib {
    /**
     * @brief 繰り返し二乗法
     * @param x 基数
     * @param n 指数
     * @param mod mod
     * @return x^n % mod
     * @note O(log n)
    */
    template <typename T>
    T fast_pow(T x, ll n, T mod = ugilib::constants::INF<T>) {
        assert(n >= 0);
        T res = 1;
        while (n) {
            if (n & 1) res = res*x % mod;
            x = x*x % mod;
            n >>= 1;
        }
        return res;
    }
}  // namespace ugilib

Back to top page