繰り返し二乗法

目的

$a^n \mod m$を$O(\log m)$で求めます。

計算量

$O(\log m)$

使い方

long pow(long a,long n,long m)
$a^n \mod m$をreturnします。

ソースコード

long pow(long a, long n, long m) {
	long ret = 1;
	for (; n > 0; n >>= 1, a = a * a % m) {
		if (n % 2 == 1) {
			ret = ret * a % m;
		}
	}
	return ret;
}