cinador   4년 전

문제

보통 서기 x년이 윤년인지 아닌지는 다음과 같이 판단한다.

  1. x가 400의 배수이면 윤년이다.
  2. x가 400의 배수가 아닐 때, 100의 배수이면 윤년이 아니다.
  3. x가 100의 배수도 아닐 때, 4의 배수이면 윤년이다.
  4. x가 4의 배수도 아니면 윤년이 아니다.

이것은 다음과 같이 일반화 할 수 있다. 임의의 수열 A1, ..., An 에 대해 서기 x년이 "일반화 윤년"인지 아닌지는 다음과 같이 판단한다.

  1. x가 Ai 의 배수가 되는 가장 작은 i (1 ≤ i ≤ n) 에 대해, i 가 홀수면 일반화 윤년이고, 짝수면 일반화 윤년이 아니다.
  2. 이를 만족하는 i 가 없으면, n이 홀수면 일반화 윤년이 아니고, 짝수면 일반화 윤년이다.

예를 들어, A = [400, 100, 4] 일 때, A에 대응하는 일반화 윤년은 우리가 지금 쓰고 있는 윤년과 동일하다.

수열 A1, ..., An 와 자연수 l, r 이 주어졌을 때, l ≤ x ≤ r 을 만족하는 자연수 x 중에서 서기 x년이 A에 대응하는 일반화 윤년인 x의 개수를 구하여라.

ㅤ

입력

입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.

preview

n은 1 ≤ n ≤ 50, l, r은 1 ≤ l ≤ r ≤ 4000, 모든 i 에 대해 Ai는 1 ≤ Ai ≤ 4000을 만족한다. 모든 입력은 자연수이다.

입력의 마지막에는 3개의 0이 주어진다.

ㅤ

출력

각 테스트 케이스의 답을 한 줄에 하나씩 출력한다.

댓글을 작성하려면 로그인해야 합니다.