BOJ: https://www.acmicpc.net/problem/14404


X, Y 시스템이 A, B 시스템을 포함하려면
(1) gcd(X, Y) | gcd(A, B)
(2) 작은 가격에 대해서 A, B 시스템에서 생성 가능한 가격을 모두 만들 수 있어야 함


여기서 작은 가격은 max(A * B, X * Y) 까지만 확인해도 충분하다. (궁금하다면 설탕 배달, 쿨한 물건 구매를 풀어보자)
그런데 귀찮으니까 최대값인 40000으로 설정해도 된다.


가능한 Y의 값이 무한하다는 말은 Y가 필요없다는 말과 동일하다 (Y를 매우 크게 잡았다고 가정하면?)
그러면 X | gcd(A, B) 인 경우에만 -1을 출력하면 된다.


이외의 경우는 Y가 max(A, B)를 넘을 수 없다. 그러면 A나 B중 하나를 X로만 만들 수 없기 때문이다.
이 모든 경우를 고려하면 O(N^3) (N은 A, B, X의 가능한 최대값)이므로, Naive 한 알고리즘으로도 해결 할 수 있다.


아래는 Go로 작성한 예시 소스코드