편의점의 같은 간식 꾸러미

문제

한 편의점에서 행사에 사용할 간식 꾸러미를 준비한다. 준비된 간식은 곡물바 A개와 과일젤리 B개다. 담당자는 준비된 간식을 모두 사용하여 여러 개의 꾸러미를 만들려 한다. 각 간식은 낱개 포장이 되어 있으므로 하나를 쪼개어 서로 다른 꾸러미에 넣을 수 없다. 행사에서 나눠 줄 꾸러미는 내용물이 모두 같아야 한다. 따라서 모든 꾸러미에 들어가는 곡물바의 개수가 서로 같아야 하고, 모든 꾸러미에 들어가는 과일젤리의 개수도 서로 같아야 한다. 다만 한 꾸러미 안에서 곡물바의 개수와 과일젤리의 개수가 같을 필요는 없다. 예를 들어 모든 꾸러미에 곡물바를 2개씩, 과일젤리를 3개씩 넣는 것은 허용된다. 각 꾸러미에는 두 종류의 간식이 모두 적어도 하나씩 들어가야 한다. 간식을 남겨 두거나 버리는 것은 허용되지 않으며, 준비된 것 이외의 간식을 추가할 수도 없다. 꾸러미의 크기나 포장 재료의 수에는 제한이 없다. 조건을 만족하는 방법 중에서 만들 수 있는 꾸러미 수가 가장 큰 방법을 선택한다. 꾸러미를 k개 만든다면 곡물바 A개를 k개의 꾸러미에 같은 개수로 나눌 수 있어야 하며, 과일젤리 B개도 같은 방식으로 나눌 수 있어야 한다. 어느 한 종류라도 나누고 남는 간식이 생긴다면 그 k는 사용할 수 없다. 두 종류의 간식은 각각 적어도 하나 준비되어 있으므로, 모든 간식을 하나의 꾸러미에 넣는 방법은 항상 가능하다. 구해야 하는 값은 한 꾸러미에 들어가는 간식의 총개수가 아니라 만들 수 있는 꾸러미 수의 최댓값이다. 간식을 넣는 순서나 포장 모양은 구분하지 않는다. 주어진 두 간식의 개수를 이용하여 모든 조건을 만족하는 최대 꾸러미 수를 구한다.

입력

첫째 줄에 곡물바의 개수 A와 과일젤리의 개수 B가 공백으로 구분되어 주어진다. A와 B는 정수이며 1 ≤ A, B ≤ 1,000이다.

출력

만들 수 있는 꾸러미 수의 최댓값을 정수 하나로 출력한다. 조건을 만족하는 방법은 항상 존재한다.

18 30

6

7 16

1

9 9

9

출처: Devin.KR 자체 제작