영화관의 안내 카드 묶음

문제

한 영화관은 상영관 입구에서 나누어 줄 두 종류의 안내 카드를 준비했다. 첫 번째 종류는 관람 예절을 설명하고, 두 번째 종류는 다음 상영 일정을 설명한다. 창고에는 첫 번째 카드가 A장, 두 번째 카드가 B장 있으며, 직원은 두 종류의 카드를 각각 여러 묶음으로 나누어 보관하려 한다. 한 묶음에는 한 종류의 카드만 넣을 수 있다. 보관함에 붙일 표기를 통일하기 위해 모든 묶음에 들어가는 카드 수를 같은 양의 정수 D로 정해야 한다. 첫 번째 카드끼리 만든 묶음과 두 번째 카드끼리 만든 묶음에도 같은 D를 사용한다. 카드를 버리거나 새로 추가할 수 없으며, 낱장으로 남겨 두는 것도 허용하지 않는다. 따라서 A장과 B장 모두 각각 D장씩 정확하게 나누어져야 한다. 두 종류의 묶음 개수까지 같을 필요는 없다. 묶음 하나를 담는 봉투에는 카드가 최대 K장 들어간다. 그러므로 D는 K 이하여야 한다. 직원은 봉투를 여닫는 횟수를 줄이기 위해, 이 조건을 만족하는 D 중 가장 큰 값을 선택하려 한다. 카드의 종류에 따라 서로 다른 묶음 크기를 선택하거나, 일부 묶음에만 적은 수의 카드를 넣는 방법은 사용할 수 없다. 예를 들어 두 카드의 수가 모두 어떤 수로 나누어지더라도 그 수가 봉투의 용량을 넘으면 선택할 수 없다. 반대로 봉투의 용량 이하라는 이유만으로 선택할 수 있는 것은 아니며, 두 종류 모두 나머지 없이 나누어지는지도 확인해야 한다. 카드 수와 봉투의 용량은 모두 양의 정수이므로 D를 1로 정하는 방법은 항상 가능하다. 따라서 정답이 없는 입력은 없다. A, B, K가 주어졌을 때 직원이 선택할 가장 큰 묶음 크기 D를 구하는 프로그램을 작성한다. 가능한 값 중 수치상 가장 큰 정수 하나가 답이며, 묶음의 배치 순서나 각 종류의 묶음 개수는 출력하지 않는다.

입력

첫째 줄에 정수 A, B, K가 공백으로 구분되어 주어진다.
A와 B는 각각 1 이상 1000000000 이하이고, K도 1 이상 1000000000 이하이다.

출력

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

84 126 10

7

35 64 20

1

144 216 100

72

출처: Devin.KR 자체 제작