버스 노선의 공통 점검 간격

문제

한 버스 운행 모형에는 N개의 순환 노선이 있다. 각 노선의 버스는 출발 지점을 떠나 정해진 시간만큼 운행한 뒤 같은 지점으로 돌아오며, 돌아온 즉시 다음 순환을 시작한다. 모든 버스는 시각 0에 동시에 출발하고, 각 노선의 한 바퀴 운행 시간은 양의 정수 분으로 주어진다. 운행 시간은 반복해도 달라지지 않으며, 대기 시간은 없다. 운영자는 모든 노선에 같은 간격의 자동 점검 신호를 적용하려 한다. 점검 간격을 양의 정수 d분으로 정하면 신호는 시각 d, 2d, 3d와 같이 d의 양의 정수 배수인 시각에 발생한다. 시각 0은 운행 시작을 나타내는 기준이며, 점검 신호를 세는 대상에는 포함하지 않는다. 신호는 모든 노선에 동시에 전달되지만, 실제 점검 장치의 동작 시간은 고려하지 않는다. 사용할 수 있는 간격에는 한 가지 필수 조건이 있다. 각 노선의 버스가 한 바퀴를 마치고 출발 지점으로 돌아오는 모든 시각에 반드시 점검 신호가 발생해야 한다. 반대로 버스가 운행 중일 때 추가 신호가 발생하는 것은 허용한다. 서로 다른 노선의 운행 시간이 같아도 각 노선에 이 조건을 그대로 적용한다. 모든 노선이 매번 동시에 돌아올 필요는 없으며, 한 노선의 귀환 시각에 다른 노선의 버스가 운행 중이어도 괜찮다. 장치 설정 범위 때문에 d는 A 이상 B 이하의 정수여야 한다. 두 경계값도 선택할 수 있는 값에 포함된다. 운영자가 검토할 수 있도록 이 범위에서 필수 조건을 만족하는 서로 다른 간격의 개수를 구하고, 그 가운데 가장 큰 간격도 함께 구한다. 같은 간격은 여러 노선에 사용할 수 있더라도 한 번만 센다. 가능한 간격이 하나도 없다면 개수는 0, 가장 큰 간격은 -1로 출력한다. 버스의 실제 운행을 시간순으로 모의 실행할 필요 없이 주어진 운행 시간으로 답을 구한다.

입력

첫째 줄에 정수 N, A, B가 공백으로 구분되어 주어진다.
1 ≤ N ≤ 30,000이며 1 ≤ A ≤ B ≤ 1,000,000,000이다.
둘째 줄에 각 노선의 한 바퀴 운행 시간 T₁, T₂, …, Tₙ이 공백으로 구분되어 주어진다. 각 Tᵢ는 1 이상 1,000,000,000 이하의 정수다. 운행 시간이 같은 노선이 있을 수 있다.

출력

조건을 만족하는 서로 다른 점검 간격의 개수와 그 가운데 가장 큰 간격을 공백으로 구분하여 한 줄에 출력한다. 가능한 간격이 없다면 0 -1을 출력한다.

3 3 20
72 120 168

5 12

2 5 10
18 30

1 6

3 2 100
35 64 81

0 -1

출처: Devin.KR 자체 제작