エンジニアの競馬情報収集ブログ

最近は5割が競馬の話、3割がLoL/LJLの話、2割が技術的な話な感じ。たまにその他の話。

続・BigIntegerはどこまで万能なのか。

はじめに

前回、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を甘く見た実装です。結果は…

f:id:yoshiki_utakata:20150616002453p:plain

そりゃそうだ。

この問題は繰り返し二乗法の問題ではないので…1からnまで和を取るところだけ直さないといけませんね…