はじめに

前回、BigIntegerにmodPowというメソッドがあり、中では繰り返し二乗法を使っていて、意外と使えるかもしれない？どこまで使えるのか？という話をしました。

<a href="http://yoshiki-utakata.hatenablog.com/entry/2015/06/15/010206">JavaのBigInteger.modPowはどの程度使えるのか - もしも社会人プログラマーがtopcoderのイエローコーダーを目指したら</a>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();
    }
}