最大公約数

目的

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

計算量

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

使い方

recursive integer(kind=8) gcd(integer(kind=8) a,integer(kind=8) b)
aとbの最大公約数をreturnします。

ソースコード

recursive integer(kind=8) function gcd(a,b)result(res)
	integer(kind=8)::a,b
	if(a<b)then
		res=gcd(b,a)
		return
	end if
	if(b==0)then
		res=a
	else
		res=gcd(mod(a,b),b)
	end if
end function