모든 코스에 맞는 표지 간격

문제

한 마라톤 대회에서는 참가자의 준비 정도에 따라 선택할 수 있도록 길이가 서로 다른 여러 코스를 운영한다. 운영진은 참가자가 달린 거리를 쉽게 확인하도록 각 코스에 거리 표지를 설치하려 한다. 모든 코스에서 같은 간격을 사용하면 안내문을 통일할 수 있으므로, 코스마다 다른 간격을 정하는 대신 하나의 공통 간격 d를 선택하기로 했다. 각 코스의 길이는 미터 단위의 양의 정수다. 간격 d 역시 미터 단위의 양의 정수로 정한다. 길이가 A미터인 코스에서는 출발점으로부터 d미터, 2d미터, 3d미터처럼 d의 배수인 거리에 표지를 설치한다. 출발점은 거리 0인 기준점이며, 별도의 거리 표지는 설치하지 않는다. 마지막 표지는 반드시 결승점과 정확히 일치해야 하고, 결승점을 지나서 표지를 설치할 수는 없다. 따라서 길이가 A인 코스에 간격 d를 사용할 수 있으려면 A를 d로 나눈 나머지가 0이어야 한다. d가 코스 길이와 같다면 결승점에 표지 하나만 설치하므로 허용한다. 반대로 d가 어떤 코스의 길이보다 크다면 그 코스의 결승점에 표지를 설치할 수 없으므로 허용하지 않는다. 코스들이 서로 다른 장소에 있더라도 이 조건은 각 코스의 길이만으로 판단한다. 운영진이 사용할 수 있는 표지 간격의 범위는 L미터 이상 R미터 이하다. 두 경계값 L과 R도 후보에 포함한다. 이 범위에 있는 정수 d 중에서 주어진 N개 코스 모두에 사용할 수 있는 간격이 몇 개인지 구해야 한다. 같은 길이의 코스가 여러 번 주어져도 각각 동일한 조건을 적용하며, 같은 간격을 여러 번 세지는 않는다. 여러 간격이 조건을 만족하면 그 개수를 모두 세고, 만족하는 간격이 하나도 없으면 0을 출력한다. 표지의 총개수나 가장 큰 간격을 구하는 것이 아니라, 선택 가능한 서로 다른 간격의 개수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, L, R이 공백으로 구분되어 주어진다. 둘째 줄에 각 코스의 길이를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000, 1 ≤ L ≤ R ≤ 1,000,000, 1 ≤ A_i ≤ 1,000,000이다. 모든 거리의 단위는 미터다.

출력

L 이상 R 이하인 정수 간격 중에서 모든 코스에 사용할 수 있는 서로 다른 간격의 개수를 정수 하나로 출력한다. 가능한 간격이 없으면 0을 출력한다.

3 2 12
24 36 60

5

2 4 5
18 30

0

1 1 9
9

3

출처: Devin.KR 자체 제작