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

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

JavaのBigInteger.modPowはどの程度使えるのか

繰り返し二乗法とは

AOJの問題でこんなものがあります

Power | Aizu Online Judge

mとnが入力として与えられるので、mn を 1000000007 で割った余りを出力せよという問題です。n が最大で 109 なので、単純にn-1回「掛けてmodで割る」を繰り返しても間に合いません。

問題ページの下の方に行ったら解説ページがあるので、そこを読んでもらえばわかると思いますが、ここでは「繰り返し二乗法」というアルゴリズムを使います。x4 を (x2)2 と考えると、単純アルゴリズムだと3回かかってた計算が2回で済みます。log(n) 回で計算が済むというものです。

JavaだとBigIntegerで解ける…?

しかしこの問題、Javaだとこれだけのコードで済みます。

import java.io.*;
import java.util.*;
import java.math.*;


class Main {
    static Scanner sc = new Scanner(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        BigInteger n = new BigInteger(sc.next());
        BigInteger m = new BigInteger(sc.next());
        System.out.println(n.modPow(m, new BigInteger("1000000007")));
    }
}

BigIntegerのmodPowというメソッドを使うと一発で終わってしまうのです。これがAcceptされるということは、この中では繰り返し二乗法が使われていることになります。また、modの計算までよしなにやってくれているようなのです。

BigIntegerは遅いというイメージがあったので驚きでした。繰り返し二乗法を使っていると、logオーダーになり、オーダー的にはかなり小さくなるので、一回の計算のオーダーが多少悪かったとしても間に合うというオチなのかもしれません。BigIntegerのメソッドについて調べてみて、今後使う機会があれば使ってみたいと思います。