はじめに
前回、BigIntegerにmodPowというメソッドがあり、中では繰り返し二乗法を使っていて、意外と使えるかもしれない?どこまで使えるのか?という話をしました。
yoshiki-utakata.hatenablog.com
topcoder SRM 660 Hard
そこで、この前のtopcoderでこんな問題があった。
問題
整数 n, k, m が入力されるので、1 <= i <= n となるiについて、i^(2^k-1)
の合計を m で割った余りを求めよという問題。1 <= n <= 1000000
, 1 <= k <= 400
, 2 <= m <= 1000000000
である。
実装1
これをこう実装してみた。
import java.math.BigInteger; public class Powerit { public int calc(int n, int k, int m) { BigInteger mod = new BigInteger("" + m); BigInteger two = new BigInteger("2"); // 2^k-1 を求める BigInteger kata = two.pow(k); kata = kata.subtract(BigInteger.ONE); BigInteger ans = BigInteger.ZERO; for (int i = 1; i <= n; i++) { BigInteger tai = new BigInteger("" + i); tai = tai.modPow(kata, mod); ans = ans.add(tai).remainder(mod); } return ans.intValue(); } }
topcoderを甘く見た実装です。結果は…
そりゃそうだ。
この問題は繰り返し二乗法の問題ではないので…1からnまで和を取るところだけ直さないといけませんね…