最初に
C++で書かれた、冪剰余コードです。表記
冪剰余情報
WikipediaC++コード
/** * 冪剰余を返す。 * C ≡ b^e ( mod m) * * @param [in] b 基底 * @param [in] e 冪指数 * @param [in] m m を法とした b の e 冪剰余 * @return 冪剰余を返す。 */ template<typename IntType> IntType Modpow(IntType b, IntType e, IntType m) { IntType result = 1; while (e > 0) { if ((e & 1) == 1) result = (result * b) % m; e >>= 1; b = (b * b) % m; } return result; }