繰り返し二乗法とは

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

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

問題ページの下の方に行ったら解説ページがあるので、そこを読んでもらえばわかると思いますが、ここでは「繰り返し二乗法」というアルゴリズムを使います。x⁴ を (x²)² と考えると、単純アルゴリズムだと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のメソッドについて調べてみて、今後使う機会があれば使ってみたいと思います。