最大公約数

目的

整数a,bの最大公約数を$O(\log (\max(a,b)))$で求めます。

計算量

$O(\log (\max(a,b)))$

使い方

long gcd(long a,long b)
aとbの最大公約数をreturnします。

ソースコード

long gcd(long a, long b) {
	if (a > b)
		return gcd(b, a);
	if (a == 0)
		return b;
	return gcd(a, b % a);
}