공연장 좌석 묶음

문제

작은 공연장에서 단체 관람객에게 나누어 줄 좌석 묶음을 준비한다. 이번 공연에 사용할 좌석은 모두 N개이며, 준비한 좌석을 하나도 남기지 않고 여러 묶음으로 나누려 한다. 각 묶음에 들어가는 좌석 수는 모두 같아야 한다. 좌석에 붙은 번호나 실제로 놓인 위치는 묶음을 만드는 데 영향을 주지 않는다. 담당자는 한 묶음에 들어갈 좌석 수를 정수 k로 정한다. 그러면 모든 묶음은 정확히 k개의 좌석으로 이루어져야 하며, 마지막 묶음만 다른 수의 좌석을 갖도록 만들 수는 없다. 따라서 N을 k로 나누었을 때 나머지가 0인 경우에만 그 크기로 묶음을 만들 수 있다. 묶음이 하나만 만들어져도 괜찮으며, 한 묶음에 좌석이 하나만 들어가는 것도 허용한다. 단체 예약 안내에는 한 묶음의 좌석 수가 L개 이상 R개 이하여야 한다고 적혀 있다. 두 경계값도 허용되는 크기에 포함된다. N을 남김없이 나눌 수 있더라도 이 범위를 벗어나는 크기는 선택할 수 없다. 또한 좌석을 추가하거나 일부 좌석을 사용하지 않는 방법으로 범위를 맞추어서는 안 된다. 담당자는 조건을 만족하는 크기 가운데 가장 큰 값을 선택하려 한다. 같은 조건에서 작은 묶음을 많이 만드는 것보다 큰 묶음을 적게 만드는 것을 우선하기 때문이다. 구하려는 값은 만들어지는 묶음의 개수가 아니라 한 묶음에 들어가는 좌석 수 k이다. 예를 들어 어떤 크기를 검사할 때에는 먼저 그 크기가 안내된 범위에 들어가는지 확인하고, 이어서 전체 좌석을 그 크기로 정확히 나눌 수 있는지 확인하면 된다. 가능한 크기가 여러 개라면 가장 큰 정수 하나가 답이므로 별도의 동점 처리는 필요하지 않다. 가능한 크기가 하나도 없다면 좌석 묶음 준비가 불가능하다는 뜻으로 0을 출력한다. N, L, R이 주어졌을 때 담당자가 선택할 값을 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 1,000
1 ≤ L ≤ R ≤ 1,000

출력

조건을 만족하는 한 묶음의 좌석 수 중 최댓값을 정수 하나로 출력한다. 조건을 만족하는 값이 없으면 0을 출력한다.

84 5 15

14

17 3 10

0

1 1 1

1

출처: Devin.KR 자체 제작