ユークリッドの互除法(2 つの自然数の最大公約数を求める) - 秋田大学ICPC対策室@wiki

ユークリッドの互除法

ユークリッドの互除法（ユークリッドのごじょほう）は、
2 つの自然数または整式の最大公約数を求める手法の一つです。
詳しい説明は,wikipediaのユークリッドの互除法に載っています。

最大公約数 (GCD) を返す関数

int gcd(int a, int b){
	return (b > 0)? gcd(b, a % b) : a ;
}

最小公倍数 (LCM) を返す関数

int lcm(int a, int b){
	return a / gcd(a, b) * b;
}

...