은행 창구의 동전 묶음

문제

한 은행 창구에서는 하루 동안 받은 동전을 종류별로 나누어 임시 보관한다. 오늘 정리할 동전은 두 종류이며, 첫 번째 종류는 A개, 두 번째 종류는 B개다. 담당자는 같은 종류의 동전끼리만 묶어서 보관하려 한다. 한 묶음에 들어가는 동전 수는 모든 묶음에서 같아야 하며, 두 종류에 서로 다른 묶음 크기를 사용할 수 없다. 사용할 묶음 크기를 양의 정수 d라고 하자. 첫 번째 종류의 동전을 정확히 d개씩 나누어 묶었을 때 남는 동전이 없어야 하고, 두 번째 종류도 정확히 d개씩 묶었을 때 남는 동전이 없어야 한다. 종류가 다른 동전을 한 묶음에 섞거나, 일부 동전을 묶지 않은 채 따로 보관하는 방법은 허용하지 않는다. 동전의 금액은 판단에 영향을 주지 않으며, 오직 각 종류의 동전 개수만 사용한다. 창구에 준비된 포장 도구는 한 묶음에 최대 C개의 동전만 넣을 수 있다. 따라서 d는 C 이하여야 한다. 이 제한 안에서 가능한 묶음 크기 중 가장 큰 값을 선택하려 한다. 묶음 크기를 크게 선택할수록 한 번에 정리하는 동전 수가 많아지므로, 담당자는 묶음의 총개수 대신 묶음 크기 자체를 기준으로 결정한다. 포장 도구의 최대 용량을 반드시 채울 필요는 없다. 입력으로 두 종류의 동전 개수와 포장 도구의 최대 용량이 주어진다. 모든 조건을 만족하는 가장 큰 묶음 크기를 구한다. 두 종류 모두 동전이 적어도 하나 있으며, C도 1 이상이므로 동전을 하나씩 묶는 방법은 항상 가능하다. 따라서 가능한 묶음 크기가 없는 경우는 발생하지 않으며, 출력할 최댓값은 언제나 하나로 정해진다.

입력

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

출력

A와 B를 모두 나누어떨어지게 하는 양의 정수 중 C 이하인 가장 큰 값을 출력한다.

24 36 8

6

17 25 10

1

30 45 100

15

출처: Devin.KR 자체 제작