시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 (추가 시간 없음) 256 MB 168 31 28 29.167%

문제

다음과 같은 조건이 N개 주어진다.

  • i번째 bit가 1이어야 한다. 즉, 어떠한 수 X가 있다면 X & (1 << i)의 값이 0이 아니어야 한다.

1 이상 B 이하의 정수 중 이러한 조건을 만족하는 A의 배수는 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(0 ≤ N < 32), A, B(0 < A, B < 231)가 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 각 줄에는 켜져야 하는 bit가 N개 주어진다. 이 값들은 30이하인 음이 아닌 정수이며, 켜져야 하는 bit는 중복으로 주어지지 않는 것이 보장된다.

출력

1이상 B이하의 정수 중 주어진 N개의 조건들을 만족하는 A의 배수의 개수를 출력하라.

예제 입력 1

1 2 15
1

예제 출력 1

4

출처

Contest > 네블컵 > 제2회 네블컵 B번