高速べき乗のアルゴリズム

べき乗を求める方法は,最初に1つの数をn回連続で乗算することである.複雑度O(n).明らかに、いくつかのカードデータのテーマの中で、O(n)のアルゴリズムを加えるのはTLEが簡単で、そこで今日のテーマを引き出しました:高速べき乗.高速べき乗の原理は簡単で,a b a^b abのbをバイナリに変換し,ビット演算に基づいて計算する.例えば、5 15^{15}515の15を1111に置き換え、5 1 5^{1}51を計算する× 5 2 5 ^{2} 52× 5 4 5 ^{4} 54× 5 8 8 5^{8}58は,ビット演算を用いて2,4,8を計算すればよい.
バイナリなので、ビット演算(その後ブログで補足)という強力なツール:&と>>:&演算は通常バイナリビット操作に用いられ、例えば1つの数&1の結果はバイナリの最下位ビットを取ることである.また、パリティx&1=0がパリティであり、x&1=1がパリティであると判断することもできる.演算は比較的に単純で、バイナリは最後の1位を取り除いて、多く言わないで、コードを放します.

int quickpow(int base, int pow) {
    int ans = 1;
    while (pow != 0) {
        if ((pow & 1) != 0)
            ans *= base;	//      1，              。
        base *= base;		//       ， 2 4，4 8.
        pow >>= 1;		// b       。
    }
    return ans;
}

このアルゴリズムの複雑さはO(l o g 2 log_2 log 2 n)である.
その後、高速べき乗を用いて問題を解く例を補足します.