冪剰余：C++コード

C++,アルゴリズム,プログラム

作成者：

最初に

C++で書かれた、冪剰余コードです。

表記

冪剰余
C\equiv b^e ( \text{mod}\,m)

情報

Wikipedia

C++コード

/**
* 冪剰余を返す。
* 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;
}

オンライン実行

コメント 

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。