두 수업의 모둠 정원

문제

한 학원에서 오전 수업과 오후 수업에 사용할 모둠 활동 계획을 세운다. 오전 수업의 수강생은 A명이고 오후 수업의 수강생은 B명이다. 두 수업의 학생을 서로 섞지는 않지만, 활동지를 같은 방식으로 제작하기 위해 모든 모둠의 정원은 하나의 값으로 통일하려 한다. 여기서 정원은 모둠 하나에 실제로 들어가는 학생 수를 뜻한다. 선택한 정원을 d라고 할 때, 오전 수업의 모든 학생을 정확히 d명씩 나누고 오후 수업의 모든 학생도 정확히 d명씩 나눌 수 있어야 한다. 어느 수업에서도 학생이 남아서는 안 되며, 정원보다 적은 학생이 들어가는 모둠을 따로 만들 수도 없다. 두 수업의 모둠 수가 같을 필요는 없다. 예를 들어 한 수업에 모둠이 두 개 생기고 다른 수업에 모둠이 세 개 생기는 것은 허용된다. 학원에서 준비한 활동용 책상에는 한 모둠이 최대 K명까지 앉을 수 있다. 따라서 정원 d는 1 이상 K 이하인 정수여야 한다. A와 B를 모두 나누어떨어지게 하더라도 K보다 큰 정원은 선택할 수 없다. 책상은 필요한 만큼 준비되어 있으므로 전체 모둠 수에는 별도의 제한이 없다. 담당자는 조건을 만족하는 정원 중 가장 큰 값을 선택하려 한다. 이 문제에서 크게 만들려는 값은 모둠 수가 아니라 모둠 하나에 들어가는 학생 수다. 따라서 가능한 정원을 찾은 뒤 두 수업의 모둠 수를 비교하거나 합할 필요는 없다. 학생을 배치하는 순서와 학생의 이름도 결과에 영향을 주지 않는다. A, B, K가 주어질 때 담당자가 선택할 정원을 구한다. 세 입력은 모두 1 이상의 정수이므로 정원을 1명으로 정하면 항상 조건을 만족한다. 따라서 가능한 정원이 없는 경우는 주어지지 않는다. 가장 큰 정수 값은 하나로 결정되므로 별도의 동점 처리도 필요하지 않다.

입력

첫째 줄에 정수 A, B, K가 공백으로 구분되어 주어진다.
1 ≤ A, B, K ≤ 1,000이다.

출력

A와 B를 모두 나누어떨어지게 하는 1 이상 K 이하의 정수 중 최댓값을 출력한다.

24 36 8

6

17 23 10

1

18 30 4

3

출처: Devin.KR 자체 제작