유클리드 호제법
아래 영상을 참고해 작성했습니다. https://www.youtube.com/watch?v=Obs-HC5j5bI 정의 자연수 a, b가 주어질 때 a와 b의 최대 공약수 (=gcd(a, b))를 구하는 방법 과정 gcd(A, B) = gcd(B, A % B)를 이용해 재귀적으로 구할 수 있습니다. gcd(12345, 123)을 구해봅시다. (B == 0이 될 때 A 값이 정답임) 증명 위의 영상으로 대체하겠습니다. 코드 매번 큰 비트가 사라지기 때문에 O(max(log a, log b)) 만에 gcd(a, b)를 구할 수 있습니다. #include int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { printf("%d\n", gcd(..
