[競プロ]繰り返し2乗法【Java】【Python】 - Qiita

久々の競プロ記事です。 今回は繰り返し2乗法についてです。Javaで書いてみます。また、繰り返し2乗法を使用した問題をJava, Pythonで解いてみます。 繰り返し2乗法とは べき乗の計算量を減らすテクニックです。以下のように、指数を2のべき乗表記をして累乗計算をします。 N乗の計算がO(N)からO(logN)になります。 計算方法 3^10を求めます。 10 = 2^3 + 2^1と表せるため、 3^10 = 3^(2^3 + 2^1) = 3^(2^3) * 3^(2^1)と表せます。 きれいに書くと以下のとおりです。 「それはわかるけどなんでそう考えると計算量が減るの？」という声が聞こえて来そうです。 もうちょっと丁寧に説明しますね。 2進数のbit演算を使用しています。 こんな感じです↓ 計算の過程は以下のとおりです。 tmp・・・一時変数 ans・・・3^10の解が入る変数