冪剰余
冪剰余 $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 では現在未対応．）
（2020年2月2日追記：atcoderが言語アップデートによりboost1.71.0 に対応したので C++(GCC9.2.1)で使用可能です．）
#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
