승강장 안내 띠의 공통 길이

문제

지하철역의 시설 담당자는 두 승강장에 붙일 안내 띠를 준비하고 있다. 첫 번째 승강장에 사용할 띠의 길이는 A센티미터이고, 두 번째 승강장에 사용할 띠의 길이는 B센티미터다. 두 띠는 이미 필요한 전체 길이에 맞추어 준비되어 있으므로 버리거나 다른 띠를 이어 붙일 수 없다. 담당자는 안내 문구를 일정한 간격으로 반복해서 붙이기 위해 두 띠를 같은 길이의 조각들로 나누려 한다. 조각 하나의 길이를 d센티미터로 정하면, 첫 번째 띠에서 나오는 모든 조각과 두 번째 띠에서 나오는 모든 조각의 길이가 전부 d여야 한다. 어느 띠에서도 마지막에 짧은 조각이나 자투리가 남아서는 안 된다. 따라서 A와 B가 모두 d로 나누어떨어져야 한다. 안내 문구를 읽을 수 있는 공간을 확보하려면 조각의 길이는 적어도 2센티미터여야 한다. 또한 작업대에 놓인 절단 도구는 한 조각의 길이가 C센티미터를 넘는 작업을 지원하지 않는다. 조각의 길이는 센티미터 단위의 정수로만 정할 수 있다. 두 띠에서 만들어지는 조각의 개수는 서로 달라도 되며, 길이가 조건을 만족하면 띠 하나를 자르지 않고 그대로 한 조각으로 사용하는 것도 허용한다. 시설 담당자는 반복해서 붙여야 하는 조각의 수를 줄이기 위해 가능한 조각 길이 중 가장 큰 값을 선택한다. 두 띠에 서로 다른 조각 길이를 적용하거나, 일부 조각만 다른 길이로 만드는 방법은 사용할 수 없다. A, B, C가 주어졌을 때 모든 조건을 만족하는 가장 큰 정수 d를 구한다. 조건을 만족하는 길이가 하나도 없다면 작업이 불가능하다는 뜻으로 0을 구한다.

입력

첫째 줄에 A, B, C가 공백으로 구분되어 주어진다. A, B, C는 각각 1 이상 1,000 이하의 정수이며, 길이의 단위는 센티미터다.

출력

2 이상 C 이하이면서 A와 B를 모두 나누어떨어지게 하는 가장 큰 정수 d를 출력한다. 그러한 정수가 없으면 0을 출력한다.

24 36 8

6

7 11 10

0

18 18 18

18

출처: Devin.KR 자체 제작