세탁소의 같은 구성 꾸러미

문제

세탁소에서 세탁을 마친 손수건 A장과 작은 수건 B장을 배달용 꾸러미에 나누어 담으려 한다. 두 종류의 세탁물은 서로 구별하며, 각 종류 안에서는 어느 물건을 골라도 상관없다. 직원은 배달받는 사람이 꾸러미를 바꾸어 받아도 내용이 같도록 모든 꾸러미의 구성을 정확히 맞추려 한다. 꾸러미의 구성이 같다는 것은 각 꾸러미에 들어 있는 손수건의 장수가 모두 같고, 각 꾸러미에 들어 있는 작은 수건의 장수도 모두 같다는 뜻이다. 한 꾸러미 안에서 손수건과 작은 수건의 장수가 서로 같아야 하는 것은 아니다. 예를 들어 모든 꾸러미에 손수건 두 장과 작은 수건 세 장을 넣는 방식도 같은 구성으로 인정한다. 각 꾸러미에는 두 종류가 모두 한 장 이상 들어 있어야 한다. 준비한 손수건과 작은 수건은 한 장도 남기지 않고 전부 사용해야 한다. 세탁물을 자르거나 다른 종류로 바꾸는 일은 허용하지 않으며, 추가 세탁물을 가져올 수도 없다. 따라서 꾸러미 수를 정했다면 손수건과 작은 수건을 각각 그 수만큼 똑같이 나눌 수 있어야 한다. 한 종류만 남는 방식이나 마지막 꾸러미에 남은 물건을 몰아넣는 방식은 허용하지 않는다. 직원은 이 조건을 만족하면서 꾸러미를 가능한 한 많이 만들려 한다. 만들 수 있는 최대 꾸러미 수를 구하는 프로그램을 작성한다. 꾸러미에 번호를 붙이는 순서나 물건을 고르는 순서는 답에 영향을 주지 않는다. A와 B는 모두 양수이므로 전체 세탁물을 하나의 꾸러미에 담는 방법은 항상 가능하다. 따라서 가능한 방법이 없는 경우는 없으며, 출력할 값은 항상 1 이상의 정수다.

입력

첫째 줄에 손수건 수 A와 작은 수건 수 B가 공백으로 구분되어 주어진다. A와 B는 각각 1 이상 1,000 이하의 정수다.

출력

조건을 만족하며 만들 수 있는 최대 꾸러미 수를 한 줄에 출력한다.

18 30

6

17 24

1

28 28

28

출처: Devin.KR 자체 제작