modpow
(lib/modpow.hpp)

• View this file on GitHub
• Last update: 2021-10-09 16:38:32+09:00
• Include: #include "lib/modpow.hpp"

概要

TBD

使い方

TBD

計算量

TBD

Verified with

• test/verify/aoj-dpl-1-a.test.cpp

Code

/**
 * @brief modpow 
 * @docs docs/modpow.md
 */
template<typename T = int64_t>
T modpow(T n, T power, T mod) {
    T res = 1;
    while (power > 0) {
        if (power & 1) res = res * n % mod;
        power >>= 1;
        n = n * n % mod;
    }
    return res;
}

#line 1 "lib/modpow.hpp"
/**
 * @brief modpow 
 * @docs docs/modpow.md
 */
template<typename T = int64_t>
T modpow(T n, T power, T mod) {
    T res = 1;
    while (power > 0) {
        if (power & 1) res = res * n % mod;
        power >>= 1;
        n = n * n % mod;
    }
    return res;
}

Back to top page