math/gcd-lcm.cpp


1
2
3
4
5
6
7
8

// Laufzeiten: O(log(a) + log(b))
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd (b, a % b);
}

ll lcm(ll a, ll b) {
	return a * (b / gcd(a, b)); // Klammern gegen Overflow.
}