累乗計算の高速化 - へなちょここーだーHackerRankのAntiPalindromic Stringsを解くときにどうしても累乗計算がO(n)になってしまいタイムアウトになってしまっていたところ、凄くキレイで高速なアルゴリズムを発見！ 高速な累乗計算 - あどけない話 これを使ってみました。 単純なxのn乗をmを法として求めるアルゴリズム long myPow(long x, long n, long m){ long result = 1; for(int i = 0; i < n; i++){ result *= x; result = result % m; } return result; } 改善後のアルゴリズム ここから、累乗計算の方法を改良していきましょう。その例として、を計算してみます。 1. まずは19を2進法であらわす。 2. これを利用して累乗を計算する。 3. これを計算できる漸化式を考える。 4.
