三浦と窮理とブログ

自分の経験したことを検索可能にしていくブログ.誰かの役に立ってくれれば嬉しいです.

冪剰余と剰余の逆元を求めるC++/Boostライブラリ

冪剰余

冪剰余 $a ^ b \bmod m$ を求めます.たぶん二分累乗法だと思います.

#include <boost/multiprecision/integer.hpp>
boost::multiprecision::powm(a, b, m)

剰余の逆元(拡張ユークリッド互除法)

剰余の逆元 $a^{-1} \bmod m$ が存在すれば求めます.

(2019年10月5日追記:これはboost1.70.0で追加されたものなので,atcoder では現在未対応.)

#include <boost/integer/mod_inverse.hpp>
boost::integer::mod_inverse(a, m)

使用例

プログラム

#include <iostream>
#include <boost/multiprecision/integer.hpp>
#include <boost/integer/mod_inverse.hpp>
#define MOD 1000000007

int main() {
    //冪剰余 3^100 mod MOD
    cout << boost::multiprecision::powm(3, 100, MOD) << endl;
    // 剰余の逆元 3^-1 mod 13
    cout << boost::integer::mod_inverse(3, 13) << endl;
}

出力

886041711
9

参考

boost/multiprecision/integer.hpp - 1.57.0

Modular Multiplicative Inverse - 1.70.0