수거 묶음의 공통 크기

문제

한 세탁소는 세탁을 마친 작은 수건과 큰 수건을 수거 장소로 보내려 한다. 오늘 보낼 작은 수건은 A장이고 큰 수건은 B장이다. 직원은 수량을 쉽게 확인할 수 있도록 수건을 여러 묶음으로 나누어 포장한다. 이때 작은 수건과 큰 수건을 같은 묶음 안에 섞지 않으며, 두 종류에 사용하는 묶음당 수건 수는 똑같이 정하기로 했다. 묶음당 수건 수를 d라고 하자. 작은 수건은 한 묶음에 정확히 d장씩 넣고, 큰 수건도 한 묶음에 정확히 d장씩 넣는다. 모든 수건을 포장해야 하므로 어느 종류에서도 남는 수건이 생겨서는 안 된다. 마지막 묶음에만 수건을 적게 넣는 것도 허용하지 않는다. 따라서 작은 수건 A장과 큰 수건 B장이 각각 크기 d인 묶음으로 정확히 나누어져야 한다. 두 종류에서 만들어지는 묶음의 개수까지 같을 필요는 없다. 수거 장소에서는 묶음을 한 손으로 옮겨야 하므로, 한 묶음에 들어가는 수건 수를 K장 이하로 제한했다. 직원은 이 제한을 지키면서 묶음당 수건 수를 가능한 한 크게 정하려 한다. 묶음의 총개수를 직접 출력하는 것이 아니라, 조건을 만족하는 가장 큰 d 하나를 구하는 것이 목표이다. 수건의 크기나 무게에 따른 추가 조건은 없으며, 종류에 관계없이 장수만으로 판단한다. A, B, K는 모두 양의 정수이다. d 역시 1 이상 K 이하의 정수여야 한다. 한 묶음에 한 장씩 넣으면 어떤 양의 수량도 남김없이 포장할 수 있으므로, 조건을 만족하는 값은 언제나 존재한다. K가 두 수량보다 크더라도 남김없이 포장할 수 있다는 조건은 그대로 적용된다. 가능한 값이 여러 개이면 그중 가장 큰 값을 출력한다. 주어진 수량과 수거 제한을 이용하여 오늘 사용할 묶음의 크기를 결정한다.

입력

첫째 줄에 작은 수건 수 A, 큰 수건 수 B, 묶음당 최대 수건 수 K가 공백으로 구분되어 주어진다. A, B, K는 모두 1 이상 1,000 이하의 정수이다.

출력

1 이상 K 이하이면서 A와 B를 모두 나누어떨어지게 하는 가장 큰 정수 d를 출력한다. 조건을 만족하는 값은 항상 존재한다.

48 72 10

8

35 64 20

1

30 45 100

15

출처: Devin.KR 자체 제작