BOJ 2436 - 공약수

문제 링크

---

https://www.acmicpc.net/problem/2436

문제 해결

---

1. 구하려는 두 수를 a, b로 놓는다.

2. a == (GCD*x), b == (GCD*y) 이므로, measure = x*y (x*y == LCM/GCD)

3. measure의 (x,y)쌍을 찾되 합이 가장 작은 것을 찾아야하므로 시간을 단축하기 위해, sqrt(measure)부터 찾는다.

주의할 점

---

1. LCM == GCD*x*y가 성립하기 위해선 반드시 x와 y가 서로소임을 보여야한다.

※ 정확하고 부드러운 태클은 언제나 환영입니다.