ugipro_lib_cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub CURRY-AND-RICE/ugipro_lib_cpp

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

Depends on

Verified with

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