math/pow_mod.hpp

• View this file on GitHub
• Last update: 2023-10-01 12:06:18+09:00
• Include: #include "math/pow_mod.hpp"

Required by

• math/convolution/ntt.hpp
• 素数判定 (math/is-prime.hpp)
• math/primitive-root.hpp

Verified with

• test/aoj/aoj-ALDS1-1-C.test.cpp
• test/library-checker/convolution/convolution-mod.test.cpp
• test/library-checker/math/primality-test.test.cpp

Code

#pragma once

constexpr long long pow_mod(long long x, long long k, long long m) {
    long long res = 1;
    long long mul = (x >= 0 ? x % m : x % m + m);
    while(k) {
        if(k & 1) res = (__int128_t)res * mul % m;
        mul = (__int128_t)mul * mul % m;
        k >>= 1;
    }
    return res;
}

#line 2 "math/pow_mod.hpp"

constexpr long long pow_mod(long long x, long long k, long long m) {
    long long res = 1;
    long long mul = (x >= 0 ? x % m : x % m + m);
    while(k) {
        if(k & 1) res = (__int128_t)res * mul % m;
        mul = (__int128_t)mul * mul % m;
        k >>= 1;
    }
    return res;
}

Back to top page